一亩三分地论坛

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

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

10.29 google mtv onsite new grad

[复制链接] |试试Instant~ |关注本帖
zchang3 发表于 2015-10-31 01:14:24 | 显示全部楼层 |阅读模式

2015(10-12月) 码农类 硕士 全职@Google - 网上海投 - Onsite |Otherfresh grad应届毕业生

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

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

x
水校无实习背景,这波找工作还是很苦逼的,大部分公司连面试都不愿意给,能拿到google的机会还是挺高兴的。面试在youtube的一栋楼。
第一轮:
白人老太太,9年码工,题目是给一堆系统路径,类似“/abc/xyz/hij/f1”,找最长公共路径。
我说了longest common prefix的,她说怎么优化,于是说字典树,又问是不是要建完整的一颗树,于是说不用,发现要分叉了就标记一下跳出,然后从根节点找到高度最低的分叉点就是公共路径,代码没写完,最后一段写了伪代码。
第二轮:
中国大哥,感觉非常亲切。题目是给一个function叫next(),返回的是多叉树的一条边,类似(m,n),m是父节点n是子节点,让建立这棵树。
开始说先遍历一遍存成一个图,然后用拓扑排序的思路。然后在大量边的情况下优化,于是说用一个哈希表存节点指针,对于一条边,先拿到父节点(不存在就建一个插进去),然后拿子节点(不存在就插进去),把这两个点连起来,并保存父节点关系。最后遍历哈希表找到根节点。代码写完有个小bug不过小哥说可以了。
午饭:. more info on 1point3acres.com
台湾小哥,各种聊
第三轮:
白人小哥,穿着紫色女巫的紧身镂空连衣裙带着法师帽就进来了。。。
题目是给一堆people,每人有skills,再给一堆tasks,每个有需要的skills,返回bool值是否所有任务都可完成。然后一通讨论corner case。follow up问people之间不能合作怎么做。这个代码没写完,中午有点懵,反应也慢了。时间一到被小哥打断拍照走人。
第四轮:
白人程序媛,leetcode原题,判断一个数旋转180度还是不是本身,数是string形式的。follow up就是给个N,然后返回所有长度小于等于N的满足旋转条件的字符串。写完代码后聊了两分钟结束。

感觉还是达不到45分钟做两道题的水平,不过算是正常发挥了。发帖求人品求大米,各位好运~

评分

2

查看全部评分

本帖被以下淘专辑推荐:

snail_914 发表于 2015-12-8 06:22:26 | 显示全部楼层
bobzhang2004 发表于 2015-12-6 04:18
大神可以分享下code吗?对bitmap不熟。。。

抱歉啊 我没有写code。 大概pseudo code 就是 用java自带的BitMap(伪bitmap) 或者自己做个
  1. class MyBitMap{
  2.     byte[] bytes=new Byte[peopleList.length()/8]
  3.     set(index, bit)
  4.     get (index)
  5. }
复制代码
假设一共有8个人peopleList.length()就==8
MyBitMap里面 0...7 每一位对应一个人. from: 1point3acres.com/bbs
然后建立 HashMap <Skill, MyBitMap> map.  map里面的Entry就是 <SkillA, 00001001> <SkillB, 11000001>...存的是每个skill对应的有哪些人会。 会SkillA的有 0, 3号 两个人, 会SkillB的有 0, 6, 7号 三个人。
再然后遍历task, 比如TaskA 需要SkillA还有SkillB, 那就取 00001001&11000001 !=0, 说明某个人(0号) 可以独立完成taskA.



评分

1

查看全部评分

回复 支持 4 反对 0

使用道具 举报

snail_914 发表于 2015-11-19 05:14:05 | 显示全部楼层
看前面的回复 第三题第二问想到了一个快速判断的方法 给每一个人编号1 2 ...100。 建一个hashtable<skill, people>, 不过people的表现形式不用HashSet的list形式。 而是用bitmap: 每一位是某一个person,0代表该person不会这个skill,1代表会。 HashTable setup之后, 遍历tasks, 把每个task里面的skills 在前面的HashTable里找到value。 把所有value取bit and (&), 不为0的话就表示有某个人包含了所有需要的skills。 这样o (m)时间复杂下解决了问题

评分

1

查看全部评分

回复 支持 2 反对 0

使用道具 举报

宝贝忆彼岸 发表于 2015-10-31 01:34:00 | 显示全部楼层
感谢分享,请问lz能否再详细说一下第三轮的task问题,是每个人只能完成一项任务,还是多个人可以完成一项任务,还是一个人可以完成多项任务?
回复 支持 反对

使用道具 举报

 楼主| zchang3 发表于 2015-10-31 01:45:14 | 显示全部楼层
宝贝忆彼岸 发表于 2015-10-31 01:34
感谢分享,请问lz能否再详细说一下第三轮的task问题,是每个人只能完成一项任务,还是多个人可以完成一项任 ...

第一问的话没有限制,可以多个人合作完成一个任务,也可以一个人参与完成多个任务
第二问的话一个任务只能由一个人完成,但一个人可以完成多个任务
回复 支持 反对

使用道具 举报

hurtlocker 发表于 2015-10-31 02:03:38 | 显示全部楼层
感谢分享。请问那个people task这个题的大致思路是什么呢?
回复 支持 反对

