一亩三分地论坛

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

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

谷歌 匹兹堡 11.15 昂赛

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

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

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

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

x
今天去了谷歌匹兹堡昂赛
四轮题都不算难
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: 时间空间复杂度,如何优化


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


代发都写出来了,心里没底,攒人品,也不求大米,只求好运,希望对大家有帮助。

评分

1

查看全部评分

本帖被以下淘专辑推荐:

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. 1point3acres.com/bbs
第一题没看懂 第四题求详细 每个工人存放的task是来自于要分发的task 还是不是
.鐣欏璁哄潧-涓浜-涓夊垎鍦
第一题的话很简单,就是两个String Array比较,合法就返回true,不合法就返回false.
第三轮我也没说出什么好的优化,跟他讨论了一下,说时间空间现在都是O(n), 他说空间上,Map的key会很长,我说是的诶,但是不可避免的我需要存下来unique的树结构的所有信息用String,他说那好吧,其实他也没答案。
第四题工人存放的是安排给他的工作,就是所有工作安排给所有工人,然后所有工人组成的list就是结果。. 1point 3acres 璁哄潧
回复 支持 反对

使用道具 举报

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

使用道具 举报

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
. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴. Waral 鍗氬鏈夋洿澶氭枃绔,
在meeting room2 里, 最常规的思路就是分开看,开始时间和结束时间,然后做完了就可以做新的,有会还在开的时候就得加一个会议室,这里跟这个很相似,我每次都找到所有现有worker中工作最早做完的那一个,然后跟最近开始的工作的开始时间作比较,如果来的记做就安排给他,来不及就加个新的。 当时时间紧也没有细想对不对。。。
回复 支持 反对

使用道具 举报

 楼主| shao921024 发表于 2016-11-20 04:39:13 | 显示全部楼层
hellojay 发表于 2016-11-20 04:32.1point3acres缃
同问楼主第四题思路,觉得是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 发表于 7 天前 | 显示全部楼层
shao921024 发表于 2016-11-20 04:38
跟楼下说的一样,我一上来就是Meeting Room 2 的思路,抱歉回复晚了,这两天在做别家OA

在meeting roo ...
. 1point3acres.com/bbs
楼主你好,最早做完的后来还用了一个新的heap吗,还是遍历就够了?祝offer!
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-6 14:24

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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