一亩三分地论坛

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

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

Google onsite 面经

[复制链接] |试试Instant~ |关注本帖
谁的时延 发表于 2015-11-10 09:18:10 | 显示全部楼层 |阅读模式

2015(10-12月) 码农类 硕士 全职@Google - 网上海投 - Onsite |Other在职跳槽

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

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

x
面试了很多家,google家的面试整体体验最好,每个环节都安排的特别合理,整个campus很大,很舒服。
看了很多面经,下面和大家分享下面试的大概题目回馈大家的帮助,也希望能够帮助到大家,希望大家跟我一起祈福,祝我能拿到offer。
我也有一个问题,我总共面试了5轮,第一轮,没答太好,答完时间到了,面试官说他不确定代码逻辑是否正确,这轮要是挂了,整个面试就算挂了?
第二轮,答出了O(n)解法,然后面试官follow up O(logn), 一直在尝试,最后在他的提示下,想出来了,但是没时间写代码。后面三轮都答得非常好,原题和follow up都答出来了,面试官反馈特别好。但是因为第一轮,没写对,是不是就全挂了?大家有其中一轮没答好还得offer的吗? 谢谢。
.鏈枃鍘熷垱鑷1point3acres璁哄潧
下面是面试大概题目:
第一轮: 给一个 M * N的screen,和一个String,比如“Hello World", 请问整个screen能放下多少个string。
note: 如果有一个词在一行放不下,放到下一行。
这一轮感觉就是纯的字符串处理。
第二轮:给一个sorted array, 求出是否含有popular item。 popular item定义就是大于size的1/4。我给出了O(n)解法和代码。面试官follow up O(logn)。
第三轮:flow water
第四轮:给一个没排序的array,删除里面的duplicate,保留原来里面item的顺序。可能有多个重复的items。要O(n)解法
第五轮:给一个String[] array, 和任意一个移动的window size k, 对array里的元素位置进行改变,使得window里的元素不重复. 要efficient的解法。
. more info on 1point3acres.com
祝大家找工作顺利, good luck。 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
.鏈枃鍘熷垱鑷1point3acres璁哄潧

评分

5

查看全部评分

本帖被以下淘专辑推荐:

snail_914 发表于 2015-11-26 05:50:36 | 显示全部楼层
关注一亩三分地公众号:
Warald_一亩三分地
不知道楼主现在有结果了吗 保佑
关于第四轮, 不明白为什么不直接用HashSet 加双指针, 一个fast pointer正常遍历array, 一个slow来收缩array, slow标记过的部分都是没有重复的。 举个栗子, [2 3 3 4 3],
fast [2 ]
slow[2 ]
set(2)

fast [2 3].1point3acres缃
slow[2 3]
set(2 3)

fast [2 3 3]-google 1point3acres
slow[2 3]
set(2 3)

fast [2 3 3 4]
slow[2 3 4]. 1point3acres.com/bbs
set(2 3 4). 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷

fast [2 3 3 4 3]
slow[2 3 4]
set(2 3 4)

回复 支持 2 反对 0

使用道具 举报

hj867955629 发表于 2015-11-16 13:27:29 | 显示全部楼层
关注一亩三分地微博:
Warald
lianlu 发表于 2015-11-11 12:02
不知道第二轮怎么做。如果是O(n)的算法就不需要sorted array的假设了吧。可以对于每个元素二分搜索其范围, ...
. more info on 1point3acres.com
找n/4 n/2 3n/4 n这几个candidate,然后分别用二分搜索看长度满不满足
回复 支持 2 反对 0

使用道具 举报

returning 发表于 2015-11-29 03:53:18 | 显示全部楼层
snail_914 发表于 2015-11-26 06:17
请问楼主能够在解释清楚一点第三题吗? 每一个点前进路径会有什么限制呢?  . 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
第五题应该是字符串重排,  ...

第四题,为何需要双指针?如果可以用hashtable的话,那么直接从左到右遍历,如果当前的数重复出现,那么跳过,如果是第一次出现,那么把它向左移动就行了,每移动一次,更新一下index。

第五题,我看不懂你说的Heap取出k个元素append到stringbuffer,如果直接取k个最大的,那么如果保证这新的k个和前面的自身间隔大于k?我觉得还是用bst维护好一些,bst按照出现频率维护,频率大的在后面。另外一个hashtable维护前面k个已经出现的数,想要继续插入,就是在bst里面找出现频率最大的数,并且这个数没有在前面k个里面出现,找到之后,更新hasthtable,更新bst。用bst好处是,每次查找新插入的string,不需要真正取出string,只需要在bst里面从后向前走就行了。
回复 支持 1 反对 0

使用道具 举报

小小平民 发表于 2015-11-11 14:46:30 | 显示全部楼层
jkingxt 发表于 2015-11-10 15:22. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
我想问一下第四轮的题目。因为要o(n),是map+double linkedlist的解法么?

第四轮:map + linkedList 的解法是怎么做的啊?还是不太明白。
. Waral 鍗氬鏈夋洿澶氭枃绔,我的疑问是 map 的插入操作不是logN复杂度么?在扫描一遍就是NlogN了呀?
回复 支持 0 反对 1

使用道具 举报

queeniejing 发表于 2015-11-10 09:55:08 | 显示全部楼层
谢谢LZ 分享, 祝LZ 早日拿到offer。 请问下第三题 flow water 是什么题目? 还有第五题 window 里面的元素是 string 吗 还是char?
回复 支持 反对

