修真四万年是一本奇书 - 未名空间MITBBS历史存档

w*92018-05-19 07:05

1 楼

1. 这里提到过的bar组成的histogram求最大内切矩形
2. 一个问题有O(N^2)和O(NlgN)两个算法，哪些情况下我们该选N平方那个。不停问还
有什么理由没有，不知道是在期待什么理由还是想听你能说出多少。
3. 给一个字符串，比如aabbbccdeaaaee, 连续的部分要求删除重复的，返回abcdeae,
还要求记录删掉了多少个。后来发现面试官希望in place做，就是没必要多开个数组来
存之类的。
4. 100*100的元素是0或1的矩阵。假如有100K个这样的矩阵的一个库, 然后给你一个矩
阵，设计个方法来回答这个矩阵是否在这个库里。
5. 好像还有一个题，大概也是查找什么东西是不是在什么集合里之类的。确实不记得
了。
6. 问了简历里的一个project怎么做的
祝大家好运！

A*e2018-05-19 07:05

2 楼

作者涉猎很广，做大烩菜是一把好手，量也足。不过最近也是进度渐渐赶上了。
还有类似的吗？

g*y2018-05-19 07:05

3 楼

羡慕啊羡慕，我就天天盼着被问histogram问题。。。

M*t2018-05-19 07:05

4 楼

这书最近两部没法看
感觉作者是搞政治工作的
絮絮叨叨啰啰嗦嗦祥林嫂一样

【在 A*******e 的大作中提到】

: 作者涉猎很广，做大烩菜是一把好手，量也足。不过最近也是进度渐渐赶上了。
: 还有类似的吗？

g*y2018-05-19 07:05

5 楼

祝楼主拿到offer！

【在 w***9 的大作中提到】

: 1. 这里提到过的bar组成的histogram求最大内切矩形
: 2. 一个问题有O(N^2)和O(NlgN)两个算法，哪些情况下我们该选N平方那个。不停问还
: 有什么理由没有，不知道是在期待什么理由还是想听你能说出多少。
: 3. 给一个字符串，比如aabbbccdeaaaee, 连续的部分要求删除重复的，返回abcdeae,
: 还要求记录删掉了多少个。后来发现面试官希望in place做，就是没必要多开个数组来
: 存之类的。
: 4. 100*100的元素是0或1的矩阵。假如有100K个这样的矩阵的一个库, 然后给你一个矩
: 阵，设计个方法来回答这个矩阵是否在这个库里。
: 5. 好像还有一个题，大概也是查找什么东西是不是在什么集合里之类的。确实不记得
: 了。

E*02018-05-19 07:05

6 楼

Thank you! Congratulations!

s*i2018-05-19 07:05

7 楼

现在google的题目变简单了

【在 w***9 的大作中提到】

: 1. 这里提到过的bar组成的histogram求最大内切矩形
: 2. 一个问题有O(N^2)和O(NlgN)两个算法，哪些情况下我们该选N平方那个。不停问还
: 有什么理由没有，不知道是在期待什么理由还是想听你能说出多少。
: 3. 给一个字符串，比如aabbbccdeaaaee, 连续的部分要求删除重复的，返回abcdeae,
: 还要求记录删掉了多少个。后来发现面试官希望in place做，就是没必要多开个数组来
: 存之类的。
: 4. 100*100的元素是0或1的矩阵。假如有100K个这样的矩阵的一个库, 然后给你一个矩
: 阵，设计个方法来回答这个矩阵是否在这个库里。
: 5. 好像还有一个题，大概也是查找什么东西是不是在什么集合里之类的。确实不记得
: 了。

g*y2018-05-19 07:05

8 楼

会不会是面phd的题目难些，面master的题目简单些？

【在 s*****i 的大作中提到】

: 现在google的题目变简单了

P*e2018-05-19 07:05

9 楼

I guess not.
intern easier, fulltime more difficult?

【在 g*******y 的大作中提到】

: 会不会是面phd的题目难些，面master的题目简单些？

w*92018-05-19 07:05

10 楼

可惜我没好好看以前的帖子啊，被问到时只是记起这里讨论过而已。。所以回答得应该
很不理想。
哪个帖子是最好的解决方法啊，我去看看，就当学习了。

【在 g*******y 的大作中提到】

: 羡慕啊羡慕，我就天天盼着被问histogram问题。。。

H*M2018-05-19 07:05

11 楼

i dont think the histogram problem is a simple one, even for onsite..

【在 s*****i 的大作中提到】

: 现在google的题目变简单了

w*92018-05-19 07:05

12 楼

非常惨的是其中一个面试官说着完美纯正的我完全听不懂的印度英语，每道题我都叫他
重复了不知多少次，整个交流过程非常差，我估计必然要挂在他那里。
我现在只希望以后的面试宁愿题难一点儿都行，可千万别在碰到这种情况了，太郁闷了。

