google onsite

上周在mountain view面的

第一轮：
   1先上来问了下quicksort, 举一个worse case 时间复杂度的例子， 然后coding, 一个n的数组，没有重复， 0到n-1都在这个数组里面， 只能读，不能写（swap除外），问怎么排序，我上来就说quicksort ：）然后问有没有再优化的，想了下给了个O（n)的，不到20行搞定
    2 设计题，问用什么数组实现搜索推荐，先讨论了几种方案，最后说用trie

第二轮：
1给两个list A 和 B, 每个list里没有重复的，写一个方法返回3个list， 第一个是只有A里面有的，第二个是A和B都有的，第3个是只有B里面有的。 不难，20分钟边讲边说，写完了
2一个无限数组的running median， 让写一个Iterator，给了个o(n)的

您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

法，然后他笑着说简单吧，我说简单，他说简单我们就不这么写了，（难道我说难他会让我写code吗），他说现在这两个list很大，内存不够，所以给你的是两个Iterator，结果也用iterator，写next就可以了，然后我就写了一个类，然后讨论了下可能出现的问题，用了几个unit test检查后应该没什么问题，然后还剩5分钟，就让我问问题了。


一共问了9个题，一天下来相当累，人都很nice，除了有一轮一个面无表情的abc，但是那个flood fill的和avl树的没答上，其他还犯了两三个粗心的小错误，觉得肯定没戏了

一个无限数组的running median， 让写一个Iterator，给了个o(n)的方法跟insertion sort，后来让优化，想了半天说用tree
这个题是不是求一个median 的iterator。 是不是对数组建立一个tree，每个节点保存孩子节点的个数？然后可以通过二分的方法求median？

您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

楼主第三轮的第2题DP那道可以再说下麻～好想知道好想知道～
还有关于第五轮，为什么用Iterator就不需要放的进内存了呢？然后因为是排好序的，就用两个指针一点点网上loop一遍就好了对吧？
Tanks！！！

强人！ bless有offer!

cynosure2 发表于 2015-2-23 08:16
强人！ bless有offer!

谢谢 不过总觉得整体不难 估计要全做对才可以 希望不大

bohanl 发表于 2015-2-23 08:33
谢谢 不过总觉得整体不难 估计要全做对才可以 希望不大

没错，google就这样，要说难不是，但要全答好也不易. 加油

觉得楼主很强

running median用一个minHeap 和一个maxHeap做是不是会好一点？用这个方法取median的值只需要O(1)吧

自己顶一下

对啦，还有第五轮那个用了几个unit test检查后应该没什么问题。怎么用unit test哈？是自己想几个值，然后说给他听麻？