推荐:数据科学课程和书籍清单以及培训讲座


一亩三分地论坛

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

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

Doordash电面二面

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

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

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

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

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

之前看地里的面经不多,而且都是数组相关的题目,所以没有特别准备其他的,结果考了个tree的题目,不过题目还是不难. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
给一个BST的root,和两个node,求两个node的path

. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
希望能攒个人品进到下一轮!.1point3acres缃

评分

1

查看全部评分

swufejun 发表于 2016-11-18 05:13:15 | 显示全部楼层
怎么样,祝好。。。找的内推还是海投的呀
回复 支持 反对

使用道具 举报

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

使用道具 举报

 楼主| Crystal_yy 发表于 2016-11-19 01:06:09 | 显示全部楼层
swufejun 发表于 2016-11-18 05:13
怎么样,祝好。。。找的内推还是海投的呀
.1point3acres缃
写成评论了。。。
回复 支持 反对

使用道具 举报

frk 发表于 2016-12-4 08:52:42 | 显示全部楼层
楼主可以再讲解一下这道题吗. 鍥磋鎴戜滑@1point 3 acres

补充内容 (2016-12-4 09:15):. 1point 3acres 璁哄潧
谢谢楼主分享。 这个会用到lowest common ancestor吗
回复 支持 反对

使用道具 举报

 楼主| Crystal_yy 发表于 2016-12-5 06:54:06 | 显示全部楼层
frk 发表于 2016-12-4 08:52. more info on 1point3acres.com
楼主可以再讲解一下这道题吗
. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
补充内容 (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上,这样对吗?

回复 支持 反对

使用道具 举报

 楼主| 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. 1point3acres.com/bbs
额。。我有点没懂你后面说的left right child!=null的部分耶,我当时没有想太复杂的方法,就是直接脑子 ...

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

使用道具 举报

 楼主| Crystal_yy 发表于 2016-12-13 23:34:47 | 显示全部楼层
frk 发表于 2016-12-13 13:11
就是用的LC上 LCA binary  tree的那道题的做法。我接下来是第二轮。 那遍历的话就是暴力搜嘛。

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

使用道具 举报

本版积分规则

关闭

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

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

custom counter

GMT+8, 2017-8-18 22:46

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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