使用道具 举报

 楼主| 谁的时延 发表于 2015-11-10 10:04:03 | 显示全部楼层
queeniejing 发表于 2015-11-10 09:55
谢谢LZ 分享, 祝LZ 早日拿到offer。 请问下第三题 flow water 是什么题目? 还有第五题 window 里面的元素 ...

第三题:
~  ~   ~   ~   ~   ~  ~
~  1   2   2   3  (5) *
~  3   2   3  (4) (4) *
~  2   4  (5)  3   1  *
~ (6) (7)  1   4   5  *
~ (5)  1   1   2   4  *
*  *   *   *   *   *  *

给定一个grid,判断是否有点技能到达~,也能到达*。就用图的DFS,BFS做。

第五题,其实比较难,考虑的情况很多,window就是在输入的string[] array里移动,windows里的元素可以是任何string。
回复 支持 反对

使用道具 举报

ljdsoft 发表于 2015-11-10 12:40:05 | 显示全部楼层
请问楼主第二轮 O(logn) 复杂度的思路是什么呢?
回复 支持 反对

使用道具 举报

licheng2002 发表于 2015-11-10 12:50:45 | 显示全部楼层
谢谢分享!请问第五题的意思是不是重新排列array使得相同string的distance至少为k?
回复 支持 反对

使用道具 举报

 楼主| 谁的时延 发表于 2015-11-10 12:54:29 | 显示全部楼层
licheng2002 发表于 2015-11-10 12:50
谢谢分享!请问第五题的意思是不是重新排列array使得相同string的distance至少为k?

这可以是一种解法,有很多种可能性,输出其中一种就行了。
回复 支持 反对

使用道具 举报

marthew777 发表于 2015-11-10 13:27:27 | 显示全部楼层
marthew777 发表于 2015-11-10 13:26 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
多谢分享。
. 1point3acres.com/bbs
完了。。字数不够。。。我擦。。被警告了。。
回复 支持 反对

使用道具 举报

yjfox 发表于 2015-11-10 13:46:47 | 显示全部楼层
谢谢lz分享 赞一个,必有offer。

请教下lz几个问题
第一轮: 每行 长度mod string长度剩下的值跟词长度match?         

第二轮:这个popular item是value 大于 size / 4 还是出现频率?如果是value的话是不是简单二分?

第五轮:感觉解法多种,比如类似greedy的统计所有string出现次数然后分配。不过这里为什么要用string[] array呢,普通char[] array也一个意思阿,难道别有用意?

谢谢lz!. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
回复 支持 反对

使用道具 举报

jkingxt 发表于 2015-11-10 15:22:32 | 显示全部楼层
我想问一下第四轮的题目。因为要o(n),是map+double linkedlist的解法么?
回复 支持 反对

使用道具 举报

yjfox 发表于 2015-11-10 23:56:21 | 显示全部楼层
jkingxt 发表于 2015-11-10 15:22
我想问一下第四轮的题目。因为要o(n),是map+double linkedlist的解法么?

you are right.
回复 支持 反对

使用道具 举报

lianlu 发表于 2015-11-11 12:02:57 | 显示全部楼层
不知道第二轮怎么做。如果是O(n)的算法就不需要sorted array的假设了吧。可以对于每个元素二分搜索其范围,但是在worst case下也有O(n)的复杂度。
回复 支持 反对

使用道具 举报

hj867955629 发表于 2015-11-16 14:24:54 | 显示全部楼层
jkingxt 发表于 2015-11-10 15:22
我想问一下第四轮的题目。因为要o(n),是map+double linkedlist的解法么?

map+双向链表怎么做?能用额外空间那感觉这题没啥trick了啊。。
回复 支持 反对

使用道具 举报

guoqinlong 发表于 2015-11-16 20:44:12 | 显示全部楼层
hj867955629 发表于 2015-11-16 13:27
找n/4 n/2 3n/4 n这几个candidate,然后分别用二分搜索看长度满不满足
. 鍥磋鎴戜滑@1point 3 acres
你好~是说对于这4个candidate,分别进行用二分法来计算是不是most popularity嘛?
回复 支持 反对

使用道具 举报

guoqinlong 发表于 2015-11-16 20:44:59 | 显示全部楼层
楼主好~想问一下第五题的思路哈~如何efficient啊~
回复 支持 反对

使用道具 举报

面假空虚 发表于 2015-11-17 11:22:29 | 显示全部楼层
yjfox 发表于 2015-11-10 13:46.鐣欏璁哄潧-涓浜-涓夊垎鍦
谢谢lz分享 赞一个,必有offer。. 1point3acres.com/bbs
. visit 1point3acres.com for more.
请教下lz几个问题

第二轮当然是count > size/4 了,要死value的话直接看最后一个元素O(1)就有结果了没意义。array是sorted的
回复 支持 反对

使用道具 举报

pyemma 发表于 2015-11-17 11:31:45 | 显示全部楼层
第二题只需要检查0, 1/4, 2/4, 3/4 4/4位置的元素看它们是不是就可以了,检查每一个数用二分搜索找左右boundary算个数,所以是(10 logn) = logn
回复 支持 反对

使用道具 举报

面假空虚 发表于 2015-11-17 11:33:28 | 显示全部楼层
guoqinlong 发表于 2015-11-16 20:44. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
你好~是说对于这4个candidate,分别进行用二分法来计算是不是most popularity嘛?
. Waral 鍗氬鏈夋洿澶氭枃绔,
对的,因为most popularity如果出现的话只能是这四个数字中的某个或某几个
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2017-4-29 11:07

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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