推荐:数据科学课程和书籍清单以及培训讲座


一亩三分地论坛

 找回密码
 获取更多干活,快来注册

一亩三分地官方iOS手机应用下载
查看: 8824|回复: 28
收起左侧

Google Onsite 附面试准备

  [复制链接] |试试Instant~ |关注本帖
xujun 发表于 2015-9-30 05:24:37 | 显示全部楼层 |阅读模式

2015(7-9月) 码农类 硕士 全职@Google - 网上海投 - Onsite |Otherfresh grad应届毕业生

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

您需要 登录 才可以下载或查看,没有帐号?获取更多干活,快来注册

x
(1) 中年白人: 先在手机上演示了一个game, 就是一个球从起点开始沿着通道,看能不能滚到终点。不过有限制, 每次球一走到底要不到边界,要不到障碍物,中间不能停留。 可以上下左右走,然后让写个function 给定起点, 终点,和图,判断是不是solvable. 写出来了, 就是用BFS,有个小bug被指出。然后问复杂度, 问如何优化。
(2) 韩国人: (a) 给一个dictionary, 再给一个set of coding string (g5, goo3,goog2, go2le.........). return all string from dictionary that can be matched with the coding string. 要求尽量减少dictionary look up 次数。给了个方法,但一直不满意复杂度。
                     (b)如何用Trie,   把问题(a)解决,要求写code 建一个Trie包括所有字典词和coding string.不是很明白。。。凭感觉写了个。.鏈枃鍘熷垱鑷1point3acres璁哄潧
(3) 阿三, 非常拽。。。 给一个dictionary, 一个string,找出dict 里能全部用string里的letter 表示的所有最长的词。给了算法,死活不满意,不让我写code. 估计被黑了。
  (4) 阿三。 design google calendar .  要求分析如何存data, 如何invoke user events, 如何handle 100000events per second, 然后要写了一部分thread safe 的code 实现如何invoke event.. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
  (5)   年轻白人: (a)leetcode 上的coin 题, 用DP. (b)给你一个password 假定6位, 有个function 每call 一次就给你一个triplet 是password 里的随即三位,order不变。比如google, 可能返回, ggl, goe, oog, ool, ........问如何最有效破译这个密码,写code. . 1point 3acres 璁哄潧
. From 1point 3acres bbs
. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
============
如何准备
============
1. 书籍:
B1. Introduction to Algorithms
B2. Algorithms (4th Edition) by Robert Sedgewick and Kevin Wayne
B3. Cracking the Coding Interview

B4. Programming Pearls

. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
2. 在线资源
MITBBS
LEETCODE
TOPCODER

careercup.1point3acres缃

3. Design. visit 1point3acres.com for more.
总结贴:
http://blog.csdn.net/sigh1988/article/details/9790337
其它资源:
http://www.mitbbs.com/article_t/JobHunting/32498535.html
https://www.facebook.com/note.php?note_id=365915113919
https://www.facebook.com/video/video.php?v=432864835468
https://www.facebook.com/photo.php?v=572283147938&set=vb.9445547199&type=3&permPage=1

http://vimeo.com/11280885


必看论文:. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
Google: Google File System, MapReduce, BigTable. from: 1point3acres.com/bbs
Facebook: Cassandra
Amazon: Dynamo
. Waral 鍗氬鏈夋洿澶氭枃绔,
其实读懂这5篇论文后,很多系统设计题就应该大概明白怎么做了,因为很多重要的设计思想都在这些论文中。.1point3acres缃
. 鍥磋鎴戜滑@1point 3 acres

评分

4

查看全部评分

本帖被以下淘专辑推荐:

stellari 发表于 2015-10-3 15:56:50 | 显示全部楼层
关注一亩三分地公众号:
Warald_一亩三分地
5-b感觉有硬伤啊。如果密码就是:aaaaaa的话,严格来讲,我永远也不可能以100%的置信度破译这个密码。因为每次返回的都是aaa,比如经过100次都是这样,那我怎么知道是因为密码是全“a”,还是因为虽然密码不是全a,但是我就是运气差(hao),每次都返回的正好都是a呢?比如密码是"aaaaab"的话,100次里不出现b的概率基本可以小到忽略不计,但是3次内不出现还是很有可能的。所以我们总得制定一个标准K,即K次内还没出现过的字母就认为不存在于这个密码当中了。不知面试官有没有提这方面的内容?.鐣欏璁哄潧-涓浜-涓夊垎鍦

或者这道题有其他的限制条件?
回复 支持 2 反对 0

使用道具 举报

kelvinzhong 发表于 2015-9-30 07:10:40 | 显示全部楼层
关注一亩三分地微博:
Warald
这。。第四题第二问怎么做?? 好难。。
回复 支持 反对

使用道具 举报

M_Jason 发表于 2015-9-30 07:38:46 | 显示全部楼层
楼主onsite的题不简单啊!!楼主都答上来了?
回复 支持 反对

使用道具 举报

小小平民 发表于 2015-9-30 08:12:08 | 显示全部楼层
thread safe 的code是咋写的啊?楼主用的是什么语言啊?
回复 支持 反对

使用道具 举报