【在 g*******y 的大作中提到】

: 祝楼主拿到offer！

s*i2018-05-19 07:05

13 楼

没看过确实不容易。不过这个是经典的题，就算写不出完整的code，能把idea说出来就
可以了啊，这不是电面嘛

【在 H*M 的大作中提到】

: i dont think the histogram problem is a simple one, even for onsite..

S*n2018-05-19 07:05

14 楼

4. 100*100的元素是0或1的矩阵。假如有100K个这样的矩阵的一个库, 然后给你一个矩
阵，设计个方法来回答这个矩阵是否在这个库里。
这个大家有没有什么好的解法？

s*i2018-05-19 07:05

15 楼

预处理100K个矩阵，记录每个矩阵0和1的个数，用这个签名作为key保存在hashmap里面
然后找出与要查找的矩阵签名相同的，然后挨个比。因为都是0和1，用XOR应该比较快

【在 S******n 的大作中提到】

: 4. 100*100的元素是0或1的矩阵。假如有100K个这样的矩阵的一个库, 然后给你一个矩
: 阵，设计个方法来回答这个矩阵是否在这个库里。
: 这个大家有没有什么好的解法？

S*n2018-05-19 07:05

16 楼

谢谢

【在 s*****i 的大作中提到】

: 预处理100K个矩阵，记录每个矩阵0和1的个数，用这个签名作为key保存在hashmap里面
: 然后找出与要查找的矩阵签名相同的，然后挨个比。因为都是0和1，用XOR应该比较快

d*e2018-05-19 07:05

17 楼

有关于这个问题的解法吗，我没能找到以前这个问题的讨论？Thx.

【在 H*M 的大作中提到】

: i dont think the histogram problem is a simple one, even for onsite..

d*a2018-05-19 07:05

18 楼

4.
这个题怎么做？我想到的就是用个trie。

【在 w***9 的大作中提到】

: 1. 这里提到过的bar组成的histogram求最大内切矩形
: 2. 一个问题有O(N^2)和O(NlgN)两个算法，哪些情况下我们该选N平方那个。不停问还
: 有什么理由没有，不知道是在期待什么理由还是想听你能说出多少。
: 3. 给一个字符串，比如aabbbccdeaaaee, 连续的部分要求删除重复的，返回abcdeae,
: 还要求记录删掉了多少个。后来发现面试官希望in place做，就是没必要多开个数组来
: 存之类的。
: 4. 100*100的元素是0或1的矩阵。假如有100K个这样的矩阵的一个库, 然后给你一个矩
: 阵，设计个方法来回答这个矩阵是否在这个库里。
: 5. 好像还有一个题，大概也是查找什么东西是不是在什么集合里之类的。确实不记得
: 了。

r*m2018-05-19 07:05

19 楼

请问你这是一次电面吗，45分钟咋做这么多啊，要coding不？

【在 w***9 的大作中提到】

: 1. 这里提到过的bar组成的histogram求最大内切矩形
: 2. 一个问题有O(N^2)和O(NlgN)两个算法，哪些情况下我们该选N平方那个。不停问还
: 有什么理由没有，不知道是在期待什么理由还是想听你能说出多少。
: 3. 给一个字符串，比如aabbbccdeaaaee, 连续的部分要求删除重复的，返回abcdeae,
: 还要求记录删掉了多少个。后来发现面试官希望in place做，就是没必要多开个数组来
: 存之类的。
: 4. 100*100的元素是0或1的矩阵。假如有100K个这样的矩阵的一个库, 然后给你一个矩
: 阵，设计个方法来回答这个矩阵是否在这个库里。
: 5. 好像还有一个题，大概也是查找什么东西是不是在什么集合里之类的。确实不记得
: 了。

b*g2018-05-19 07:05

20 楼

多谢分享。祝愿早日拿到这个offer。

P*l2018-05-19 07:05

21 楼

histogram code:
package myTest;
import static org.apache.commons.lang.StringUtils.join;
public class DP_blackBlock {
int[][] matrix;
void readMatrix(String[] mtx) {
int n = mtx.length;
String[] s = mtx[0].split("[ ]+");
int m = s.length;
matrix = new int[m][];
for (int i = 0; i < m; i++) {
s = mtx[i].split("[ ]+");
matrix[i] = new int[n];
for (int j = 0; j < n; j++) {
matrix[i][j] = Integer.valueO

h*k2018-05-19 07:05

22 楼

改进一下，用整个矩阵的1的个数作key，重复率可能比较高，
可以用矩阵中每个row和column中的1的个数的集来做key。

【在 s*****i 的大作中提到】

: 预处理100K个矩阵，记录每个矩阵0和1的个数，用这个签名作为key保存在hashmap里面
: 然后找出与要查找的矩阵签名相同的，然后挨个比。因为都是0和1，用XOR应该比较快