P*******y
发帖数: 168 | 1 一共两轮，通过LinkedIn找人内推拿到的面试。
第一轮：美国人
1. three sum，很快给了n^2的解，然后问nlogn的解，提示说用hash_map，想了一会儿
想不出来，然后就move on下一题。后来到版上问发现被忽悠了，应该不存在nlogn的解
2. 2G 大文件，RAM只有1G，怎么sort。
3. 一个image，每个pixel一个颜色。给你其中一个pixel的位置，以及一个颜色，如果
那个pixel颜色和给的一样，什么都不用做，如果不一样，就把这个pixel变成给定的颜
色，同时把他的neighbor和这个pixel原来颜色一样的也换成新的颜色，然后再
neighbor的neighbor这样下去。给了思路，没让写code，说我肯定写得出，然后就结束
了。
他家recruiter效率很高，结束后一个多小时就通知过了，安排第二轮。
第二轮昨天，一个三姐，迟到了十分钟。recruiter原来邮件里有说如果面试官十分钟
内没来，给她说一下。十分钟刚到，给recruiter发了邮件，三姐就打过来了。就开始
面了。
1. 给个时间，string格式，比如10:35，让你求时针和分针小的夹角
2. 另一种rotated array，比如 1,3,5,8,10,12,7,6,2 就是中间大，两边小，让
binary search一个数
/* 这题上面例子错了，应该是这样 1,2,3,10,9,8,7,6,5,4 就是说新的array是原来的
递增array的后面一部分反转得到的。不过上面那样也是一个很有意思的题 */
3. 找有环linked list的环的结点数，说这题之前给我说如果有做到的给她说一下，可
能前面两题写太快了，她以为我前面都做过了。其实我也没做过前面的，只是做过类似
的。这题我就给她说做过怎么确定有没有环，没有做过找环个数的，然后就让做了。说
了思路，说对的，没让写code,就接着问怎么找环的第一个结点，我说这个我做过，也
说了思路，这题就过去了。没写code
4. maximum subarray sum，leetcode原题。这题她先给了一个人的做法，问复杂度，
我看了下，说是N^3。然后问我有没有更好的方法，我就给他说了O(n)的解法，然后写
code。
这时候差不多面了半小时，三姐就不问了，让我问她问题。然后就好了。
然后一个小时后就收到recruiter的邮件说可以on site了，效率很高。
他家的题我碰到的比较传统，运气比较好，不会像网上别人的面经那种完全没思路的
面试有时候运气真的很重要。希望上面的题目对大家有帮助。 | l**b
发帖数: 457 | | f*****e
发帖数: 2992 | 3 bless.
【在 P*******y 的大作中提到】
: 一共两轮，通过LinkedIn找人内推拿到的面试。
: 第一轮：美国人
: 1. three sum，很快给了n^2的解，然后问nlogn的解，提示说用hash_map，想了一会儿
: 想不出来，然后就move on下一题。后来到版上问发现被忽悠了，应该不存在nlogn的解
: 2. 2G 大文件，RAM只有1G，怎么sort。
: 3. 一个image，每个pixel一个颜色。给你其中一个pixel的位置，以及一个颜色，如果
: 那个pixel颜色和给的一样，什么都不用做，如果不一样，就把这个pixel变成给定的颜
: 色，同时把他的neighbor和这个pixel原来颜色一样的也换成新的颜色，然后再
: neighbor的neighbor这样下去。给了思路，没让写code，说我肯定写得出，然后就结束
: 了。
| A*****i
发帖数: 3587 | | x*****0
发帖数: 452 | | p*****2
发帖数: 21240 | 6 中间大两头小但是并不是sorted呀。能用bs吗？ | p*****2
发帖数: 21240 | 7
貌似要两头一起搞了。
【在 p*****2 的大作中提到】
: 中间大两头小但是并不是sorted呀。能用bs吗？
| f*****e
发帖数: 2992 | 8 先用BS找最大的位置，然后对两边BS。
【在 p*****2 的大作中提到】
: 中间大两头小但是并不是sorted呀。能用bs吗？
| r*******6
发帖数: 99 | 9 谢谢分享。"同时把他的neighbor和这个pixel原来颜色一样的也换成新的颜色，然后再 | P*******y
发帖数: 168 | 10 是sorted,从左边到高点递增，然后再递减这样。这一题安静了想了一两分钟，给了她
方法
跟传统的rotated sorted array有点像，但是判断哪边混合的哪边单调的方法不太一样
【在 p*****2 的大作中提到】
: 中间大两头小但是并不是sorted呀。能用bs吗？
| | | P*******y
发帖数: 168 | 11 不用这样的，直接找中间，然后判断中间的右边那个是大是小就知道两边的情况了
然后就可以找其中一边BS
【在 f*****e 的大作中提到】
: 先用BS找最大的位置，然后对两边BS。
| P*******y
发帖数: 168 | 12 嗯，就是做BFS，不过要mark visit过的点
【在 r*******6 的大作中提到】
: 谢谢分享。"同时把他的neighbor和这个pixel原来颜色一样的也换成新的颜色，然后再
| l****i
发帖数: 2772 | 13 我怎么觉得不需要mark visit过的点。因为在BFS的同时，修改了点的颜色。
【在 P*******y 的大作中提到】
: 嗯，就是做BFS，不过要mark visit过的点
| j*****y
发帖数: 1071 | 14 比如是 1 2 4 0, 要搜索 0
第一次 中间的数字是 2， 这个时候怎么确定哪边搜索呢 ?
【在 P*******y 的大作中提到】
: 不用这样的，直接找中间，然后判断中间的右边那个是大是小就知道两边的情况了
: 然后就可以找其中一边BS
| l****i
发帖数: 2772 | 15 你这个没法确定选择哪一半吧。
【在 P*******y 的大作中提到】
: 不用这样的，直接找中间，然后判断中间的右边那个是大是小就知道两边的情况了
: 然后就可以找其中一边BS
| s*****1
发帖数: 134 | 16 bless~
先Binary Search找最大数，再两个单调递增或递减的binary search找那个值 | P*******y
发帖数: 168 | 17 找到2，然后看右边是4，右边比中间大，说明右边是混合的，左边是单调递增的
然后就把你的target和左边范围比较，如果在左边里，就找左边，反之，找右边
这是当时写的代码：
if(A[mid] > A[mid+1]){
if(target < A[mid] && target >= A[end])
return search(A, mid+1, end);
else
return search(A, begin, mid-1);
}else{
if(target >= A[begin] && target < A[mid])
return search(A, begin, mid-1);
else
return search(A, mid+1, end);
}
【在 j*****y 的大作中提到】
: 比如是 1 2 4 0, 要搜索 0
: 第一次 中间的数字是 2， 这个时候怎么确定哪边搜索呢 ?
| P*******y
发帖数: 168 | 18 需要的，而且mark要在入队的时候，不然会有重复入队的情况发生
因为一个点可能是好几个点的neighbor
【在 l****i 的大作中提到】
: 我怎么觉得不需要mark visit过的点。因为在BFS的同时，修改了点的颜色。
| j*****y
发帖数: 1071 | 19 用你的代码跑
-1 2 4 0, target = 0 就有问题
【在 P*******y 的大作中提到】
: 找到2，然后看右边是4，右边比中间大，说明右边是混合的，左边是单调递增的
: 然后就把你的target和左边范围比较，如果在左边里，就找左边，反之，找右边
: 这是当时写的代码：
: if(A[mid] > A[mid+1]){
: if(target < A[mid] && target >= A[end])
: return search(A, mid+1, end);
: else
: return search(A, begin, mid-1);
: }else{
: if(target >= A[begin] && target < A[mid])
| l****i
发帖数: 2772 | 20 入队之前，把点的颜色就改了，应该就不会出现重复入队了。
【在 P*******y 的大作中提到】
: 需要的，而且mark要在入队的时候，不然会有重复入队的情况发生
: 因为一个点可能是好几个点的neighbor
| | | n**m
发帖数: 122 | 21 这样有问题吧
如果target比中值小 两边都有可能。
【在 P*******y 的大作中提到】
: 不用这样的，直接找中间，然后判断中间的右边那个是大是小就知道两边的情况了
: 然后就可以找其中一边BS
| w********p
发帖数: 948 | 22 这道题cc150上有高度类似的体。
总的来说比较合理的题。
不过电面里的任何一题， bug free 的写出来都是要功夫的。
【在 P*******y 的大作中提到】
: 嗯，就是做BFS，不过要mark visit过的点
| P*******y
发帖数: 168 | 23 有道理，我上面举的例子有问题，原来题目的例子是这样子：
rotate之后： 1,2,3,10,9,8,7,6,5,4
rotate之前： 1,2,3,4,5,6,7,8,9,10
就是原来增序的后面一半反转后形成的的。这样子就可以用那个方法
【在 j*****y 的大作中提到】
: 用你的代码跑
: -1 2 4 0, target = 0 就有问题
| P*******y
发帖数: 168 | 24 嗯，这个想法不错，这样可以省去mark了
【在 l****i 的大作中提到】
: 入队之前，把点的颜色就改了，应该就不会出现重复入队了。
| l**b
发帖数: 457 | 25 这个差距好大啊。
【在 P*******y 的大作中提到】
: 有道理，我上面举的例子有问题，原来题目的例子是这样子：
: rotate之后： 1,2,3,10,9,8,7,6,5,4
: rotate之前： 1,2,3,4,5,6,7,8,9,10
: 就是原来增序的后面一半反转后形成的的。这样子就可以用那个方法
| G****A
发帖数: 4160 | 26 递增、递减两种情况，都调用同一个search()函数，搞不定吧？
找到2，然后看右边是4，右边比中间大，说明右边是混合的，左边是单调递增的
然后就把你的target和左边范围比较，如果在左边里，就找左边，反之，找右边
这是当时写的代码：
if(A[mid] > A[mid+1]){
if(target < A[mid] && target >= A[end])
return search(A, mid+1, end);
else
return search(A, begin, mid-1);
}else{
if(target >= A[begin] && target < A[mid])
return search(A, begin, mid-1);
else
return search(A, mid+1, end);
}
【在 P*******y 的大作中提到】
: 找到2，然后看右边是4，右边比中间大，说明右边是混合的，左边是单调递增的
: 然后就把你的target和左边范围比较，如果在左边里，就找左边，反之，找右边
: 这是当时写的代码：
: if(A[mid] > A[mid+1]){
: if(target < A[mid] && target >= A[end])
: return search(A, mid+1, end);
: else
: return search(A, begin, mid-1);
: }else{
: if(target >= A[begin] && target < A[mid])
| l*****a
发帖数: 14598 | 27 第二轮第二题,跟那道rotated的做法有区别吗?
我感觉是一样的
【在 P*******y 的大作中提到】
: 一共两轮，通过LinkedIn找人内推拿到的面试。
: 第一轮：美国人
: 1. three sum，很快给了n^2的解，然后问nlogn的解，提示说用hash_map，想了一会儿
: 想不出来，然后就move on下一题。后来到版上问发现被忽悠了，应该不存在nlogn的解
: 2. 2G 大文件，RAM只有1G，怎么sort。
: 3. 一个image，每个pixel一个颜色。给你其中一个pixel的位置，以及一个颜色，如果
: 那个pixel颜色和给的一样，什么都不用做，如果不一样，就把这个pixel变成给定的颜
: 色，同时把他的neighbor和这个pixel原来颜色一样的也换成新的颜色，然后再
: neighbor的neighbor这样下去。给了思路，没让写code，说我肯定写得出，然后就结束
: 了。
| l*****a
发帖数: 14598 | 28 每个子问题有两种情况
1)单调递增或递减
2)跟原问题一样
【在 G****A 的大作中提到】
: 递增、递减两种情况，都调用同一个search()函数，搞不定吧？
:
: 找到2，然后看右边是4，右边比中间大，说明右边是混合的，左边是单调递增的
: 然后就把你的target和左边范围比较，如果在左边里，就找左边，反之，找右边
: 这是当时写的代码：
: if(A[mid] > A[mid+1]){
: if(target < A[mid] && target >= A[end])
: return search(A, mid+1, end);
: else
: return search(A, begin, mid-1);
|
|
