PoketGem 电面

原帖地址:一亩三分地

练手公司,背景什么的完全不符。本想着给onsite的话就推了,结果2面的时候把我拒了呵呵

一面:native speaker
1, strstr
我说我写个KMP吧(反正是练手,好久没写了看看还能写出来不),非让我写个naive的。
2, 求 top k
写了个quick select算法。问复杂度说是average O(n), worst case O(n^2)。
我说用median of medians可以保证worst case时候O(n),那哥们好像没听说过。

二面:native speaker
先问问什么pocket gem,由于完全没准备他们家背景,所以瞎扯。
我说我以前玩过你们家的一个游戏,挺好玩,名字就叫 ‘pocket gem’ (老婆给我说的)。
结果这哥们说我在这呆了4年都不知道有这么个游戏。
然后解释名字记错了,但是是一个貌似连连看的游戏,结果被告知他们家没有这样的游戏。。。
事后证明老婆记错了。。那个游戏是宝石工厂,不是他们家的。。。
然后在这种诡异气氛下就开始做题了
1,sort color, 要求O(n)时间,常数空间
. From 1point 3acres bbs个人觉得那个3个指针one pass的做法有点tricky,不好装是现想出来的。
所以用两次partition来做。
结果这哥们没听过partition,解释了半天quicksort 中的 partition什么的都不懂。
然后就先开写,但他看不懂我写的。。。
后来在各种演示下终于将信将疑的move到下一题了
2, 有parent指针的BST,找next larger元素。
没啥好说的,解释了几种情况后3分钟搞定。

======
估计挂在culture问题或partition上了。
练手也算得到了一个不错的经验,以后还是用最常见的写法来写,免得看不懂。