谈谈使用过的几款咖啡机

一亩三分地论坛

 找回密码
 Sign Up 注册获取更多干货
H1B/绿卡遥遥无期
又不想回国
来东南亚最大的互联网集团工作?
码农求职神器Triplebyte:
不用海投
内推多家公司面试
坐标湾区
Games Startup
招聘游戏开发工程师
游戏初创公司招聘工程师、UIUX Designer和游戏策划
查看: 4375|回复: 25
收起左侧

google ,uber 跪经

[复制链接] |试试Instant~ |关注本帖
我的人缘0
49502292 发表于 2016-6-9 15:27:03 | 显示全部楼层 |阅读模式
  此人我要顶:
 
0% (暂未有人投票) 【我投】
  此人我要踩:
 
0% (暂未有人投票) 【我投】

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

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

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

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, 最后没时间写代码了。 跪了。。。. 1point3acres
. 留学申请论坛-一亩三分地

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大米 +60 收起 理由
hakase + 10 感谢分享!
woaibai + 50 感谢分享!

查看全部评分


上一篇:Google 6/2 Onsite [已跪]
下一篇:VMware onsite面经
我的人缘0
diyutianshi 发表于 2016-6-10 15:06:36 | 显示全部楼层
  此人我要顶:
 
0% (暂未有人投票) 【我投】
  此人我要踩:
 
0% (暂未有人投票) 【我投】
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

使用道具 举报

我的人缘0
diyutianshi 发表于 2016-6-9 16:41:04 | 显示全部楼层
  此人我要顶:
 
0% (暂未有人投票) 【我投】
  此人我要踩:
 
0% (暂未有人投票) 【我投】
Google的第四轮其实对应的是DFS的Parenthesis Theorem: https://www.clear.rice.edu/comp314/lec/week3/Depth-First.htm

评分

参与人数 1大米 +10 收起 理由
mnmunknown + 10 回答的很好!

查看全部评分

回复 支持 1 反对 0

使用道具 举报

我的人缘0
blackrose 发表于 2016-6-9 21:43:05 | 显示全部楼层
  此人我要顶:
 
0% (暂未有人投票) 【我投】
  此人我要踩:
 
0% (暂未有人投票) 【我投】
Popular number 那个 能用比binary search?
回复 支持 反对

使用道具 举报

我的人缘0
blackrose 发表于 2016-6-9 21:47:37 | 显示全部楼层
  此人我要顶:
 
0% (暂未有人投票) 【我投】
  此人我要踩:
 
0% (暂未有人投票) 【我投】
Google 第四题,是dfs + merge吧。。。

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

使用道具 举报

我的人缘0
blackrose 发表于 2016-6-9 21:55:47 | 显示全部楼层
  此人我要顶:
 
0% (暂未有人投票) 【我投】
  此人我要踩:
 
0% (暂未有人投票) 【我投】
patpat 楼主,同跪了很多,不过我目前都是小公司。。。。大的只面了微软,已经不抱希望了。。。
回复 支持 反对

使用道具 举报

我的人缘0
ScottShao 发表于 2016-6-10 00:10:41 | 显示全部楼层
  此人我要顶:
 
0% (暂未有人投票) 【我投】
  此人我要踩:
 
0% (暂未有人投票) 【我投】
diyutianshi 发表于 2016-6-9 16:41
Google的第四轮其实对应的是DFS的Parenthesis Theorem: https://www.clear.rice.edu/comp314/lec/week3/Dep ...

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

使用道具 举报

我的人缘0
handsomecool 发表于 2016-6-10 02:18:20 | 显示全部楼层
  此人我要顶:
 
0% (暂未有人投票) 【我投】
  此人我要踩:
 
0% (暂未有人投票) 【我投】
同问google第四轮,即使是BST也不能通过存range来O(1)判断在不在吧,比如parent node记载的range是[1, 10] , target node是7, 那可能child就是只有1,2,3,10没有7啊。。

每个node存下所有具体child node的值要O(n^2)估计也不是好办法
. 留学申请论坛-一亩三分地
补充内容 (2016-6-10 03:16):
哦!我可能没理解到题目一个条件,就是target node已知是存在于这个BST里的,那我觉得这个存range的做法没错,如果是BST的话。
Mobile Apps Category (English)728x90
回复 支持 反对

使用道具 举报

我的人缘0
laogudongfu 发表于 2016-6-10 02:47:50 | 显示全部楼层
  此人我要顶:
 
0% (暂未有人投票) 【我投】
  此人我要踩:
 
0% (暂未有人投票) 【我投】
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的路径。
回复 支持 反对

使用道具 举报

我的人缘0
blackrose 发表于 2016-6-10 02:54:48 | 显示全部楼层
  此人我要顶:
 
0% (暂未有人投票) 【我投】
  此人我要踩:
 
0% (暂未有人投票) 【我投】
laogudongfu 发表于 2016-6-10 02:47
我感觉并不用segment tree 这么麻烦。对这棵树分别做前序遍历和后序遍历,把遍历的顺序分别存在两个hashm ...
. visit 1point3acres for more.
要求O(1).....
回复 支持 反对

使用道具 举报

我的人缘0
laogudongfu 发表于 2016-6-10 02:59:47 | 显示全部楼层
  此人我要顶:
 
0% (暂未有人投票) 【我投】
  此人我要踩:
 