使用道具 举报

孤笑客 发表于 2015-10-31 05:46:27 | 显示全部楼层
第三题第二问感觉可以用Inverted Index做?
回复 支持 反对

使用道具 举报

984619642helen 发表于 2015-10-31 05:53:52 | 显示全部楼层
楼主运气好,希望能过吧。。我遇到的四个题没一个直观的
回复 支持 反对

使用道具 举报

宝贝忆彼岸 发表于 2015-10-31 06:51:06 | 显示全部楼层
zchang3 发表于 2015-10-31 01:45. 1point3acres.com/bbs
第一问的话没有限制,可以多个人合作完成一个任务,也可以一个人参与完成多个任务
第二问的话一个任务只 ...

嗯嗯,谢谢回复,明白了,第二问我是这样想的,先建一个map,key是skill,value是由这个skill的人,然后看一个task需要哪些skill,每一个skill建一个set,存放有这些skill的人,然后每个对这些set金星intersection。
但是感觉这样做,空间复杂度很高,因为要建很多set,不知道LZ当时用了什么方法
回复 支持 反对

使用道具 举报

leochen4891 发表于 2015-11-4 05:30:47 | 显示全部楼层
感谢分享,祝怒拿offer
回复 支持 反对

使用道具 举报

hj867955629 发表于 2015-11-5 01:40:53 | 显示全部楼层
宝贝忆彼岸 发表于 2015-10-31 06:51
嗯嗯,谢谢回复,明白了,第二问我是这样想的,先建一个map,key是skill,value是由这个skill的人,然后 ...

第二问不能合作的话就是一个task只能一个人来完成,那按照people skill的数量对people排个序,然后扫一遍每个task,需要的skill数量小于之前排序的array才看是否都包含要求的skill?
回复 支持 反对

使用道具 举报

宝贝忆彼岸 发表于 2015-11-5 02:33:47 | 显示全部楼层
hj867955629 发表于 2015-11-5 01:40. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
第二问不能合作的话就是一个task只能一个人来完成,那按照people skill的数量对people排个序,然后扫一遍 ...

恩,感觉这样空间复杂度确实会减少,但是感觉时间复杂度增大,了,因为worst case对于每个task都要遍历所有的people-skill
回复 支持 反对

使用道具 举报

tinir 发表于 2015-11-9 23:25:57 | 显示全部楼层
Skill tasks 那题感觉像Leetcode里course Arrange, 然后有prerequisites 那道,不知是否类似?请教楼主 谢谢!
回复 支持 反对

使用道具 举报

nothingtrouble 发表于 2015-11-10 02:47:20 | 显示全部楼层
宝贝忆彼岸 发表于 2015-11-5 02:33
恩,感觉这样空间复杂度确实会减少,但是感觉时间复杂度增大,了,因为worst case对于每个task都要遍历所 ...
. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
或者换一种角度,每个人就是一个bitmap,每一位是某一个skill,0代表不会,1代表会。同理每一个task就是一个bitmap,每一位也是skill,0代表需要,1代表不需要,做与运算,看看每个人的bitmap能不能包含task的bitmap。
回复 支持 反对

使用道具 举报

AlexandraVon 发表于 2015-11-10 05:24:09 | 显示全部楼层
请问第四题,“旋转180度”是回文嘛?
回复 支持 反对

使用道具 举报

lianlu 发表于 2015-11-10 07:03:41 | 显示全部楼层
第三题是不是二分图的匹配?
回复 支持 反对

使用道具 举报

saberkun 发表于 2015-11-11 11:46:45 | 显示全部楼层
lianlu 发表于 2015-11-10 07:03
第三题是不是二分图的匹配?

是network flow的典型例子
回复 支持 反对

使用道具 举报

maomaoxiong 发表于 2015-11-11 12:20:25 | 显示全部楼层
第三题,遍历每个人,将对应的skill放到一个set。再遍历task,看对应的skill是否在set里面,应该可以解决第一题。
follow up;建一个hashtable。 skill-》count。每个skill有几个人会。再遍历task,对于skill也可以建立相同的map,比较一下就成了。
回复 支持 反对

使用道具 举报

snail_914 发表于 2015-11-19 04:48:10 | 显示全部楼层
maomaoxiong 发表于 2015-11-11 12:20
第三题,遍历每个人,将对应的skill放到一个set。再遍历task,看对应的skill是否在set里面,应该可以解决第 ...
. 1point3acres.com/bbs
比如Task TA 需要 Skills S1 S2。 然后people: P1 会S1, P2会S2, 楼上的方法会返回true但应该是false, 因为一个任务只能一个人完成. 感觉HashMap的value应该再存hashSet<People>, 也就是 HashMap<Skill, HashSet<People>> 不过复杂度会提高
回复 支持 反对

使用道具 举报

bobzhang2004 发表于 2015-12-6 04:11:44 | 显示全部楼层
请问trie为什么可以优化呢?都需要scan整个prefix的长度吧,每次都需要,不和两个for循环一样吗?
回复 支持 反对

使用道具 举报

bobzhang2004 发表于 2015-12-6 04:13:09 | 显示全部楼层
请问最长公共路径只的是/abc/xyz/hij/f1  /abc/xyz/f2 /xyz/f3 公共路径是xyz?还是根本没有?
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-11 04:46

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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