近期论坛无法登录的解决方案


一亩三分地论坛

 找回密码
 获取更多干活,快来注册

一亩三分地官方iOS手机应用下载
查看: 3872|回复: 25
收起左侧

google ,uber 跪经

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

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

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

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

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

Google 4 轮
1 轮 白人  Zigzag iterator 和LC有点出入, 输入是 list<Iterator> 解法差不多
2 轮 韩国大叔, 题目具体忘了, 大概使用sliding window + hashmap做
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。 感觉聊得还可以吧,然并卵 该跪还是跪。
. From 1point 3acres bbs
以上差不多就这些, 最后再吐个槽, 今年真是日了狗 不知道是点背还是实力挫, 找个工地搬砖这么蛋疼。 跪了6个onsie了,什么时候能结束。

评分

2

查看全部评分

diyutianshi 发表于 2016-6-10 15:06:36 | 显示全部楼层
关注一亩三分地公众号:
Warald_一亩三分地
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 | 显示全部楼层
关注一亩三分地微博:
Warald
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吧。。。
. 1point 3acres 璁哄潧
补充内容 (2016-6-9 21:50):. 1point 3acres 璁哄潧
第四题如果不是bst 不能这么用吧。。。。-google 1point3acres
回复 支持 反对

使用道具 举报

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.com/bbs每个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
我感觉并不用segment tree 这么麻烦。对这棵树分别做前序遍历和后序遍历,把遍历的顺序分别存在两个hashm ...

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

使用道具 举报

laogudongfu 发表于 2016-6-10 02:59:47 | 显示全部楼层

是O(1)啊,两次遍历都是preprocess,真正判断只要从hashmap里取两个值出来比较就行了
回复 支持 反对

使用道具 举报

aangel 发表于 2016-6-10 03:24:28 | 显示全部楼层
求问第三轮那个binary search 怎么解决n/4的问题的?
第四轮要求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. Waral 鍗氬鏈夋洿澶氭枃绔,
我倒是很想知道怎么才能O1 space O1time
. 1point 3acres 璁哄潧
哈哈哈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):.鏈枃鍘熷垱鑷1point3acres璁哄潧
而且你用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)过不就可以了吗?. more info on 1point3acres.com
跟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 举个栗子

      [1, 5]
      /     \ . 1point 3acres 璁哄潧
   [1, 3] [4, 5]
   /   \    /  \
[1,2] 3  4   5
/  \
1   2
回复 支持 反对

使用道具 举报

本版积分规则

关闭

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

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

custom counter

GMT+8, 2017-6-29 17:37

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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