一亩三分地论坛

 找回密码
 获取更多干货,去instant注册!

扫码关注一亩三分地公众号
查看: 1868|回复: 17
收起左侧

google onsite

[复制链接] |试试Instant~ |关注本帖
bohanl 发表于 2015-2-23 08:10:39 | 显示全部楼层 |阅读模式

2015(1-3月) 码农类 硕士 全职@Google - 网上海投 - Onsite |Other

注册一亩三分地论坛,查看更多干货!

您需要 登录 才可以下载或查看,没有帐号?获取更多干货,去instant注册!

x
上周在mountain view面的

第一轮:
   1先上来问了下quicksort, 举一个worse case 时间复杂度的例子, 然后coding, 一个n的数组,没有重复, 0到n-1都在这个数组里面, 只能读,不能写(swap除外),问怎么排序,我上来就说quicksort :)然后问有没有再优化的,想了下给了个O(n)的,不到20行搞定
    2 设计题,问用什么数组实现搜索推荐,先讨论了几种方案,最后说用trie
. Waral 鍗氬鏈夋洿澶氭枃绔,
第二轮:
1给两个list A 和 B, 每个list里没有重复的,写一个方法返回3个list, 第一个是只有A里面有的,第二个是A和B都有的,第3个是只有B里面有的。 不难,20分钟边讲边说,写完了
2一个无限数组的running median, 让写一个Iterator,给了个o(n)的方法跟insertion sort,后来让优化,想了半天说用tree, 但是想不出具体该怎么做,最后要了个提示,然后根据提示把方法给他了,接着又问怎么保证Tree是平衡的,我直接蒙了,把avl忘得一干二净,他最后说你知道avl吗,我说我不记得了

第三轮:
1 一个遍设计的题,题目很长而且有图,这里不方便说,但结果用到hashtable,key是随便什么id,value是一个list, 里面存随机数组,然后每个随机数要有个timer, 过期就删除。我这里描述的是我的答案。这个题半个小时写完,就一个地方要删除过期的我忘写了(大意了),后来经过提醒补上了。
2 这时候还剩20分钟,然后最难的题来了,问了一个类似flood fill的题但是要比他难很多,题目很长这里不详细说了, 我说用dfs backtrace,面试官说可行但是有没有更好的方法,想了半天说dp,然后还没等我继续往下说,他就提示了,然后我就发现他是想让我用dp,但是提示跟我想的方法好像不太一样,然后又想,最后只说了个大概就没时间了

第四轮:
1.问garbage collection和arc的区别,各自的优点和缺点,我运气好,以前学ios programming的时候专门看了的,然后他让我用doubly linked list给他展示,随便画一画,然后问我arc有什么缺点(他是想问我memory cycle), 我但是没想到,就说我不太清楚,他说这个doubly linked list不会用cycle吗,我说如果你用weakref就不会,顿时向我投来了肯定的目光。。。也许是我yy的
2 给以个二叉搜索树和一个iterator,先问你怎么存data才能让这个树可以接受重复元素,我说存一个object,里面是Key和计数器,他说好,然后开始写代码,问题是怎么判断这个树和Iterator里面元素和计数都一样,我说用一个hashmap的counter,先去in order traverse这个数,存在map里,然后再比较iterator,最后看看这个map 的counter是否为0或者为空,他说好,写吧,这题明显是想考bst 的 in order,然后用stack写了个iterative的traverse,中间粗心犯了个小错误,stack里面Object存错了,被面试官指出然后改正,后面的很简单的code没让写,不过时间也不多了,他说你问我问题吧。。。

第五轮:. visit 1point3acres.com for more.
1给两个key/value pair的list A 和B(都是根据Key排好序的), 假设A是左边的list, B是右边的list, 根据A来join这两个list, (如果只有右边有的Key就不要存在结果里面了)。 这题很水,直接说解法,然后他笑着说简单吧,我说简单,他说简单我们就不这么写了,(难道我说难他会让我写code吗),他说现在这两个list很大,内存不够,所以给你的是两个Iterator,结果也用iterator,写next就可以了,然后我就写了一个类,然后讨论了下可能出现的问题,用了几个unit test检查后应该没什么问题,然后还剩5分钟,就让我问问题了。. 鍥磋鎴戜滑@1point 3 acres


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

. 鍥磋鎴戜滑@1point 3 acres

评分

3

查看全部评分

本帖被以下淘专辑推荐:

cynosure2 发表于 2015-2-23 08:16:49 | 显示全部楼层
强人! bless有offer!
回复 支持 反对

使用道具 举报

 楼主| bohanl 发表于 2015-2-23 08:33:16 | 显示全部楼层
cynosure2 发表于 2015-2-23 08:16
强人! bless有offer!

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