0% (暂未有人投票) 【我投】

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

使用道具 举报

我的人缘0
aangel 发表于 2016-6-10 03:24:28 | 显示全部楼层
  此人我要顶:
 
0% (暂未有人投票) 【我投】
  此人我要踩:
 
0% (暂未有人投票) 【我投】
求问第三轮那个binary search 怎么解决n/4的问题的?
第四轮要求O(1)的time和space吧,hashmap不能用了
回复 支持 反对

使用道具 举报

我的人缘0
laogudongfu 发表于 2016-6-10 03:27:57 | 显示全部楼层
  此人我要顶:
 
0% (暂未有人投票) 【我投】
  此人我要踩:
 
0% (暂未有人投票) 【我投】
我倒是很想知道怎么才能O1 space O1time
回复 支持 反对

使用道具 举报

我的人缘0
Xochitl 发表于 2016-6-10 03:40:30 | 显示全部楼层
  此人我要顶:
 
0% (暂未有人投票) 【我投】
  此人我要踩:
 
0% (暂未有人投票) 【我投】
laogudongfu 发表于 2016-6-10 03:27
我倒是很想知道怎么才能O1 space O1time

哈哈哈O(1)的space大概是正好一眼看到了是不是子树然后回答了出来吧
回复 支持 反对

使用道具 举报

我的人缘0
handsomecool 发表于 2016-6-10 04:16:13 | 显示全部楼层
  此人我要顶:
 
0% (暂未有人投票) 【我投】
  此人我要踩:
 
0% (暂未有人投票) 【我投】
laogudongfu 发表于 2016-6-10 02:47
我感觉并不用segment tree 这么麻烦。对这棵树分别做前序遍历和后序遍历,把遍历的顺序分别存在两个hashm ...

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


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

使用道具 举报

我的人缘0
jyttwc901231 发表于 2016-6-10 04:29:51 | 显示全部楼层
  此人我要顶:
 
0% (暂未有人投票) 【我投】
  此人我要踩:
 
0% (暂未有人投票) 【我投】
请问找popular number怎么用BST?。。。。
回复 支持 反对

使用道具 举报

我的人缘0
blackrose 发表于 2016-6-10 04:31:31 | 显示全部楼层
  此人我要顶:
 
0% (暂未有人投票) 【我投】
  此人我要踩:
 
0% (暂未有人投票) 【我投】
jyttwc901231 发表于 2016-6-10 04:29
请问找popular number怎么用BST?。。。。
. 留学申请论坛-一亩三分地
目测 先sort, 其实不用sort就可以了。。。
回复 支持 反对

使用道具 举报

我的人缘0
jyttwc901231 发表于 2016-6-10 04:34:58 | 显示全部楼层
  此人我要顶:
 
0% (暂未有人投票) 【我投】
  此人我要踩:
 
0% (暂未有人投票) 【我投】
blackrose 发表于 2016-6-10 04:31
目测 先sort, 其实不用sort就可以了。。。

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

使用道具 举报

我的人缘0
aangel 发表于 2016-6-10 04:52:27 | 显示全部楼层
  此人我要顶:
 
0% (暂未有人投票) 【我投】
  此人我要踩:
 
0% (暂未有人投票) 【我投】
jyttwc901231 发表于 2016-6-10 04:34
sort我知道,但是那个好像有点慢?。。。

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

使用道具 举报

我的人缘0
Xochitl 发表于 2016-6-10 06:33:54 | 显示全部楼层
  此人我要顶:
 
0% (暂未有人投票) 【我投】
  此人我要踩:
 
0% (暂未有人投票) 【我投】
handsomecool 发表于 2016-6-10 04:16
你这个办法挺有意思,对普通非BST也有效。

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

使用道具 举报

我的人缘0
 楼主| 49502292 发表于 2016-6-10 09:43:08 | 显示全部楼层
  此人我要顶:
 
0% (暂未有人投票) 【我投】
  此人我要踩:
 
0% (暂未有人投票) 【我投】
handsomecool 发表于 2016-6-10 02:18
同问google第四轮,即使是BST也不能通过存range来O(1)判断在不在吧,比如parent node记载的range是[1, 10]  ...
. visit 1point3acres for more.
我觉得可以这么建segment tree吧  每个node 加个 range, 然后判断 target node 是不是在 source node range 里面  o1 time o1 space 举个栗子

      [1, 5]
      /     \
   [1, 3] [4, 5]
   /   \    /  \
[1,2] 3  4   5
/  \
1   2
回复 支持 反对

使用道具 举报

游客
请先登录

本版积分规则

提醒:发帖可以选择内容隐藏,部分板块支持匿名发帖。请认真读完以下全部说明:

■隐藏内容方法: [hide=200]你想要隐藏的内容比如面经[/hide]
■意思是:用户积分低于200则看不到被隐藏的内容
■可以自行设置积分值,不建议太高(200以上太多人看不到),也不建议太低(那就没必要隐藏了)
■建议只隐藏关键内容,比如具体的面试题目、涉及隐私的信息,大部分内容没必要隐藏。
■微信/QQ/电子邮件等,为防止将来被骚扰甚至人肉,以论坛私信方式发给对方最安全。
■匿名发帖的板块和方法:http://www.1point3acres.com/bbs/thread-405991-1-1.html

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

custom counter

GMT+8, 2018-6-25 16:22

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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