一亩三分地论坛

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

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

[找工就业] google onsite 面经,顺带求问这样的表现能拿offer吗?

[复制链接] |试试Instant~ |关注本帖
tltzhsajsdr 发表于 2016-1-16 23:17:34 | 显示全部楼层 |阅读模式

2016(1-3月)-[14]CS硕士+fresh grad 无实习/全职 - 校园招聘会| 码农类全职@Googlefresh grad应届毕业生

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

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

x
fresh ms,没有系统设计题,第一轮算是有一点点ood吧。昨天面的,感觉还可以,第一第二轮都是写了两题还跑了test case,第三第四轮只写了一题,主要是面试官一直要聊,还总问我些小的followup,第四轮可能是因为有shadow吧,要演示给shadow看?让我做了很多浪费时间的事情,例如把所有的需要用的到数据结构写出来,例如一直跑test case就是不让我写代码,例如把每一个方程先declare一遍,然后把时间复杂度空间复杂度写上,然后解释复杂度。。。总之就是第三四轮只写了一题,虽然我拼命的想快点写,让他再问一题,但我看他也没有再问的意思。。。. From 1point 3acres bbs
听说onsite 通过率不到10% ? 主观上是觉得还可以的。。


附上面经
Mountain View 1.15 onsite
1,印度女
        一,给一个Set<Character>,给一个string,求string里最小的substring,which contains all chars in this set. 类似leetcode里的inimum Window Substring
        二,输入为List<Stirng>,string的格式类似于: (peer,Bob,David), (peer,David,Christina),(manager,Tina,Bob)
        表示Bob和David是同事,David和Christina是同事,Tina是Bob的manager
                让你设计一种数据结构储存这些关系,并且implement以下function:
                boolean is_peer(某个员工,某个员工)
                boolean is_manager(某个员工,某个员工)
        peer的意思是他们有共同的direct manager才算peer,如果他们的manager的manager相同,不算peer
        is_manager返回时,不需要是直接的manager,例如假设Jessica 是 Eric的manager的manager的manager,这种情况也返回true. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
        开始用了union find,看两个员工是不属于同一个set,后来发现union find只能tell manager关系,对于is_peer很难实现
        又用了多叉树,每个节点是一个员工,具体忘了,反正也不太work
        在提示下定义了新类,
        class Employee{
                Employee manager;
                List<Employee> peer;
        }
        然后还是建树,peer list里存这个节点的peer
2,欧洲男 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
        一,假设内存里有一个很长的doubly linked list,例如
. 1point3acres.com/bbs                = 1 = 2 = 3 = 4 = 5 = 6 = 7 = 8 = 10 = . From 1point 3acres bbs
                输入是List<DoublyLinkedList>,返回connected component的个数
                假设这个输入里是{2,3,5,6,8},返回3
                2,3是一个component,5,6是一个component,8是一个component.鐣欏璁哄潧-涓浜-涓夊垎鍦
                没什么坑
        二,给一个String s,你可以删除一些字母,然后rearrange,使之成为palindrome,返回最长的这种palindrome,如果最长的不止一个,返回任意一个。followup,如果最长的不止一个,返回全部。坑不少


3,棕色男,语速快,似native
一个一米长的sidewalk,假设是0-1,设雨滴的宽度固定为0.01米,每次下雨的位置随机,精度是double,问多少滴雨才能使整个sidewalk变湿
        一道面经题,但是要从随机就开始写,模拟整个过程,坑,很多坑
        开始是自己建了一个雨滴类,类里有start,end,然后用类似merge interval的方法. 鍥磋鎴戜滑@1point 3 acres
        用Math.random()获得一个double来表示雨滴的起点,但是这个起点就是个坑,这起点应该落在-0.01 - 1,而不是0-1,然后让你证明如何再区间[-0.01,1]之间用Math.random()来获得均等概率的随机数
        然后merge雨点又是坑,开始写半天,用的是O(N),然后又经提示发现可以binary search来找到当前新雨点的插入位置
        然后证时间复杂度,弄半天发现是O(N * (sidewalk长度 / 每个雨滴宽度))的复杂度,二分优化到O(N * log(sidewalk长度 / 每个雨滴宽度))。让你算一个期望,估计一个分布,大概需要多少雨滴才能湿润全部sidewalk。 说了半天的standard distribution,被告知不是standard distribution。。。
        深坑,问有没有literally O(N)复杂度的方法
        提示下又用了bucket方法,建很多个bucket,每个bucket的长度是雨滴的宽度,然后每个bucket维护一个左边湿润的位置,右边湿润的位置,不断更新


