w******a
发帖数: 236 | 1 今天下午和LinkedIn的一个老美电面了一下，一个小时只做了一道题。自己发挥的不好
，就move on吧。题目其实很简单，在一个2D的，行sorted，列sorted，另外前一行的
最后一个数小于下一行第一个数的整数数组中，寻找target数是否存在。举例：
1 3 5 7
8 10 12 16
20 14 28 40
一开始我说了O(n)的解法，就是从右上角的元素开始，根据当前元素和target比较的大
小，决定向下还是向左移动，直到最后一行和最左一列。leetcode的网站上有的。后来
又问如果是row=1或者col=1怎么办。回答说那就普通binary search。再问那考虑通用
情况，如何改进。这时候我反应过来，应该对这个二维数组从middle element开始，直
接进行binary search。复杂度为O(lg(M+N))。对方表示满意。
接下来开始写程序。这时候突然开始愚钝，死活没写对怎么计算middle element当前的
row和col的值。后来时间耗得差不多了，突然反应过来应该用个小的helper function
去做1D index到2D index的转换。但是已经没有时间写完了，只好就是描述了一下，在
collabedit上尽量写下自己的思路。
只剩5分钟了，他问了一个data mining的题目，好像是一个著名的filter的定义。我说
我虽然是做了data mining，但是本行不是这个，所以没有听说过这个。但是我做了类
似的东西，快速解释了一下。最后问了他，在对LinkedIn Today模块的数据进行处理时
，如何解决同一个story前后不同版本的de-duplication问题。他谈了谈大概，就结束
了。
最后他祝我Good Luck。估计没戏了。我觉得自己确实不是码农的料，可是为了生计，
目前就是只能做这个。换个工作也这么难，感觉有些郁闷。但是还是要打起精神，总结
经验教训，继续努力吧。
希望对后来人的准备有帮助。 |
d******u
发帖数: 397 | |
l***i
发帖数: 1309 | 3 I don't think you can do log(M+N), after you throw away one quarter, the
remaining ones are no longer a square and it gets tricky |
w****x
发帖数: 2483 | 4 二分嘛, 版上有, linkedin怎么又用这道题 |
l*****a
发帖数: 14598 | 5 估计笔误，O(lg(M*N)) or O(lgM+lgN)
【在 l***i 的大作中提到】
: I don't think you can do log(M+N), after you throw away one quarter, the
: remaining ones are no longer a square and it gets tricky
|
l*****a
发帖数: 14598 | 6 要有信心，不是也在大公司骑驴找马吗？
我今天还学习了你当年的FB面经呢
hoho
【在 w******a 的大作中提到】
: 今天下午和LinkedIn的一个老美电面了一下，一个小时只做了一道题。自己发挥的不好
: ，就move on吧。题目其实很简单，在一个2D的，行sorted，列sorted，另外前一行的
: 最后一个数小于下一行第一个数的整数数组中，寻找target数是否存在。举例：
: 1 3 5 7
: 8 10 12 16
: 20 14 28 40
: 一开始我说了O(n)的解法，就是从右上角的元素开始，根据当前元素和target比较的大
: 小，决定向下还是向左移动，直到最后一行和最左一列。leetcode的网站上有的。后来
: 又问如果是row=1或者col=1怎么办。回答说那就普通binary search。再问那考虑通用
: 情况，如何改进。这时候我反应过来，应该对这个二维数组从middle element开始，直
|
h****e
发帖数: 928 | 7 这道题的复杂度应该是O(log(M*N))，也就是O(logM+logN)。转化成
一维数组大概是最简单的解法了。下面是Java写的解法：
public boolean searchMatrix(int[][] matrix, int target) {
int m = matrix.length;
if (m==0) {
return false;
}
int n = matrix[0].length;
if (n==0) {
return false;
}
int i=0;
int j=m*n-1;
while (i<=j) {
int mid = i+(j-i)/2;
int row = mid/n;
int col = mid%n;
int v = matrix[row][col];
if (v==target) {
return true;
}
if (v>target) {
j = mid-1;
} else {
i = mid+1;
}
}
return false;
} |
w******a
发帖数: 236 | 8 不好意思，确实是笔误，应该是O(M*N)。
【在 l*****a 的大作中提到】
: 估计笔误，O(lg(M*N)) or O(lgM+lgN)
|
v****c
发帖数: 29 | 9 。。。
O(log(M*N))和O(log(M+N))有什么区别？
【在 w******a 的大作中提到】
: 不好意思，确实是笔误，应该是O(M*N)。
|
y**********u
发帖数: 6366 | 10 字符串不一样
【在 v****c 的大作中提到】
: 。。。
: O(log(M*N))和O(log(M+N))有什么区别？
|
w******a
发帖数: 236 | 11 今天脑子木得很，进水了，居然再次笔误！！！复杂度应该是O(lg(M*N))。 |
i****s
发帖数: 1152 | |
b******i
发帖数: 914 | 13 本人愚钝，为什么这个可以work？
直接转化为一维数组以后，得到的一维数组并不是排好序的啊，为什么能直接二分搜索
呢？
【在 h****e 的大作中提到】
: 这道题的复杂度应该是O(log(M*N))，也就是O(logM+logN)。转化成
: 一维数组大概是最简单的解法了。下面是Java写的解法：
: public boolean searchMatrix(int[][] matrix, int target) {
: int m = matrix.length;
: if (m==0) {
: return false;
: }
: int n = matrix[0].length;
: if (n==0) {
: return false;
|
b******i
发帖数: 914 | 14 哦 原来前一行的最后一个数小于后一行的第一个，有这个条件
【在 b******i 的大作中提到】
: 本人愚钝，为什么这个可以work？
: 直接转化为一维数组以后，得到的一维数组并不是排好序的啊，为什么能直接二分搜索
: 呢？
|