使用道具 举报

cynosure2 发表于 2015-2-23 08:55:30 | 显示全部楼层
bohanl 发表于 2015-2-23 08:33
谢谢 不过总觉得整体不难 估计要全做对才可以 希望不大

没错,google就这样,要说难不是,但要全答好也不易. 加油
回复 支持 反对

使用道具 举报

yapingchen1990 发表于 2015-2-23 10:19:48 | 显示全部楼层
觉得楼主很强
回复 支持 反对

使用道具 举报

charles901030 发表于 2015-2-23 13:29:43 | 显示全部楼层
running median用一个minHeap 和一个maxHeap做是不是会好一点?用这个方法取median的值只需要O(1)吧
回复 支持 反对

使用道具 举报

 楼主| bohanl 发表于 2015-2-23 13:37:41 | 显示全部楼层
charles901030 发表于 2015-2-23 13:29
running median用一个minHeap 和一个maxHeap做是不是会好一点?用这个方法取median的值只需要O(1)吧

对,但是要加上maintain heap的时间,应该还是log(n), 当时想到过heap,但没往深想,他还是想要bst的解法
回复 支持 反对

使用道具 举报

 楼主| bohanl 发表于 2015-2-24 07:27:09 来自手机 | 显示全部楼层
自己顶一下
回复 支持 反对

使用道具 举报

leyhzm 发表于 2015-2-24 12:00:48 | 显示全部楼层
楼主第三轮的第2题DP那道可以再说下麻~好想知道好想知道~. 1point3acres.com/bbs
还有关于第五轮,为什么用Iterator就不需要放的进内存了呢?然后因为是排好序的,就用两个指针一点点网上loop一遍就好了对吧?.鏈枃鍘熷垱鑷1point3acres璁哄潧
Tanks!!!
回复 支持 反对

使用道具 举报

leyhzm 发表于 2015-2-24 12:37:13 | 显示全部楼层
对啦,还有第五轮那个用了几个unit test检查后应该没什么问题。怎么用unit test哈?是自己想几个值,然后说给他听麻?
回复 支持 反对

使用道具 举报

 楼主| bohanl 发表于 2015-2-24 12:57:01 | 显示全部楼层
leyhzm 发表于 2015-2-24 12:00. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
楼主第三轮的第2题DP那道可以再说下麻~好想知道好想知道~
还有关于第五轮,为什么用Iterator就不需要放 ...

放进Iterator就不用返回所有结果了 对我就是这么做的
回复 支持 反对

使用道具 举报

 楼主| bohanl 发表于 2015-2-24 12:57:44 | 显示全部楼层
bohanl 发表于 2015-2-24 12:57
放进Iterator就不用返回所有结果了 对我就是这么做的

恩 就是自己给数据做测试
回复 支持 反对

使用道具 举报

sonicgu 发表于 2015-2-24 13:48:51 | 显示全部楼层
第一题O(n)我猜是给一个array,保存一下每个值都在哪个位置,然后根据位置进行swap,然后swap的时候动态更新位置array, 撸一遍就结束了
回复 支持 反对

使用道具 举报

zhiyiting 发表于 2015-2-25 14:08:15 | 显示全部楼层
楼主可以详细说下flood fill那题吗?谢谢谢谢
回复 支持 反对

使用道具 举报

samantha_kr 发表于 2015-3-5 15:16:28 | 显示全部楼层
请问LZ用C++么~
回复 支持 反对

使用道具 举报

mm豆 发表于 2015-4-25 06:14:33 | 显示全部楼层
一个无限数组的running median, 让写一个Iterator,给了个o(n)的方法跟insertion sort,后来让优化,想了半天说用tree.鐣欏璁哄潧-涓浜-涓夊垎鍦
这个题是不是求一个median 的iterator。 是不是对数组建立一个tree,每个节点保存孩子节点的个数?然后可以通过二分的方法求median?
回复 支持 反对

使用道具 举报

celtspirit 发表于 2015-4-25 12:43:20 | 显示全部楼层
请问lz,你说的iterator是指什么?
回复 支持 反对

使用道具 举报

泡妞被妞泡 发表于 2015-4-25 14:29:37 | 显示全部楼层
第一题可以用Counting Sort吧?
回复 支持 反对

使用道具 举报

本版积分规则

请点这里访问我们的新网站:一亩三分地Instant.

Instant搜索更强大,不扣积分,内容组织的更好更整洁!目前仍在beta版本,努力完善中!反馈请点这里

关闭

一亩三分地推荐上一条 /5 下一条

手机版|小黑屋|一亩三分地论坛声明 ( 沪ICP备11015994号 )

custom counter

GMT+8, 2016-12-8 01:11

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

快速回复 返回顶部 返回列表