一亩三分地论坛

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

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

Google onsite

[复制链接] |试试Instant~ |关注本帖
jianghaon0 发表于 2015-4-14 22:18:23 | 显示全部楼层 |阅读模式

2015(4-6月) 码农类 硕士 全职@Google - Other - Onsite |Fail在职跳槽

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

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

x
Google onsite已挂,发个面经造福大家。一共面了5轮上午3轮下午2轮。
第1轮白人,很nice题目是给你一个string让你返回以这个string为前缀的最短的palindrome string讨论了下,有了思路解决了。. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
第2轮烙印,先问了下最challange的project大概5分钟然后上题不停的在电脑上打字。题目find local min in a array就是一个元素比它左右的元素都小让你找到一个输出。条件是array unsorted相邻元素不重复,先给了O(n)的方法,然后在他提示下想出log(n)的方法。
第3轮中国大叔,比较nice感觉放水题目给你一个int n把它转换成base为k的数string输出这么简单还出了一个bug。。。不过提示下改了。然后给你看代码让你改错感觉是java多线程同步之类的错
午饭跟一个白人小哥一次吃吹了吹牛.鏈枃鍘熷垱鑷1point3acres璁哄潧
第4轮烙印,居然问了第2轮一样的题目。。只不过没有相邻元素不相同的条件。让你证明为什么找不到比O(n)更好的算法。做完还有时间给了另外一题,给你一个String Array例如abcd abdd都可以简写为a4d让你判断Array里面有没有这样的String用hashmap很简单。
第5轮一个老白资深程序员吧,估计我就是挂在他手里。这轮本来时间就不够他还要去找水笔拿水估计只做了30分钟结果没写完思路是有了不过不是最优解。题目是给你一个String 里面有a-z 0-9可以转换成一个m*n的char矩阵,然后给你一个String 让你在m*n矩阵里面寻找s并且输出寻找指针移动的过程(过程不唯一随便输出一个)。
Ex:
s e c
t b d
a r d
如果让你找star 你就输出“ddl” move down down right
我用dfs穷举法做每次4个方向做穷举貌似他不满意还找出我一个bug。。。
总的来说题目都不难,都做出来了但是总免不了粗心出现了几个bug可能这就是挂掉的原因吧。大家好好努力面试细心,希望还是很大的。
最后祝大家都有好offer,顺便求大米谢谢啦。


评分

6

查看全部评分

本帖被以下淘专辑推荐:

stellari 发表于 2015-6-26 17:28:45 | 显示全部楼层
jianghaon0 发表于 2015-4-21 02:37
比如说给你个矩阵
A B C
D E F
. Waral 鍗氬鏈夋洿澶氭枃绔,
感谢楼主分享。不过我觉得这个题的时间复杂度严格来说是否应该为O(m*n + (m+n)*k)? 其中k是待找单词的长度。
. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
首先我们建立一个hashmap,将每个字母映射到它的坐标上去。然后对待找单词中的每一个字母 i,我们计算当前坐标位置和 字母 i 所在位置的路径。因为这两个位置最大差距不会超过(M, N),所以路径长度最大是M + N,于是总的路径构建复杂度是O((M+N) * K),再加上构建hashmap的 O(M*N)时间,总时间复杂度应该是O(M*N + (M+N)*K)
回复 支持 1 反对 0

使用道具 举报

jeager 发表于 2015-4-15 12:49:26 | 显示全部楼层
求教 第三轮那个多线程同步是啥啊.....是用到multithreading了么......
回复 支持 反对

使用道具 举报

 楼主| jianghaon0 发表于 2015-4-15 21:32:40 | 显示全部楼层
大概就是ad里面有bank的account的信息。然后用户点击ad以后要给bank账户打钱之类的函数让你看看有什么错。应该是多线程的问题更新账户的时候要synchronize block我感觉是这样。
回复 支持 反对

使用道具 举报

jeager 发表于 2015-4-15 22:01:06 | 显示全部楼层
jianghaon0 发表于 2015-4-15 21:32
大概就是ad里面有bank的account的信息。然后用户点击ad以后要给bank账户打钱之类的函数让你看看有什么错。 ...

哦哦哦 这样啊 我还以为要自己写multithreading的code 吓尿了.......
回复 支持 反对

使用道具 举报

 楼主| jianghaon0 发表于 2015-4-15 22:47:51 | 显示全部楼层
jeager 发表于 2015-4-15 22:01
哦哦哦 这样啊 我还以为要自己写multithreading的code 吓尿了.......

哈哈很简单的,不用怕小心仔细些没问题的
回复 支持 反对

使用道具 举报

kaleo211 发表于 2015-4-16 07:33:30 | 显示全部楼层
楼主, find local min in array, 你还记得log(n)的算法是什么么?
回复 支持 反对

使用道具 举报

hotIce 发表于 2015-4-16 09:52:24 | 显示全部楼层
kaleo211 发表于 2015-4-16 07:33.鐣欏璁哄潧-涓浜-涓夊垎鍦
楼主, find local min in array, 你还记得log(n)的算法是什么么?
鏉ユ簮涓浜.涓夊垎鍦拌鍧.
binary search 每次去点half http://www.careercup.com/question?id=8223978
回复 支持 反对

