一亩三分地论坛

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

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

Google Onsite 附面试准备

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

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

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

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

x
(1) 中年白人: 先在手机上演示了一个game, 就是一个球从起点开始沿着通道,看能不能滚到终点。不过有限制, 每次球一走到底要不到边界,要不到障碍物,中间不能停留。 可以上下左右走,然后让写个function 给定起点, 终点,和图,判断是不是solvable. 写出来了, 就是用BFS,有个小bug被指出。然后问复杂度, 问如何优化。. visit 1point3acres.com for more.
(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.不是很明白。。。凭感觉写了个。. 1point 3acres 璁哄潧
(3) 阿三, 非常拽。。。 给一个dictionary, 一个string,找出dict 里能全部用string里的letter 表示的所有最长的词。给了算法,死活不满意,不让我写code. 估计被黑了。. From 1point 3acres bbs
  (4) 阿三。 design google calendar .  要求分析如何存data, 如何invoke user events, 如何handle 100000events per second, 然后要写了一部分thread safe 的code 实现如何invoke event.. 鍥磋鎴戜滑@1point 3 acres
  (5)   年轻白人: (a)leetcode 上的coin 题, 用DP. (b)给你一个password 假定6位, 有个function 每call 一次就给你一个triplet 是password 里的随即三位,order不变。比如google, 可能返回, ggl, goe, oog, ool, ........问如何最有效破译这个密码,写code. . more info on 1point3acres.com


============. 鍥磋鎴戜滑@1point 3 acres
如何准备. 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.鏈枃鍘熷垱鑷1point3acres璁哄潧
LEETCODE
TOPCODER

CAREERCUP

3. Design
总结贴:
http://blog.csdn.net/sigh1988/article/details/9790337
. 1point3acres.com/bbs其它资源:
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
Facebook: Cassandra. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
Amazon: Dynamo. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴

其实读懂这5篇论文后,很多系统设计题就应该大概明白怎么做了,因为很多重要的设计思想都在这些论文中。

评分

4

查看全部评分

本帖被以下淘专辑推荐:

stellari 发表于 2015-10-3 15:56:50 | 显示全部楼层
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 | 显示全部楼层
这。。第四题第二问怎么做?? 好难。。
回复 支持 反对

使用道具 举报

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!

第三题, 楼主给的是什么算法呢?面试官期望的是什么呢?. Waral 鍗氬鏈夋洿澶氭枃绔,
第四题,能具体讲一下你的思路和面试官讨论的过程么?
第五题,(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):.1point3acres缃
是这个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)
. From 1point 3acres bbs
queiton 2:.鏈枃鍘熷垱鑷1point3acres璁哄潧
我一开始就是想到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 还是?. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
.鏈枃鍘熷垱鑷1point3acres璁哄潧
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.鐣欏璁哄潧-涓浜-涓夊垎鍦
分享一下想法 和问题 欢迎讨论
question 1:
我会用DFS 每一个node 可以mark 4个directions(因为要block o ...
. from: 1point3acres.com/bbs
感觉第二题应该是建一个带数字的trie,这样比按所有情况建trie要更有效率
回复 支持 反对

使用道具 举报

nothingtrouble 发表于 2015-10-7 22:35:13 | 显示全部楼层
guzi 发表于 2015-9-30 11:17
谢谢楼主分享,希望早上拿到dream offer!. From 1point 3acres bbs

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

猜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要更有效率
.1point3acres缃
能说说带数字的tries 怎么做吗? 交流交流
回复 支持 反对

使用道具 举报

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

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

使用道具 举报

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

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-4 10:21

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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