一亩三分地论坛

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

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

google ,uber 跪经

[复制链接] |试试Instant~ |关注本帖
49502292 发表于 2016-6-9 15:27:03 | 显示全部楼层 |阅读模式

2016(4-6月) 码农类 硕士 全职@Google - 内推 - Onsite |Failfresh grad应届毕业生

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

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

x
4月,5月面的 google, uber onsite 已跪, 来发面经造福后面人顺便攒攒人品

Google 4 轮
1 轮 白人  Zigzag iterator 和LC有点出入, 输入是 list<Iterator> 解法差不多
2 轮 韩国大叔, 题目具体忘了, 大概使用sliding window + hashmap做. more info on 1point3acres.com
3 轮 白人, popular number  找出数组里面出现次数大于 n/4 的数字, 之前面经见过 解法 binary search
4 轮 不只是哪人,全程无表情。 给一个二叉树,一个source node 和 一个 target node, 问是否有一个路径从source node 到 target node (沿着parent 到 children ) ,LZ很天真的说用dfs做下,写完然后问如何在O1 time 和space 找到, LZ没想出, 然后提示是说先preprocess下,每个node 加一个label 的range,举个栗子 [1,10] 代表这个node下面的节点范围是1-10 这样通过判断 target node 的label是否在范围内就可以确定,感觉像segment tree, 最后没时间写代码了。 跪了。。。


Uber 4轮
1轮 写一个BST 类, implement search,delete node, 然后自己建树,跑test case。 LZ delete写出了个bug 花了几分钟修bug。
2轮 desing uber pool  还是校友,出个这么难得design 给跪了。。 难点如何匹配适合拼车的riders
3轮  给一个图,如何判断是一颗数。 这轮我也是醉了,什么都不给 自己定义input。 写了一会白板, 然后说我们用电脑写吧 然后跑几个case 给跪了。。 写完又解释了半天 最后没时间测testcase了
4轮 hiring manage 瞎b聊。  主要聊怎么用ML detect fraud。 感觉聊得还可以吧,然并卵 该跪还是跪。

以上差不多就这些, 最后再吐个槽, 今年真是日了狗 不知道是点背还是实力挫, 找个工地搬砖这么蛋疼。 跪了6个onsie了,什么时候能结束。

评分

2

查看全部评分

diyutianshi 发表于 2016-6-10 15:06:36 | 显示全部楼层
diyutianshi 发表于 2016-6-10 15:05
从根节点开始DFS树,记每个节点的开始时间和结束时间,对点A而言,如果[s_a, e_a]严格被B的[s_b, e_b]包 ...

说错了 - 是2005年

https://icpcarchive.ecs.baylor.e ... em&problem=1487
.鐣欏璁哄潧-涓浜-涓夊垎鍦
就这个了,随便搜了个解题报告:

http://blog.csdn.net/shifuwawa/article/details/5857439
回复 支持 1 反对 0

使用道具 举报

diyutianshi 发表于 2016-6-9 16:41:04 | 显示全部楼层
Google的第四轮其实对应的是DFS的Parenthesis Theorem: https://www.clear.rice.edu/comp314/lec/week3/Depth-First.htm

评分

1

查看全部评分

回复 支持 1 反对 0

使用道具 举报

blackrose 发表于 2016-6-9 21:43:05 | 显示全部楼层
Popular number 那个 能用比binary search?
回复 支持 反对

使用道具 举报

blackrose 发表于 2016-6-9 21:47:37 | 显示全部楼层
Google 第四题,是dfs + merge吧。。。

补充内容 (2016-6-9 21:50):
第四题如果不是bst 不能这么用吧。。。。
回复 支持 反对

使用道具 举报

blackrose 发表于 2016-6-9 21:55:47 | 显示全部楼层
patpat 楼主,同跪了很多,不过我目前都是小公司。。。。大的只面了微软,已经不抱希望了。。。
回复 支持 反对

使用道具 举报

ScottShao 发表于 2016-6-10 00:10:41 | 显示全部楼层
diyutianshi 发表于 2016-6-9 16:41
Google的第四轮其实对应的是DFS的Parenthesis Theorem: https://www.clear.rice.edu/comp314/lec/week3/Dep ...

求问怎么用这个性质做啊
回复 支持 反对

使用道具 举报

handsomecool 发表于 2016-6-10 02:18:20 | 显示全部楼层
同问google第四轮,即使是BST也不能通过存range来O(1)判断在不在吧,比如parent node记载的range是[1, 10] , target node是7, 那可能child就是只有1,2,3,10没有7啊。。.鏈枃鍘熷垱鑷1point3acres璁哄潧

每个node存下所有具体child node的值要O(n^2)估计也不是好办法

补充内容 (2016-6-10 03:16):.鐣欏璁哄潧-涓浜-涓夊垎鍦
哦!我可能没理解到题目一个条件,就是target node已知是存在于这个BST里的,那我觉得这个存range的做法没错,如果是BST的话。
回复 支持 反对