使用道具 举报

kaleo211 发表于 2015-4-16 23:12:47 | 显示全部楼层
hotIce 发表于 2015-4-16 09:52.鐣欏璁哄潧-涓浜-涓夊垎鍦
binary search 每次去点half http://www.careercup.com/question?id=8223978
. 1point3acres.com/bbs
这个算法真牛逼啊,
回复 支持 反对

使用道具 举报

zyn334455 发表于 2015-4-20 10:47:10 | 显示全部楼层
第四问还能有什么最优解么?
回复 支持 反对

使用道具 举报

hefang 发表于 2015-4-20 11:22:03 | 显示全部楼层
“第4轮烙印,居然问了第2轮一样的题目。。只不过没有相邻元素不相同的条件。让你证明为什么找不到比O(n)更好的算法。” 如何证明呢?难道说之前第二轮log(n)的算法不能用吗?
回复 支持 反对

使用道具 举报

 楼主| jianghaon0 发表于 2015-4-20 21:45:24 | 显示全部楼层
hefang 发表于 2015-4-20 11:22
“第4轮烙印,居然问了第2轮一样的题目。。只不过没有相邻元素不相同的条件。让你证明为什么找不到比O(n)更 ...

不能用因为他没有给定你相邻元素不相同的条件。证明方法是假设存在一个比线性快的刷法你要给出反例证明这个算法无法实现。我是给了一个例子Array [2,2,2] 如果你不线性的扫描一遍你不会知道这个数组不存在peak element

评分

1

查看全部评分

回复 支持 反对

使用道具 举报

 楼主| jianghaon0 发表于 2015-4-21 01:12:08 | 显示全部楼层
zyn334455 发表于 2015-4-20 10:47
第四问还能有什么最优解么?
. 1point3acres.com/bbs
好像可以一个字母一个字母的在矩阵中间找到位置(i,j)然后你得到一个(i,j)的序列。然后根据这个序列产生移动步骤。应该是o(m*n)复杂度吧。
回复 支持 反对

使用道具 举报

zyn334455 发表于 2015-4-21 02:03:05 | 显示全部楼层
jianghaon0 发表于 2015-4-21 01:12
好像可以一个字母一个字母的在矩阵中间找到位置(i,j)然后你得到一个(i,j)的序列。然后根据这个序列 ...

恩。。。不太明白是什么意思,是用一个hashtable记录每个字母和它出现的位置么?
回复 支持 反对

使用道具 举报

 楼主| jianghaon0 发表于 2015-4-21 02:37:29 | 显示全部楼层
zyn334455 发表于 2015-4-21 02:03
恩。。。不太明白是什么意思,是用一个hashtable记录每个字母和它出现的位置么?

比如说给你个矩阵
A B C
D E F
G H I. Waral 鍗氬鏈夋洿澶氭枃绔,
给你的string是“ECG”
然后你就找ECG在矩阵内的位置(1,1), (0,2), (2,0)根据这3个位置你就可以知道最后移动的步骤了
开始(0,0)->(1,1) "DR" (1,1)->(0,2) "LU" 等等
时间复杂度O(m*n)
回复 支持 反对

使用道具 举报

zyn334455 发表于 2015-4-21 04:27:58 | 显示全部楼层
jianghaon0 发表于 2015-4-21 02:37
比如说给你个矩阵
A B C
D E F

哦哦这样。。但假如说如果有重复字母呢?比如说矩阵里有M*N个元素,然后给定搜索单词长度为K,然后最坏情况是这M*N个元素里就只有给定搜索单词里的字母且单词的相邻字母在矩阵中互不相邻,平均每个字母出现了M*N/K次,那这样时间复杂度不就是O((M*N/K)^K)的复杂度了么,是指数级的?. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴

补充内容 (2015-4-21 04:29):
哦这个最坏情况我好像举的有点问题。。。我再想想
回复 支持 反对

使用道具 举报

 楼主| jianghaon0 发表于 2015-4-21 05:20:35 | 显示全部楼层
zyn334455 发表于 2015-4-21 04:27
哦哦这样。。但假如说如果有重复字母呢?比如说矩阵里有M*N个元素,然后给定搜索单词长度为K,然后最坏情 ...

这个你要跟你的面试官讨论我问过他,输入假设是没有重复。开始做的时候你就要把各种情况跟他说好这样就没问题了。
回复 支持 反对

使用道具 举报

zyn334455 发表于 2015-4-21 05:46:29 | 显示全部楼层
jianghaon0 发表于 2015-4-21 05:20
这个你要跟你的面试官讨论我问过他,输入假设是没有重复。开始做的时候你就要把各种情况跟他说好这样就没 ...

OK,明白了,多谢楼主!
回复 支持 反对

使用道具 举报

magicalcan 发表于 2015-5-28 15:52:40 | 显示全部楼层
最后一轮矩阵的suppose应该用trie做,感觉就是leet code的新题word search2. 普通的backtrack对于large test不行
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-4 01:47

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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