传说中的谷歌招聘委员会成员之一,从幕后走出来,教你学系统设计!


一亩三分地论坛

 找回密码
 获取更多干活,快来注册
天天打游戏、照样领工资、还办H1B
这份工作你要不要?
把贵司招聘信息放这里
查看: 3293|回复: 17
收起左侧

谷歌 匹兹堡 11.15 昂赛

[复制链接] |试试Instant~ |关注本帖
shao921024 发表于 2016-11-16 08:04:46 | 显示全部楼层 |阅读模式

2016(10-12月) 码农类 硕士 全职@Google - 猎头 - Onsite |Otherfresh grad应届毕业生

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

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

x
今天去了谷歌匹兹堡昂赛
四轮题都不算难. From 1point 3acres bbs
1. 温柔可爱的Sarah:
  • 给一个List<String[]> pairs, 里面的array是长度为2的pair,双向的。
  • 然后输入两个query, 每个query都是一个String[], 要判断这两个query是不是一个 叽里咕噜叽里咕噜
  • 条件就是这两个Array对应位置上的String要么一模一样,要不就是pair.
  • Follow up: 用一个全局变量做pair的map, 因为真对会有很多, 另一个是优化pair储存,有连续性,a -> b, b - > c, 要也能存a - > c

2. 听不懂说话的Needvir:

  • 返回一棵树里面所有的 爸爸->我->儿子 的序列
  • 我就是DFS做的,想办法查重就好了(如果你的方法有重的话)
  • Follow up: 因为我查重了所以,他问我,把一个Node作为Key放到一个Map里面的时间复杂度。


3. 可爱的胖Joe:
  • 同学做过的,返回一棵树里面所有相同子树的node,List<List<Node>>, 每一个list里面存的都是拥有相同树结构的树根。
  • 把所有节点下面的书都seralize, 然后存成 Map<Stirng, List<Node>>.
  • Follow up: 时间空间复杂度,如何优化. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴

. 1point3acres.com/bbs
4. 不耐烦的Charlie:
  • 一大堆Task有开始时间和结束时间,要把这些工作派给不同的工人
  • 每个工人有一个list存放自己要做的Task
  • 要求把这些工作尽可能的安排给少的工人,存在他们的工作List里面
  • 最后返回这些工人

.鏈枃鍘熷垱鑷1point3acres璁哄潧
代发都写出来了,心里没底,攒人品,也不求大米,只求好运,希望对大家有帮助。
鏉ユ簮涓浜.涓夊垎鍦拌鍧.

补充内容 (2016-12-10 04:58):
HC挂了,大家加油QAQ

评分

2

查看全部评分

本帖被以下淘专辑推荐:

zyoppy008 发表于 2016-11-16 16:46:41 | 显示全部楼层
第三轮 如何优化  求教
回复 支持 反对

使用道具 举报

zyoppy008 发表于 2016-11-16 16:50:28 | 显示全部楼层
第一题没看懂 第四题求详细 每个工人存放的task是来自于要分发的task 还是不是
回复 支持 反对

使用道具 举报

 楼主| shao921024 发表于 2016-11-16 22:18:03 | 显示全部楼层
zyoppy008 发表于 2016-11-16 16:50
第一题没看懂 第四题求详细 每个工人存放的task是来自于要分发的task 还是不是

第一题的话很简单,就是两个String Array比较,合法就返回true,不合法就返回false.. 1point3acres.com/bbs
第三轮我也没说出什么好的优化,跟他讨论了一下,说时间空间现在都是O(n), 他说空间上,Map的key会很长,我说是的诶,但是不可避免的我需要存下来unique的树结构的所有信息用String,他说那好吧,其实他也没答案。
第四题工人存放的是安排给他的工作,就是所有工作安排给所有工人,然后所有工人组成的list就是结果。
回复 支持 反对

使用道具 举报

amyzen 发表于 2016-11-18 14:51:16 | 显示全部楼层
想问下LZ 第四题怎样保证尽量分给少的工人呢?谢谢啦. more info on 1point3acres.com
回复 支持 反对

使用道具 举报

hellojay 发表于 2016-11-20 04:32:19 | 显示全部楼层
同问楼主第四题思路,觉得是Meeting room2的拓展
回复 支持 反对

使用道具 举报

