一亩三分地论坛

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

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

Uber onsite

[复制链接] |试试Instant~ |关注本帖
gorilazz 发表于 2015-12-5 03:24:59 | 显示全部楼层 |阅读模式

2015(10-12月) 码农类 博士 全职@Uber - 内推 - Onsite |Other在职跳槽

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

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

x
面完好几天了,一直都没消息,看样子不妙了。发帖求人品
. from: 1point3acres.com/bbs
1. Project deepdive+design uber eat
2. Design uber
3. Coding: 给一颗二叉树,每一个节点有一个value,找出一堆不相邻的节点,使得他们value的和最大。节点之间有link就算相邻,比如parent和children
4. Design auto suggest
5. Rate limiter + culture fit. 1point3acres.com/bbs

评分

5

查看全部评分

本帖被以下淘专辑推荐:

bobzhang2004 发表于 2016-1-23 22:22:18 | 显示全部楼层
大神可以详细的说说自己自己怎么回答design uber, design uber eat的吗?都问了哪些follow up question呢?谢谢
回复 支持 1 反对 0

使用道具 举报

doudoujiejie 发表于 2015-12-5 05:09:43 | 显示全部楼层
感觉各大it公司是不是share 题库 我面google onsite面到了第三题。。。
回复 支持 反对

使用道具 举报

wtcupup 发表于 2015-12-5 05:50:03 | 显示全部楼层
求第三题的的做法
回复 支持 反对

使用道具 举报

子弋 发表于 2015-12-5 13:43:28 | 显示全部楼层
请问是叶子节点到叶子节点吗?还是任意节点到任意节点

补充内容 (2015-12-5 13:47):
好像并没有区别 = =
回复 支持 反对

使用道具 举报

tiantiana 发表于 2015-12-5 23:58:06 | 显示全部楼层
Question 3:
. visit 1point3acres.com for more.
need to return all the nodes? Or, only the sum is fine.. visit 1point3acres.com for more.

Thanks,
回复 支持 反对

使用道具 举报

freemail165 发表于 2015-12-6 11:27:29 | 显示全部楼层
wtcupup 发表于 2015-12-5 05:50
求第三题的的做法

这么做是不是可以?
如果所有node都是negative, then the biggest one should be the result
否则的话,感觉上就是leetcode上那道题,找数组最大和,但是不能连续
我们只关心每层的正数,按照题意只能保留隔层的...
然后就是. 1point3acres.com/bbs
max=Math.max(max[i-1],max[i-2]+a)
回复 支持 反对

使用道具 举报

freemail165 发表于 2015-12-6 11:27:48 | 显示全部楼层
为什么两轮半 design
回复 支持 反对

使用道具 举报

dumpling_suanca 发表于 2015-12-7 04:54:27 | 显示全部楼层
freemail165 发表于 2015-12-6 11:27
这么做是不是可以?
如果所有node都是negative, then the biggest one should be the result. Waral 鍗氬鏈夋洿澶氭枃绔,
否则的话, ...

这样是不对的,不能只保留隔层,因为相邻两个子树的处理方法可能不一样。我的第一反应是recursive,就是对于每个树,它的最大“和”是选取该节点值加上所有二级子树的最大“和”,或者不选取该跟节点,但是求取它所有子树的“和”,稍晚一点儿写下代码试一下……
回复 支持 反对

使用道具 举报

freemail165 发表于 2015-12-7 14:24:46 | 显示全部楼层
design auto suggest 要求写程序了吗?
回复 支持 反对

使用道具 举报

 楼主| gorilazz 发表于 2015-12-7 14:56:50 | 显示全部楼层
freemail165 发表于 2015-12-7 14:24
design auto suggest 要求写程序了吗?

写了个trie
回复 支持 反对

使用道具 举报

aiwojiujiu 发表于 2015-12-9 15:13:03 | 显示全部楼层
dumpling_suanca 发表于 2015-12-7 04:54. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
这样是不对的,不能只保留隔层,因为相邻两个子树的处理方法可能不一样。我的第一反应是recursive,就是 ...

你的思路是对的  然后可以用dp优化 这个应该是followup会问吧
回复 支持 反对

使用道具 举报

hmmm 发表于 2015-12-12 06:06:56 | 显示全部楼层
你给我发的站内信我等级太低回复不了啊。。。站内发个微信号呗
回复 支持 反对

使用道具 举报

starcroce 发表于 2015-12-12 07:43:10 | 显示全部楼层
dumpling_suanca 发表于 2015-12-7 04:54
这样是不对的,不能只保留隔层,因为相邻两个子树的处理方法可能不一样。我的第一反应是recursive,就是 ...
. visit 1point3acres.com for more.
我觉得对于每一个node有val和sum,sum就是最后要求的值
leaf node的话就是node.sum = node.val,之后的话就是root.sum = max(root.left.sum+root.right.sum, (root.left.sum-root.left.val)+(root.right.sum-root.right.val)+root.val)
回复 支持 反对

使用道具 举报

pixel 发表于 2015-12-15 23:34:02 | 显示全部楼层
wtcupup 发表于 2015-12-5 05:50
求第三题的的做法

binary tree inorder traversal + house robber ?
回复 支持 反对

使用道具 举报

bobzhang2004 发表于 2015-12-16 09:30:58 来自手机 | 显示全部楼层
请问uber eat是什么意思,可以详细说说吗?
回复 支持 反对

使用道具 举报

yueyub 发表于 2015-12-20 14:15:00 | 显示全部楼层
dumpling_suanca 发表于 2015-12-7 04:54
这样是不对的,不能只保留隔层,因为相邻两个子树的处理方法可能不一样。我的第一反应是recursive,就是 ...
. visit 1point3acres.com for more.
聪明,你说的是对的。楼下提到dp,也是自然而然的。代码就不必要写了,很简单。
回复 支持 反对

使用道具 举报

budlover 发表于 2016-1-3 14:47:38 | 显示全部楼层
tiantiana 发表于 2015-12-5 23:58
Question 3:

need to return all the nodes? Or, only the sum is fine.

同问,请问是返回sum就行了么?
回复 支持 反对

使用道具 举报

jygan 发表于 2016-1-4 03:02:16 | 显示全部楼层
uber eat是什么意思?是送外卖的uber?
回复 支持 反对

使用道具 举报

jygan 发表于 2016-1-4 05:28:25 | 显示全部楼层
starcroce 发表于 2015-12-12 07:43
我觉得对于每一个node有val和sum,sum就是最后要求的值
leaf node的话就是node.sum = node.val,之后的 ...

你这个公式好像有问题,root.sum是以当前node为树的max sum, 也就是说root.sum可能包含root.val也有可能不包含。但是你用root->left->sum - root->left->val + root->right->sum - root->right->val, 你默认了root->left->sum包含root->left->val  ?
回复 支持 反对

使用道具 举报

jygan 发表于 2016-1-4 07:11:24 | 显示全部楼层
请问DP怎么做?这里DP的好处是什么?我用recursive做,每个节点也只计算了一次,因为这里recursive实际上是buttom up计算max sum的值。
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-3 04:30

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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