G家onsite面经

G家的面试果然不简单啊

茕茕梦 发表于 2015-2-28 11:38
好曲折。。。原来G还有这样的项目，其实要是12月毕业的话第一年不办H1B也还好，STEM29个月之后还能有两次抽 ...

同学你给结果了吗？ 我有个朋友上周三面的，今天刚拿到

楼主的经历好牛逼，我也想试试啊。

楼主遇到题确实难啊。第一题想到几个问题，楼主提到merge sort有没有提是外排？另外数很多，bst是不是最终也得存在外存上？steam的数能重复吗？如果重复能压缩到一个节点上吗，或者bst允许重复值吗？

哈哈 我也遇到过一个条件很多的图论题 刚面完都记不得是什么了 不过是三哥的题

qjx026 发表于 2015-3-5 13:18
同学你给结果了吗？ 我有个朋友上周三面的，今天刚拿到

还没消息呐 听hr说一般要两周左右

blaze 发表于 2015-3-5 14:18
哈哈 我也遇到过一个条件很多的图论题 刚面完都记不得是什么了 不过是三哥的题

是太平洋和大西洋那个题么？g家图论题里面貌似这道很热门

refurbish 发表于 2015-3-5 13:31
楼主遇到题确实难啊。第一题想到几个问题，楼主提到merge sort有没有提是外排？另外数很多，bst是不是最终 ...

我说的merge 的意思是不断建小bst，然后小的bst可以很容易merge成大bst哈，你后面问的问题我没跟老印问，他说不给任何额外空间，后来他自己在白板上鼓捣了一会，看他意思是想让我推导出一个树的中序遍历结果中根和孩子的index关系，类似于heap那样的，可是我太挫，没弄出来

sonicgu 发表于 2015-3-6 02:36
我说的merge 的意思是不断建小bst，然后小的bst可以很容易merge成大bst哈，你后面问的问题我没跟老印问， ...

题目要求什么时候要构造一个balanced binary search tree？是在stream中间的任何一个时刻可以call这个方法返回一个tree，还是整个stream结束了返回一个tree。stream的一个假设就是数据不能完全放入内存。老印提示的中序遍历，那是标准的根据排序数组构造一个BST的方法，时间复杂度是O(n)，而且必然是balanced，但是这样就太简单了，而且和之前sorting stream也没啥关系。