一亩三分地论坛

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

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

Doordash电面二面

[复制链接] |试试Instant~ |关注本帖
Crystal_yy 发表于 2016-11-17 09:44:08 | 显示全部楼层 |阅读模式

2016(10-12月) 码农类 硕士 全职@Doordash - 内推 - 技术电面 |Otherfresh grad应届毕业生

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

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

x
刚刚结束的Doordash二面,答得不好,只能发个面经攒攒人品了!!

之前看地里的面经不多,而且都是数组相关的题目,所以没有特别准备其他的,结果考了个tree的题目,不过题目还是不难
给一个BST的root,和两个node,求两个node的path


希望能攒个人品进到下一轮!

评分

1

查看全部评分

swufejun 发表于 2016-11-18 05:13:15 | 显示全部楼层
关注一亩三分地公众号:
Warald_一亩三分地
怎么样,祝好。。。找的内推还是海投的呀
回复 支持 反对

使用道具 举报

 楼主| Crystal_yy 发表于 2016-11-19 01:05:16 | 显示全部楼层
关注一亩三分地微博:
Warald
内推的,还没结果,你也可以试试,他家面试都不难
回复 支持 反对

使用道具 举报

 楼主| Crystal_yy 发表于 2016-11-19 01:06:09 | 显示全部楼层
swufejun 发表于 2016-11-18 05:13. more info on 1point3acres.com
怎么样,祝好。。。找的内推还是海投的呀

写成评论了。。。
回复 支持 反对

使用道具 举报

frk 发表于 2016-12-4 08:52:42 | 显示全部楼层
楼主可以再讲解一下这道题吗

. Waral 鍗氬鏈夋洿澶氭枃绔,补充内容 (2016-12-4 09:15):
谢谢楼主分享。 这个会用到lowest common ancestor吗
求职神器indeed - 在全球最大的求职网站找找适合你的工作?
回复 支持 反对

使用道具 举报

 楼主| Crystal_yy 发表于 2016-12-5 06:54:06 | 显示全部楼层
frk 发表于 2016-12-4 08:52.1point3acres缃
楼主可以再讲解一下这道题吗

补充内容 (2016-12-4 09:15):

会,我就是用找lowest common ancestor做的
回复 支持 反对

使用道具 举报

frk 发表于 2016-12-6 10:20:43 | 显示全部楼层
Crystal_yy 发表于 2016-12-5 06:54
会,我就是用找lowest common ancestor做的

然后是在recursion的过程中把path上的node存下来,最后要求把这条path上的所有Node输出嘛
回复 支持 反对

使用道具 举报

 楼主| Crystal_yy 发表于 2016-12-7 02:06:43 | 显示全部楼层
frk 发表于 2016-12-6 10:20 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
然后是在recursion的过程中把path上的node存下来,最后要求把这条path上的所有Node输出嘛

recursive的过程中的node应该不是path中的node吧,应该是正好不需要的node吧,我是找到common ancestor之后再找那个ancestor到两个node的路径再把他们连在一起的
回复 支持 反对

使用道具 举报

frk 发表于 2016-12-13 04:00:28 | 显示全部楼层
Crystal_yy 发表于 2016-12-7 02:06
recursive的过程中的node应该不是path中的node吧,应该是正好不需要的node吧,我是找到common ancestor之 ...
. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
那是从LCA向左右subtree各遍历一次吗,找到两个node,从下往上返回path上的node? 我试着是在recursion过程中按照lc上找LCA的方法,如果返回的left或是 right child != null,那么这个node就在path上,这样对吗?.1point3acres缃

回复 支持 反对

使用道具 举报

 楼主| Crystal_yy 发表于 2016-12-13 04:21:42 | 显示全部楼层
frk 发表于 2016-12-13 04:00
那是从LCA向左右subtree各遍历一次吗,找到两个node,从下往上返回path上的node? 我试着是在recursion过 ...

额。。我有点没懂你后面说的left right child!=null的部分耶,我当时没有想太复杂的方法,就是直接脑子想到什么就说什么了,而且我写好之后问面试官,面试官也说这样okay,没说什么其他的,我后来也就没想怎么优化我的方法,我是先找LCA,然后分别遍历左右部分的,然后把lca到left node的路径reverse一下,然后再去掉最后一位,也就是lca,因为右子树遍历的时候也会有lca会造成重复,然后把两个路径拼到一起就好了,你是什么时候面呀?第几轮?
回复 支持 反对

使用道具 举报

frk 发表于 2016-12-13 13:11:17 | 显示全部楼层
Crystal_yy 发表于 2016-12-13 04:21
额。。我有点没懂你后面说的left right child!=null的部分耶,我当时没有想太复杂的方法,就是直接脑子 ...

就是用的LC上 LCA binary  tree的那道题的做法。我接下来是第二轮。 那遍历的话就是暴力搜嘛。
回复 支持 反对

使用道具 举报

 楼主| Crystal_yy 发表于 2016-12-13 23:34:47 | 显示全部楼层
frk 发表于 2016-12-13 13:11. Waral 鍗氬鏈夋洿澶氭枃绔,
就是用的LC上 LCA binary  tree的那道题的做法。我接下来是第二轮。 那遍历的话就是暴力搜嘛。

嗯,对,就是用那个方法,找到LCA后,在写个function findpath(lca, node1/node2)分别找到路径和在一起就可以了,反正这肯定是正解,但是是不是最优解我就无从知晓了,但是我觉得面试官不太care是不是最优,能做出来就行,能问你下你第一轮的题目么?
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2017-2-22 11:26

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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