O*******g
发帖数: 1 | 1 1. Binary Search Tree, right next() function on each node
还有一个follow up question想不起来了
2. Leetcode , merge interval 变种
find mean in two sorted list with same length
一个Design问题
3. 基本都是design的问题，design google recommendation
4. 设计/测试replicate cache的方法
5. 一个martrix，每行每列都是sorted，找到前kth 个
前四轮感觉都还可以，最后一轮是烙印，比较疲惫了，老觉得有一个什么最优解，后来
查了一下基本就是merge multiple sorted list的思路，做题的时候钻了牛角尖，老觉
得还有一个更好的解法。
一周后接到电话或是hc没过，问了一下有什么需要improve的，没有正面回答，就是鼓
励以后再去试试。
郁闷，move on了。 |
l*****n
发帖数: 246 | |
w****a
发帖数: 710 | 3 谢面经
第五题我记得确实有个牛算法，但是那个面试一般不要求吧 |
t**r
发帖数: 3428 | |
h*******0
发帖数: 270 | |
n**********6
发帖数: 81 | 6 我昨天收到电话悲剧了。不解释的。唯一的原因 我研究了。hc 有通过率感觉。就是表
现得是top的。不然自我感觉良好 也没用。 |
h******1
发帖数: 20 | 7 感谢楼主分享，继续加油祝好运！刚听说我一个师兄最近的经历 （不是G家）：面试几
轮题都做对了，而且是面试官肯定了是最优解 没有bug，做的也并不慢，每轮大概2，3
题的节奏我觉得应该是合理速度啊，结果当天就被拒，理由是：有一道题做的可以much
faster，不够creative和太detail oriented。听说了以后顿时觉得面试真心不易啊，
题都做对本身就已经不容易了，如何才能避免给人留下这样的印象似乎更难捉摸啊。还
有从另一方面说，每轮面试就那么短短几十分钟，怎么就能轻易得出这样的结论呢，别
的不敢说 在我看来至少我这师兄是个特别creative的人。。。 |
l*****n
发帖数: 246 | |
u*a
发帖数: 247 | 9 有可能是
1、communication的问题，这个你需要找个人mock一下
2、做题太慢
3、Design没有答到点子上
4、你现在level很高，但表现一般，HC觉得没法按照你现在level雇你
5、被阴了
【在 O*******g 的大作中提到】
: 1. Binary Search Tree, right next() function on each node
: 还有一个follow up question想不起来了
: 2. Leetcode , merge interval 变种
: find mean in two sorted list with same length
: 一个Design问题
: 3. 基本都是design的问题，design google recommendation
: 4. 设计/测试replicate cache的方法
: 5. 一个martrix，每行每列都是sorted，找到前kth 个
: 前四轮感觉都还可以，最后一轮是烙印，比较疲惫了，老觉得有一个什么最优解，后来
: 查了一下基本就是merge multiple sorted list的思路，做题的时候钻了牛角尖，老觉
|
s********l
发帖数: 998 | |
|
|
s********l
发帖数: 998 | 11 哪个巨牛的方法啊？
【在 w****a 的大作中提到】
: 谢面经
: 第五题我记得确实有个牛算法，但是那个面试一般不要求吧
|
b******g
发帖数: 77 | 12 一个martrix，每行每列都是sorted，找到前kth 个
Analysis:
Applying a quick-select algorithm will achieve an O( n * n ) time
complexity. Can we do better? Yes. Here is a algorithm:
1. Like quick-select algorithm, this algorithm applies divide-and-
conquer.
2. Initialize those two boundary lines to (n * [0] and n * [n]) to
include all array items in boundary.
3. Process subarray between boundary lines (lo, hi ) in each
recursive call:
a. select a random item in subarray and use it as pivot.
b. draw a new boundary line (lt) to separate item < pivot
and item >= pivot. Find the number of items < pivot (nLt)
c. draw a new boundary line (gt) to separate item <= pivot
and item > pivot. Find the number of items > pivot(nGt)
d. if k < nLt, recursively process subarray between
boundary (lo, lt)
e. if k >= nGt, recursively process subarray between
boundary (gt, hi)
d. else return pivot value
Step a, b, c, all takes O( n ) time. So the entire algorithm takes
O( n log(n ) )
class Solution
{
public:
int select( const vector >& arr, int k ) const
{
srand( time( 0 ) );
if( arr.empty() || arr[0].empty() || k < 0 || k >= arr.size() * arr[
0].size() )
throw "No solution";
vector vctLo( arr.size(), 0 );
vector vctHi( arr.size(), arr[0].size() );
return select( arr, k, vctLo, 0, vctHi, arr.size() * arr[0].size() );
}
private:
int select( const vector >& arr, int k, const vector&
vctLo,
int nLo, vector& vctHi, int nHi ) const
{
// Get a random item between lower and upper bound lines
int nPivot = getPivot( arr, vctLo, nLo, vctHi, nHi );
// 3-way Partition
vector vctLt = vctHi, vctGt = vctHi;
// nLt: number of item < pivot, nGt: number of item > pivot
int nLt = 0, nGt = 0;
for( int x=0; x
{
if( x > 0 )
{
vctLt[x] = vctLt[x-1];
vctGt[x] = vctGt[x-1];
}
while( vctLt[x] > vctLo[x] && arr[x][vctLt[x]-1] >= nPivot ) --
vctLt[x];
while( vctGt[x] > vctLo[x] && arr[x][vctGt[x]-1] > nPivot ) --
vctGt[x];
nLt += vctLt[x];
nGt += vctGt[x];
}
if( k < nLt ) return select( arr, k, vctLo, nLo, vctLt, nLt );
if( k >= nGt ) return select( arr, k, vctGt, nGt, vctHi, nHi );
return nPivot;
}
int getPivot( const vector >& arr, const vector& vctLo,
int nLo,
const vector& vctHi, int nHi ) const
{
int x = 0;
while( vctLo[x] == vctHi[x] ) ++x;
int nIndex = rand() % (nHi - nLo);
while( nIndex >= vctHi[x] - vctLo[x] )
{
nIndex -= vctHi[x] - vctLo[x];
++x;
}
return arr[x][vctLo[x]+nIndex];
}
}; |
a***e
发帖数: 413 | 13 5这个题CC150上面有类似的，是找某个元素。 |
r****7
发帖数: 2282 | 14 nlog(n)的话直接K路归并就行了。。。
to
【在 b******g 的大作中提到】
: 一个martrix，每行每列都是sorted，找到前kth 个
: Analysis:
: Applying a quick-select algorithm will achieve an O( n * n ) time
: complexity. Can we do better? Yes. Here is a algorithm:
: 1. Like quick-select algorithm, this algorithm applies divide-and-
: conquer.
: 2. Initialize those two boundary lines to (n * [0] and n * [n]) to
: include all array items in boundary.
: 3. Process subarray between boundary lines (lo, hi ) in each
: recursive call:
|
c*******y
发帖数: 570 | |
b******g
发帖数: 77 | 16 k-merge is O( n * n * log( n ) ), if k = (n/2)
【在 r****7 的大作中提到】
: nlog(n)的话直接K路归并就行了。。。
:
: to
|
c**********e
发帖数: 58 | 17 Solution of the 5th problem:
http://www.geeksforgeeks.org/kth-smallest-element-in-a-row-wise
【在 r****7 的大作中提到】
: nlog(n)的话直接K路归并就行了。。。
:
: to
|
c**********e
发帖数: 58 | 18 http://www.geeksforgeeks.org/kth-smallest-element-in-a-row-wise
【在 b******g 的大作中提到】
: k-merge is O( n * n * log( n ) ), if k = (n/2)
|
e***a
发帖数: 1661 | 19 cud u give details for 设计/测试replicate cache的方法? |
n******n
发帖数: 12088 | 20 merge sorted list只用到了行排序，没有列排序
【在 O*******g 的大作中提到】
: 1. Binary Search Tree, right next() function on each node
: 还有一个follow up question想不起来了
: 2. Leetcode , merge interval 变种
: find mean in two sorted list with same length
: 一个Design问题
: 3. 基本都是design的问题，design google recommendation
: 4. 设计/测试replicate cache的方法
: 5. 一个martrix，每行每列都是sorted，找到前kth 个
: 前四轮感觉都还可以，最后一轮是烙印，比较疲惫了，老觉得有一个什么最优解，后来
: 查了一下基本就是merge multiple sorted list的思路，做题的时候钻了牛角尖，老觉
|
|
|
j*****d
发帖数: 1625 | 21 没什么好奇怪的吧。面得好的，见了CTO的，都最后可能没offer。 |
h*******i
发帖数: 211 | 22 G拒人都不怎么解释的
就是内部有人帮问也问不出来，HR会说为了protect privacy
除非你里边有朋友认识面试你的人 面试你的人可以看到其他所有面试官的feedback |
j****1
发帖数: 99 | 23 ye...+1...
【在 j*****d 的大作中提到】
: 没什么好奇怪的吧。面得好的，见了CTO的，都最后可能没offer。
|