hellojay 发表于 2016-11-20 04:37:28 | 显示全部楼层
刚想到的,可不可以用一个class 存worker的id, interval的start和end。按照Meeting room2的思路,时间不冲突的时候更新Object, 冲突的时候建一个新的object存一个新的worker
回复 支持 反对

使用道具 举报

 楼主| shao921024 发表于 2016-11-20 04:38:42 | 显示全部楼层
amyzen 发表于 2016-11-18 14:51. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
想问下LZ 第四题怎样保证尽量分给少的工人呢?谢谢啦

跟楼下说的一样,我一上来就是Meeting Room 2 的思路,抱歉回复晚了,这两天在做别家OA

在meeting room2 里, 最常规的思路就是分开看,开始时间和结束时间,然后做完了就可以做新的,有会还在开的时候就得加一个会议室,这里跟这个很相似,我每次都找到所有现有worker中工作最早做完的那一个,然后跟最近开始的工作的开始时间作比较,如果来的记做就安排给他,来不及就加个新的。 当时时间紧也没有细想对不对。。。
回复 支持 反对

使用道具 举报

 楼主| shao921024 发表于 2016-11-20 04:39:13 | 显示全部楼层
hellojay 发表于 2016-11-20 04:32
同问楼主第四题思路,觉得是Meeting room2的拓展

对对,你说得对,详情见楼上回复,因为我时间有点紧张当时,就没细想对不对。。
回复 支持 反对

使用道具 举报

gretchency 发表于 2016-11-21 03:30:51 | 显示全部楼层
第二题就是binary tree paths?
回复 支持 反对

使用道具 举报

 楼主| shao921024 发表于 2016-11-21 03:42:29 | 显示全部楼层
gretchency 发表于 2016-11-21 03:30
第二题就是binary tree paths?

不一定是binary, 有不一定个数个子节点
回复 支持 反对

使用道具 举报

laiguojiuhao 发表于 2016-11-29 13:42:09 | 显示全部楼层
shao921024 发表于 2016-11-20 04:38.鐣欏璁哄潧-涓浜-涓夊垎鍦
跟楼下说的一样,我一上来就是Meeting Room 2 的思路,抱歉回复晚了,这两天在做别家OA. 1point3acres.com/bbs
-google 1point3acres
在meeting roo ...

楼主你好,最早做完的后来还用了一个新的heap吗,还是遍历就够了?祝offer!
回复 支持 反对

使用道具 举报

yingying 发表于 2016-12-9 08:07:00 | 显示全部楼层
第三题的话,是用个Map<String, List<Node>>?  String存的是postorder path。没想到简单的办法,感觉这样好蠢。请问lz是怎么做的?

补充内容 (2016-12-9 08:07):
根据lc,一般string很长的话,说起来是O(1),实际上慢的不行。。。。感觉好弱智
回复 支持 反对

使用道具 举报

swufejun 发表于 2016-12-10 04:05:36 | 显示全部楼层
求问lz最后过了吗
回复 支持 反对

使用道具 举报

 楼主| shao921024 发表于 2016-12-10 04:54:53 | 显示全部楼层
laiguojiuhao 发表于 2016-11-29 13:42
楼主你好,最早做完的后来还用了一个新的heap吗,还是遍历就够了?祝offer!

没有用新的heap.
回复 支持 反对

使用道具 举报

 楼主| shao921024 发表于 2016-12-10 04:57:45 | 显示全部楼层
yingying 发表于 2016-12-9 08:07
第三题的话,是用个Map?  String存的是postorder path。没想到简单的办法,感觉这样好蠢。请问lz是怎么做的 ...

这个已经是我想到的比较好的方法了,面试的时候他也follow up这个问题,我觉得你能说清楚问题就可以了
回复 支持 反对

使用道具 举报

 楼主| shao921024 发表于 2016-12-10 04:57:53 | 显示全部楼层
swufejun 发表于 2016-12-10 04:05. 鍥磋鎴戜滑@1point 3 acres
求问lz最后过了吗

HC 挂了
回复 支持 反对

使用道具 举报

swufejun 发表于 2016-12-10 04:58:20 | 显示全部楼层
shao921024 发表于 2016-12-9 15:57. more info on 1point3acres.com
HC 挂了

gg思密达。。。HC貌似挂人概率还挺大的
回复 支持 反对

使用道具 举报

本版积分规则

关闭

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

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

custom counter

GMT+8, 2017-9-26 01:24

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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