p*u
发帖数: 136 | 1 电面imo.im被问到的2个题目，45分钟，都需要写代码出来，结果是挂了。
问题二略微有点变态！
问题一
Subsequences
------------
You're given a large string T. And a stream of smaller string S1, S2, S3 ...
Determine whether Si is a subsequence of T.
|T| < 10 000 000
|Si| < 100
alphabet is 'a' - 'z'
T = abcdefg
S1 = abc yes
S2 = ag yes
S3 = ga no
S4 = aa no
--------------
问题二
Rectangles
----------
their is a window of size WxH contains Number of existing rectangles with
given (xi, yi, wi, hi).
Where to place a new rectangle with dimensions w, h such that the sum of the
overlapping area with existing rectangles is minimized.
* all current rectangles fit fully in the window
* place new window fully inside
* no existing windows overlap (but the new one may ovelap when you place it)
W,H < 10 000
N -- number of windows < 100
xi, yi, wi, hi, w, h -- no limitations other than fitting in the screen.
-----------
另外推荐一个微信公众号：待字闺中
每天会推荐一个不错的面试题，质量很高。 | f****e
发帖数: 34 | 2 第一题就是这个题啊： http://www.itint5.com/oj/#15
去年fb onsite也有这题
..
【在 p*u 的大作中提到】
: 电面imo.im被问到的2个题目，45分钟，都需要写代码出来，结果是挂了。
: 问题二略微有点变态！
: 问题一
: Subsequences
: ------------
: You're given a large string T. And a stream of smaller string S1, S2, S3 ...
: Determine whether Si is a subsequence of T.
: |T| < 10 000 000
: |Si| < 100
: alphabet is 'a' - 'z'
| g****o
发帖数: 547 | 3 第二题 把矩形所占的方格都设为-1，
就是个最大子矩阵和问题
解法o(w^2*h)or o(w*h^2)
不知道有没有更简单的解。N<100这个条件没用上
..
【在 p*u 的大作中提到】
: 电面imo.im被问到的2个题目，45分钟，都需要写代码出来，结果是挂了。
: 问题二略微有点变态！
: 问题一
: Subsequences
: ------------
: You're given a large string T. And a stream of smaller string S1, S2, S3 ...
: Determine whether Si is a subsequence of T.
: |T| < 10 000 000
: |Si| < 100
: alphabet is 'a' - 'z'
| z*********8
发帖数: 2070 | 4 那做法是？
【在 f****e 的大作中提到】
: 第一题就是这个题啊： http://www.itint5.com/oj/#15
: 去年fb onsite也有这题
:
: ..
| x*******6
发帖数: 262 | | g****o
发帖数: 547 | 6 应该对T做预处理，加快后面每次query的速度
我是这样想的
开矩阵index[255][|T|+1] (如果只有小写字母那就index[26][|T|+1]）
index[x][y]表示T字符串中在位置y以后的下个x字符的index,如果没有就存-1
假设T=abcdefg, S=ag
S的第一个字符是a,就看index['a'][0]的值是1.
第二个字符是g,就去看index['g'][1] (1是由index['a'][0]得来的）的值是7.
扫完S，这个过程中没有出现-1,答案就是yes,否则是no
这样预处理时间o(T),每次query时间o(S),不必每次都扫一遍T.
【在 x*******6 的大作中提到】
: 第一个题不就在T和Si上扫一遍不就行了么。
| g****o
发帖数: 547 | 7 第二题我又想了个解法，不知道有没有人来讨论下还有没有更好的解:)
所求矩形的上边要么贴着边界，要么贴着某个已有矩形的下边
所求矩形的下边要么贴着边界，要么贴着某个已有矩形的上边
所求矩形的左边要么贴着边界，要么贴着某个已有矩形的右边
所求矩形的右边要么贴着边界，要么贴着某个已有矩形的左边
因为N只有100,这样所有所求的矩形不超过1e8种可能
用brute-force依次检验是否和现有矩形重叠,并求最大，最终时间1e10
在给定限制条件下，比刚才的1e12要好一点,也差不多达到了可接受的计算时间
C++花几分钟到十几分钟吧
【在 g****o 的大作中提到】
: 第二题 把矩形所占的方格都设为-1，
: 就是个最大子矩阵和问题
: 解法o(w^2*h)or o(w*h^2)
: 不知道有没有更简单的解。N<100这个条件没用上
:
: ..
| j***1
发帖数: 39 | 8 经典题
【在 f****e 的大作中提到】
: 第一题就是这个题啊： http://www.itint5.com/oj/#15
: 去年fb onsite也有这题
:
: ..
| f****e
发帖数: 34 | 9 你想的也太简单了……
【在 x*******6 的大作中提到】
: 第一个题不就在T和Si上扫一遍不就行了么。
| f****e
发帖数: 34 | 10 这题挺多方法的，hash，利用快排对后缀下标排序+二分，或者直接后缀数组+二分等。
【在 z*********8 的大作中提到】
: 那做法是？
| | | g**y
发帖数: 46 | 11 这解法需要很大内存（>2G), 能被接受吗？
【在 g****o 的大作中提到】
: 应该对T做预处理，加快后面每次query的速度
: 我是这样想的
: 开矩阵index[255][|T|+1] (如果只有小写字母那就index[26][|T|+1]）
: index[x][y]表示T字符串中在位置y以后的下个x字符的index,如果没有就存-1
: 假设T=abcdefg, S=ag
: S的第一个字符是a,就看index['a'][0]的值是1.
: 第二个字符是g,就去看index['g'][1] (1是由index['a'][0]得来的）的值是7.
: 扫完S，这个过程中没有出现-1,答案就是yes,否则是no
: 这样预处理时间o(T),每次query时间o(S),不必每次都扫一遍T.
| l****o
发帖数: 315 | 12 和我想的一样诶。而且表达更精简。不错。楼上说经典题的能不能贴个解答或者给个解
答链接什么的，光说经典不经典跟没回有什么区别。
【在 g****o 的大作中提到】
: 应该对T做预处理，加快后面每次query的速度
: 我是这样想的
: 开矩阵index[255][|T|+1] (如果只有小写字母那就index[26][|T|+1]）
: index[x][y]表示T字符串中在位置y以后的下个x字符的index,如果没有就存-1
: 假设T=abcdefg, S=ag
: S的第一个字符是a,就看index['a'][0]的值是1.
: 第二个字符是g,就去看index['g'][1] (1是由index['a'][0]得来的）的值是7.
: 扫完S，这个过程中没有出现-1,答案就是yes,否则是no
: 这样预处理时间o(T),每次query时间o(S),不必每次都扫一遍T.
| r**a
发帖数: 31 | 13 你复杂度是不是算错了，新窗口的w,h是给定的，窗口的位置有O(N^2)种可能，每次计
算重叠是O(N)，总复杂度不过O(N^3) 1e6
第二题我又想了个解法，不知道有没有人来讨论下还有没有更好的解:)
所求矩形的上边要么贴着边界，要么贴着某个已有矩形的下边
所求矩形的下边要么贴着边界，要么贴着某个已有矩形的上边
所求矩形的左边要么贴着边界，要么贴着某个已有矩形的右边
所求矩形的右边要么贴着边界，要么贴着某个已有矩形的左边
因为N只有100,这样所有所求的矩形不超过1e8种可能
用brute-force依次检验是否和现有矩形重叠,并求最大，最终时间1e10
在给定限制条件下，比刚才的1e12要好一点,也差不多达到了可接受的计算时间
C++花几分钟到十几分钟吧
【在 g****o 的大作中提到】
: 第二题我又想了个解法，不知道有没有人来讨论下还有没有更好的解:)
: 所求矩形的上边要么贴着边界，要么贴着某个已有矩形的下边
: 所求矩形的下边要么贴着边界，要么贴着某个已有矩形的上边
: 所求矩形的左边要么贴着边界，要么贴着某个已有矩形的右边
: 所求矩形的右边要么贴着边界，要么贴着某个已有矩形的左边
: 因为N只有100,这样所有所求的矩形不超过1e8种可能
: 用brute-force依次检验是否和现有矩形重叠,并求最大，最终时间1e10
: 在给定限制条件下，比刚才的1e12要好一点,也差不多达到了可接受的计算时间
: C++花几分钟到十几分钟吧
| g****o
发帖数: 547 | 14 厄。。。我把题目看错了
我试图去算不overlap的最大矩形
所以上面提的两种方法都不对
给定的w,h的话好办
把矩阵围着的设1,不围的设0
先算dp[x][y],表示第0~x列和第0~y行内所有的元素和
这样一个w,h的矩阵所围面积就是dp[x][y]-dp[x][y-h]-dp[x-w][y]+dp[x-w][y-h]
对x,y穷举一遍，求最小面积
时间是o(W*H)=1e8
【在 r**a 的大作中提到】
: 你复杂度是不是算错了，新窗口的w,h是给定的，窗口的位置有O(N^2)种可能，每次计
: 算重叠是O(N)，总复杂度不过O(N^3) 1e6
:
: 第二题我又想了个解法，不知道有没有人来讨论下还有没有更好的解:)
: 所求矩形的上边要么贴着边界，要么贴着某个已有矩形的下边
: 所求矩形的下边要么贴着边界，要么贴着某个已有矩形的上边
: 所求矩形的左边要么贴着边界，要么贴着某个已有矩形的右边
: 所求矩形的右边要么贴着边界，要么贴着某个已有矩形的左边
: 因为N只有100,这样所有所求的矩形不超过1e8种可能
: 用brute-force依次检验是否和现有矩形重叠,并求最大，最终时间1e10
| g****o
发帖数: 547 | 15 内存是不是应该4Byte*1e7*26 才1GB啊
不过那个矩阵的确有冗余的，把重复的元素去掉，用二分法来找下一元素位置也可以
这样算法复杂度o(S*lgT)
以上解法都是我拍脑袋自己想的
不知道哪位大侠来分享下经典题的标准解法，呵呵
【在 g**y 的大作中提到】
: 这解法需要很大内存（>2G), 能被接受吗？
| g**y
发帖数: 46 | 16 按 256算的
【在 g****o 的大作中提到】
: 内存是不是应该4Byte*1e7*26 才1GB啊
: 不过那个矩阵的确有冗余的，把重复的元素去掉，用二分法来找下一元素位置也可以
: 这样算法复杂度o(S*lgT)
: 以上解法都是我拍脑袋自己想的
: 不知道哪位大侠来分享下经典题的标准解法，呵呵
| p*u
发帖数: 136 | 17 O(N^3)，面试就写的这种做法，但是求2个矩形overlap的地方写残了。
按照goodoo说的求矩形和的方法来算overlap，写起来更简单一点，但是要耗费O(W*H)
的空间，不是很优的解法。
猜想应用场景是：电脑屏幕上已经有了n个聊天框，新建一个聊天框，放在屏幕的哪个
位置最好。客户端计算的话，空间复杂度太高的算法应该是没法实际应用的。
总的来说，算法不难，一次写好比较难。
【在 r**a 的大作中提到】
: 你复杂度是不是算错了，新窗口的w,h是给定的，窗口的位置有O(N^2)种可能，每次计
: 算重叠是O(N)，总复杂度不过O(N^3) 1e6
:
: 第二题我又想了个解法，不知道有没有人来讨论下还有没有更好的解:)
: 所求矩形的上边要么贴着边界，要么贴着某个已有矩形的下边
: 所求矩形的下边要么贴着边界，要么贴着某个已有矩形的上边
: 所求矩形的左边要么贴着边界，要么贴着某个已有矩形的右边
: 所求矩形的右边要么贴着边界，要么贴着某个已有矩形的左边
: 因为N只有100,这样所有所求的矩形不超过1e8种可能
: 用brute-force依次检验是否和现有矩形重叠,并求最大，最终时间1e10
| g****o
发帖数: 547 | 18 谢谢
2个矩形overlap leetcode上有讨论
但那个解有错，不知道为什么一直没有改
应该是
( P2.y ≤ P3.y && P1.y ≥ P4.y && P2.x ≥ P3.x && P1.x ≤ P4.x )
能不能评价下第一题的解法呢？
【在 p*u 的大作中提到】
: O(N^3)，面试就写的这种做法，但是求2个矩形overlap的地方写残了。
: 按照goodoo说的求矩形和的方法来算overlap，写起来更简单一点，但是要耗费O(W*H)
: 的空间，不是很优的解法。
: 猜想应用场景是：电脑屏幕上已经有了n个聊天框，新建一个聊天框，放在屏幕的哪个
: 位置最好。客户端计算的话，空间复杂度太高的算法应该是没法实际应用的。
: 总的来说，算法不难，一次写好比较难。
| l***p
发帖数: 358 | 19 第一题最直接的就是递归解法，直截了当，子串不超过100，所以不用担心stack
overflow
最近在学javascript，早上写了一个
var str = "abcdefg";
var substr = ["a", "d", "g", "i", "ab", "ae", "ag", "fg", "ai", "bi", "gi",
"abc", "acd", "adf", "bcd", "abg", "aabc", "bcee", "abcdefg", "abcdefgi"];
function match(bS, dS, str, bSS, dSS, substr1)
{
if (dSS - bSS === 0) { return 0; }
else if (dS - bS >= dSS - bSS) {
for (var i = bS; i < dS; i++) {
if (str[i] === substr1[bSS]) {
return match(i + 1, dS, str, bSS + 1, dSS, substr1);
}
}
} else {
return -1;
}
}
for (var i = 0, n = substr.length; i < n; i++) {
if (-1 === match(0, str.length, str, 0, substr[i].length, substr[i])) {
console.log(substr[i] + " is X");
} else {
console.log(substr[i] + " is V");
}
} | l***p
发帖数: 358 | 20 fix a typo
function match(bS, dS, str, bSS, dSS, substr1)
{
if (dSS - bSS === 0) {
return 0;
} else if (dS - bS >= dSS - bSS) {
for (var i = bS; i < dS; i++) {
if (str[i] === substr1[bSS]) {
return match(i + 1, dS, str, bSS + 1, dSS, substr1);
}
}
}
return -1;
} | | | h****y
发帖数: 49 | 21 第二题，（假设已有100个矩形）
把所有的矩形的x1, x2排序，加上左右两个端点，一共可以把这个窗口水平分为201份。
对已有矩形的y1,y2进行相同操作，把窗口垂直分成201份。
然后只需要生成一个201x201的矩阵。每一个entry存面积，正数未被占，负数表示被占。
然后找加权的最大子矩阵，权重就是面积。
接下来要证明最优解覆盖这个最大子矩阵。。。
这个比较麻烦，大家有没有idea？
如果矩形和窗口都是用实数描述的话，可以构造出比较变态的摆放方法，我就不细想了。 | l*n
发帖数: 529 | 22 这想法很好啊，跟原始的最大和子矩阵是一样的，只不过把每一块里的数字合并了。
份。
占。
了。
【在 h****y 的大作中提到】
: 第二题，（假设已有100个矩形）
: 把所有的矩形的x1, x2排序，加上左右两个端点，一共可以把这个窗口水平分为201份。
: 对已有矩形的y1,y2进行相同操作，把窗口垂直分成201份。
: 然后只需要生成一个201x201的矩阵。每一个entry存面积，正数未被占，负数表示被占。
: 然后找加权的最大子矩阵，权重就是面积。
: 接下来要证明最优解覆盖这个最大子矩阵。。。
: 这个比较麻烦，大家有没有idea？
: 如果矩形和窗口都是用实数描述的话，可以构造出比较变态的摆放方法，我就不细想了。
| b**m
发帖数: 1466 | 23 第二道题：
S2 = ag yes
只找下一个字符不行吧。 | u*****o
发帖数: 1224 | 24 请问这个代码测试结果是对的吗？我怎么觉得不能只测bSS+1呢，比如
substr1= 'ag'的情况。第一个字母是match T中的a的，但第二个字母i+1不match bss+
1, 按照这个代码的话直接return -1了啊。。但原题ag应该是按存在算的,不应该
return -1..
不过我dfs一直都学到乱乱的，很有可以理解错了。。。
【在 l***p 的大作中提到】
: fix a typo
: function match(bS, dS, str, bSS, dSS, substr1)
: {
: if (dSS - bSS === 0) {
: return 0;
: } else if (dS - bS >= dSS - bSS) {
: for (var i = bS; i < dS; i++) {
: if (str[i] === substr1[bSS]) {
: return match(i + 1, dS, str, bSS + 1, dSS, substr1);
: }
| d*****d
发帖数: 180 | 25 第一个我得初步想法是先扫一遍T，把每个字母的位置记录下来，存到一个List array,
List [] x=List[26];
x[i]是个List, i是字母-'a'得到的0-25，List里是i代表的字母出现在T中的
所有坐标，扫描完应该是排好序的，从小到大。
然后依次在X查询Sj中每个字母，如果x[Sj-'a']存在，选最小的，但要大于前一次选的
位置，依次类推。。
for(s:S)
{
int start=-1;
boolean valid=true;
for(int j=0;j
{
int idx=s.charAt(i)-'a';
List list=x.get[idx];
if (list==null) {valid=false;break;}
int idx=getMin(list, start);
if (idx<0) {valid=false;break;}
start=idx;
}
}
---
int getMin(List list, int start)
{
int idx=-1;
// find the min>start in the list
// you can do binary search...
//O (log(list.size()))
// return -1 if no match...
return idx;
}
代码仅做参考，
可能还可以优化，比如把所有Sj做个预处理，合成一个或更少几个string,...懒得想了
。。。 |
|