使用道具 举报

laogudongfu 发表于 2016-6-10 02:47:50 | 显示全部楼层
handsomecool 发表于 2016-6-10 02:18
同问google第四轮,即使是BST也不能通过存range来O(1)判断在不在吧,比如parent node记载的range是[1, 10]  ...

我感觉并不用segment tree 这么麻烦。对这棵树分别做前序遍历和后序遍历,把遍历的顺序分别存在两个hashmap里,假如分别叫做pre和post 。
这样对于两个node A和B, 如果pre[A] < pre[B] and post[A] > post[B]成立,那么就有从A到B的路径。
回复 支持 反对

使用道具 举报

blackrose 发表于 2016-6-10 02:54:48 | 显示全部楼层
laogudongfu 发表于 2016-6-10 02:47-google 1point3acres
我感觉并不用segment tree 这么麻烦。对这棵树分别做前序遍历和后序遍历,把遍历的顺序分别存在两个hashm ...

要求O(1).....
回复 支持 反对

使用道具 举报

laogudongfu 发表于 2016-6-10 02:59:47 | 显示全部楼层
. from: 1point3acres.com/bbs
是O(1)啊,两次遍历都是preprocess,真正判断只要从hashmap里取两个值出来比较就行了
回复 支持 反对

使用道具 举报

aangel 发表于 2016-6-10 03:24:28 | 显示全部楼层
求问第三轮那个binary search 怎么解决n/4的问题的?.1point3acres缃
第四轮要求O(1)的time和space吧,hashmap不能用了
回复 支持 反对

使用道具 举报

laogudongfu 发表于 2016-6-10 03:27:57 | 显示全部楼层
我倒是很想知道怎么才能O1 space O1time
回复 支持 反对

使用道具 举报

Xochitl 发表于 2016-6-10 03:40:30 | 显示全部楼层
laogudongfu 发表于 2016-6-10 03:27
我倒是很想知道怎么才能O1 space O1time
. 1point3acres.com/bbs
哈哈哈O(1)的space大概是正好一眼看到了是不是子树然后回答了出来吧
回复 支持 反对

使用道具 举报

handsomecool 发表于 2016-6-10 04:16:13 | 显示全部楼层
laogudongfu 发表于 2016-6-10 02:47
我感觉并不用segment tree 这么麻烦。对这棵树分别做前序遍历和后序遍历,把遍历的顺序分别存在两个hashm ...

你这个办法挺有意思,对普通非BST也有效。


补充内容 (2016-6-10 04:19):. From 1point 3acres bbs
而且你用O(n) space, 面试官提示的做法其实也是O(n) space,具体写起来还没有你的简洁
回复 支持 反对

使用道具 举报

jyttwc901231 发表于 2016-6-10 04:29:51 | 显示全部楼层
请问找popular number怎么用BST?。。。。
回复 支持 反对

使用道具 举报

blackrose 发表于 2016-6-10 04:31:31 | 显示全部楼层
jyttwc901231 发表于 2016-6-10 04:29
请问找popular number怎么用BST?。。。。

目测 先sort, 其实不用sort就可以了。。。
回复 支持 反对

使用道具 举报

jyttwc901231 发表于 2016-6-10 04:34:58 | 显示全部楼层
blackrose 发表于 2016-6-10 04:31.鐣欏璁哄潧-涓浜-涓夊垎鍦
目测 先sort, 其实不用sort就可以了。。。

sort我知道,但是那个好像有点慢?。。。
回复 支持 反对

使用道具 举报

aangel 发表于 2016-6-10 04:52:27 | 显示全部楼层
jyttwc901231 发表于 2016-6-10 04:34
sort我知道,但是那个好像有点慢?。。。

直接设3个count,3个candidate,一次pass O(n)过不就可以了吗?
跟leetcode 的majority element II类似
回复 支持 反对

使用道具 举报

Xochitl 发表于 2016-6-10 06:33:54 | 显示全部楼层
handsomecool 发表于 2016-6-10 04:16. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
你这个办法挺有意思,对普通非BST也有效。

嗯,我和laogudongfu一起证了一下这个这个解法,应该是对的。O(n)的space,O(1)的time,代码也简单。不知道楼上讲的O(1)的space是什么。。。。感觉超出了我的知识范围> <
回复 支持 反对

使用道具 举报

 楼主| 49502292 发表于 2016-6-10 09:43:08 | 显示全部楼层
handsomecool 发表于 2016-6-10 02:18
同问google第四轮,即使是BST也不能通过存range来O(1)判断在不在吧,比如parent node记载的range是[1, 10]  ...

我觉得可以这么建segment tree吧  每个node 加个 range, 然后判断 target node 是不是在 source node range 里面  o1 time o1 space 举个栗子

.1point3acres缃      [1, 5]
      /     \
   [1, 3] [4, 5]
   /   \    /  \
[1,2] 3  4   5.鐣欏璁哄潧-涓浜-涓夊垎鍦
/  \
1   2
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-4 00:18

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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