danchou 发表于 2015-9-30 08:24:46 | 显示全部楼层
楼主去哪里onsite的?好难!
回复 支持 反对

使用道具 举报

宝贝忆彼岸 发表于 2015-9-30 08:29:55 | 显示全部楼层
同求第四题思路,感觉楼主好牛!!
回复 支持 反对

使用道具 举报

guzi 发表于 2015-9-30 11:17:35 | 显示全部楼层
谢谢楼主分享,希望早上拿到dream offer!

第三题, 楼主给的是什么算法呢?面试官期望的是什么呢?
第四题,能具体讲一下你的思路和面试官讨论的过程么?
第五题,(1)搜了一下leetcode上题目没有包含coin的。是 given n coins, compute the number of combination if the type of coin are {1,2,5,10}? (2)是topology sort的思路么?



补充内容 (2015-9-30 11:45):
是这个coin in line? http://articles.leetcode.com/2011/02/coins-in-line.html
回复 支持 反对

使用道具 举报

say543 发表于 2015-10-3 04:59:26 | 显示全部楼层
分享一下想法 和问题 欢迎讨论
question 1:
我会用DFS 每一个node 可以mark 4个directions(因为要block or not way 才能change direction) 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
tim compleixty is o(4nm). 1point3acres.com/bbs

queiton 2:
我一开始就是想到tries 假g5a(assuming input is only alphabet), 会转成g#####a. # 可以match any character. 用所有的strings 建tries 然后dictionary 扫一遍不知道有没有理解错?
question 3:
我会用两个hashMap. the first is for target string and the second is reused for each string in dictionary. 这感觉面试官要更好的算法?

question 4:
一个
main thread 接受register event 一个thread(synchonized) 平时sleep 会被main threa 叫起来纪录event 不知道考点是data structure 还是?
. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
questino 5-1:
找不到leetcode coin 的题目 LZ 能说说吗?

question 5-2
是用猜数子的brute force 解法吗?
回复 支持 反对

使用道具 举报

hulahu 发表于 2015-10-3 14:57:57 | 显示全部楼层
楼主, 阿三, 非常拽==》可能负责stress interview..
回复 支持 反对

使用道具 举报

mileschen2008 发表于 2015-10-4 10:51:00 | 显示全部楼层
5(b)也太变态了点,感觉无从下手啊。
回复 支持 反对

使用道具 举报

ww55201 发表于 2015-10-5 12:05:10 | 显示全部楼层
感觉楼主大牛,题都好难,楼主能说下解题思路不?
回复 支持 反对

使用道具 举报

tomdarling 发表于 2015-10-7 20:55:08 | 显示全部楼层
请问楼主是在哪里onsite的呢
回复 支持 反对

使用道具 举报

wenqiang88 发表于 2015-10-7 21:45:03 | 显示全部楼层
say543 发表于 2015-10-3 04:59. Waral 鍗氬鏈夋洿澶氭枃绔,
分享一下想法 和问题 欢迎讨论
question 1:
我会用DFS 每一个node 可以mark 4个directions(因为要block o ...

感觉第二题应该是建一个带数字的trie,这样比按所有情况建trie要更有效率
回复 支持 反对

使用道具 举报

nothingtrouble 发表于 2015-10-7 22:35:13 | 显示全部楼层
guzi 发表于 2015-9-30 11:17
谢谢楼主分享,希望早上拿到dream offer!.鏈枃鍘熷垱鑷1point3acres璁哄潧

第三题, 楼主给的是什么算法呢?面试官期望的是什么呢?

猜lz说的是lintcode,有一系列的coin的题目
回复 支持 反对

使用道具 举报

宝贝忆彼岸 发表于 2015-10-7 22:44:45 | 显示全部楼层
最后一题最后一问lz有没有什么好方法,不知道带有重复字符的toplogical sort应该怎么做。。。。。求大神解答!
回复 支持 反对

使用道具 举报

nothingtrouble 发表于 2015-10-8 01:29:50 | 显示全部楼层
请问lz, 第三问, 拽阿三的那个题是什么意思?string的letter,比如google就是{g,o,l,e}吗?要不要考虑每个letter的count?
回复 支持 反对

使用道具 举报

say543 发表于 2015-10-8 13:10:39 | 显示全部楼层
wenqiang88 发表于 2015-10-7 21:45
感觉第二题应该是建一个带数字的trie,这样比按所有情况建trie要更有效率

能说说带数字的tries 怎么做吗? 交流交流
回复 支持 反对

使用道具 举报

wenqiang88 发表于 2015-10-8 19:26:08 | 显示全部楼层
say543 发表于 2015-10-8 13:10. more info on 1point3acres.com
能说说带数字的tries 怎么做吗? 交流交流

可以在a-z后加入数字节点,表示要匹配多少个字母。然后到时候直接从target string里减掉这么多字母
回复 支持 反对

使用道具 举报

aiweiwei 发表于 2015-10-8 22:06:48 | 显示全部楼层
请问楼主电面多久后收到on site的通知的
回复 支持 反对

使用道具 举报

本版积分规则

关闭

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

手机版|小黑屋|一亩三分地论坛声明

custom counter

GMT+8, 2017-7-26 08:52

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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