4,白男,中国女shadow
        也是一个面经题吧,给一个List<Stirng> l和一个number n,让rearrange这些string,使得每一个string之后至少n个位置,才能出现重复的string。如果这种结果不止一个,返回任意一个
        例如,List = {"a","a","b","b","c","c“},n = 3
        return {a,b,c,a,b,c}
        我的做法是,先count每个string出现的次数,然后有建一个
        class str{
                String s;
                int count;
        }
        用maxheap装这些str Object,然后用从heap里取,取了放进result list里,每取出一次,count--,然后放进一个queue里,当queue的size >= n了,就从queue里取回元素,如果当前元素的count > 1,放回heap里,否则放回queue,直到heap空
        最后比较result list的size和input size是否相等,不相等的话,throw exception,相等则返回result list

















. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
.鏈枃鍘熷垱鑷1point3acres璁哄潧




. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
. 1point 3acres 璁哄潧

评分

1

查看全部评分

umd2011 发表于 2016-1-16 23:34:27 | 显示全部楼层
楼主答的很好,一定会有offer的!
问几个问题:onsite不都是在白板上写代码吗,如何写 test case 和跑 test case?
希望能收到你的回复, 已米!
回复 支持 反对

使用道具 举报

 楼主| tltzhsajsdr 发表于 2016-1-16 23:36:45 | 显示全部楼层
umd2011 发表于 2016-1-16 23:34
楼主答的很好,一定会有offer的!
问几个问题:onsite不都是在白板上写代码吗,如何写 test case 和跑 tes ...

看得出来你的判断是感性的非理性的。。不过还是谢谢你!
test case就是自己想一个case,然后一步步的走代码,到一个比如每一步i怎么走,j怎么走,中间结果都是什么解释给他听这样
回复 支持 反对

使用道具 举报

coolidgelyt 发表于 2016-1-21 04:14:56 | 显示全部楼层
觉得楼主打得挺好的,题目也挺难,应该会有offer。问一下第二轮第一题doubly linked list怎么答?
回复 支持 反对

使用道具 举报

 楼主| tltzhsajsdr 发表于 2016-1-21 10:55:22 | 显示全部楼层
coolidgelyt 发表于 2016-1-21 04:14
觉得楼主打得挺好的,题目也挺难,应该会有offer。问一下第二轮第一题doubly linked list怎么答?

谢谢! 希望如此. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
就是先把输入的list加入进一个set,然后每次从中取出一个,然后看这个的左边右边是否在set中,一直重复直到都不在set中,count + 1,直到set空,最后返回count即可。类似leetcode https://leetcode.com/problems/longest-consecutive-sequence/
回复 支持 反对

使用道具 举报

Nero_hu 发表于 2016-1-22 01:47:27 | 显示全部楼层
Good luck LZ.
回复 支持 反对

使用道具 举报

s810434 发表于 2016-1-30 04:28:49 | 显示全部楼层
Bob和David是同事那题该怎麽做呢? 有没有人可以讲解一下~ 谢谢
回复 支持 反对

使用道具 举报

coolguy 发表于 2016-2-16 09:36:27 | 显示全部楼层
感谢LZ贡献面筋。最后有offer了吗?
回复 支持 反对

使用道具 举报

hurtlocker 发表于 2016-3-5 20:42:01 | 显示全部楼层
lz水平在我之上,膜拜一记,不知拿到offer了没
回复 支持 反对

使用道具 举报

Ridingstar01 发表于 2016-9-16 14:07:02 | 显示全部楼层
谢谢楼主贡献面经!继续加油,我觉得可能写的太急了给人印象也不好。
回复 支持 反对

使用道具 举报

zxcnn 发表于 2016-9-16 19:08:54 | 显示全部楼层
据我观察,楼主肯定是有offer了。
回复 支持 反对

使用道具 举报

gaocan1992 发表于 2016-9-17 08:33:01 | 显示全部楼层
楼主怎么样啊,我感觉今天面的特是这种类型。坑还挺多的反正,很虚啊。
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-9 15:02

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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