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


一亩三分地论坛

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

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

microsoft on campus interview

[复制链接] |试试Instant~ |关注本帖
hydejyy 发表于 2014-10-28 02:38:24 | 显示全部楼层 |阅读模式

2014(10-12月) 码农类 硕士 全职@Microsoft - 校园招聘会 - 校园招聘会 |Other

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

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

x
刚刚面试完 过来分享一下

是半个月前学校career fair投的简历 上周安排了面试时间 今天on campus面试 时间很短 45分钟

一上来就问了最骄傲的project 讲了讲过程怎么实现的 然后问了一个web development的project 问了两嘴技术 还有最challenge的 为什么

然后就是上代码 findpath between 2 node (BST) 给root n1 n2 然后打印n1 n2 之间的path

刷题好少 树结构偏偏也不熟 然后就墨迹墨迹一直墨迹到面试结束。。。

不会做就瞎说瞎问 哦对了 还让自己说两个 test case 最后让我随便问了两个问题就让我走了

不指望啦 分享大家啦

评分

3

查看全部评分

 楼主| hydejyy 发表于 2014-10-28 07:04:37 | 显示全部楼层
关注一亩三分地公众号:
Warald_一亩三分地
wstjpu 发表于 2014-10-28 06:49.1point3acres缃
LZ能详细说一下 怎么根据lca inplace 回溯 然后及时打印

我觉得楼上说的是对的 那个节点 能把n1n2分别分在左右树的 应该就是lowest common ancestor了
然后我当时是分别左右走 左边往下走的时候存进了stack 走完了之后一一pop出来是左边的路径 然后是lca
然后走右边 边走边print了 比较笨的方法

比如 一个BST 30 40 50 100 130 150 160  其中100是root 如果输入n1 n2 是 30 130 那路径就是 30 40 100 150 130 所以左边走的时候我push 走完pop print 右边边走边print 因为是BST 就像楼上说的检索N1 N2就好了吧 比较值的大小

不知道表述清楚没?或者大家有好的方法吗?我比较笨
回复 支持 1 反对 0

使用道具 举报

王可雪 发表于 2014-10-28 03:00:25 | 显示全部楼层
关注一亩三分地微博:
Warald
其实就是找common ancestor吧
回复 支持 反对

使用道具 举报

 楼主| hydejyy 发表于 2014-10-28 03:43:14 | 显示全部楼层
王可雪 发表于 2014-10-28 03:00. 1point 3acres 璁哄潧
其实就是找common ancestor吧

不是呢  我一开始以为也是   不过第一步我确实找了common ancestor 因为两个点的path肯定要路过它嘛
回复 支持 反对

使用道具 举报

王可雪 发表于 2014-10-28 03:45:36 | 显示全部楼层
hydejyy 发表于 2014-10-28 03:43
不是呢  我一开始以为也是   不过第一步我确实找了common ancestor 因为两个点的path肯定要路过它嘛

找到common ancestor再回溯(也许不用也行?)一下不就能得到path了吗?
.鏈枃鍘熷垱鑷1point3acres璁哄潧
补充内容 (2014-10-28 03:50):
要return成什么结构?array or list?
回复 支持 反对

使用道具 举报

水逼一枚 发表于 2014-10-28 04:51:19 | 显示全部楼层
不是找到LCA 以后 再分别找到LCA到两个点的path 最后Merge吗?
回复 支持 反对

使用道具 举报

daihao0310 发表于 2014-10-28 05:03:47 | 显示全部楼层
第一面就是common ancestor, 我也是醉了……
回复 支持 反对

使用道具 举报

还来得及吗 发表于 2014-10-28 05:09:20 | 显示全部楼层
变相的common ancestor啊~
LZ有结果了吗
回复 支持 反对

使用道具 举报

 楼主| hydejyy 发表于 2014-10-28 05:16:06 | 显示全部楼层
王可雪 发表于 2014-10-28 03:45
找到common ancestor再回溯(也许不用也行?)一下不就能得到path了吗?

补充内容 (2014-10-28 03:50):

他给了个void function 及时print吧 回溯一下点醒我啊 当时是完全傻了 脑子空白
回复 支持 反对

使用道具 举报

 楼主| hydejyy 发表于 2014-10-28 05:16:34 | 显示全部楼层
水逼一枚 发表于 2014-10-28 04:51
不是找到LCA 以后 再分别找到LCA到两个点的path 最后Merge吗?

是这个意思滴
回复 支持 反对

使用道具 举报

 楼主| hydejyy 发表于 2014-10-28 05:17:19 | 显示全部楼层
还来得及吗 发表于 2014-10-28 05:09
变相的common ancestor啊~
LZ有结果了吗

对啊  变相的
没有呢 今天刚面完 他说等三周出结果?略长啊。。。
回复 支持 反对

使用道具 举报

还来得及吗 发表于 2014-10-28 05:20:06 | 显示全部楼层
hydejyy 发表于 2014-10-28 05:17
对啊  变相的
没有呢 今天刚面完 他说等三周出结果?略长啊。。。
. Waral 鍗氬鏈夋洿澶氭枃绔,
嗯 不过应该一周左右就差不多了 加油哈~
回复 支持 反对

使用道具 举报

 楼主| hydejyy 发表于 2014-10-28 05:22:32 | 显示全部楼层
还来得及吗 发表于 2014-10-28 05:20. 1point 3acres 璁哄潧
嗯 不过应该一周左右就差不多了 加油哈~

吼吼 你也是哦 我还得继续刷题。。。
回复 支持 反对

使用道具 举报

sunnyroom 发表于 2014-10-28 05:32:29 | 显示全部楼层
不是common ancestor. 1point3acres.com/bbs

注意到这是个binary search tree.  
所以, 找两个node的 path,就是 检索的过程,边检索,边保存走过的路径。

首先找到一个节点,能把n1, n2. 分别分在左右子树。
再分别检索n1, n2.
连接走过的path.
回复 支持 反对

使用道具 举报

wstjpu 发表于 2014-10-28 06:49:50 | 显示全部楼层
hydejyy 发表于 2014-10-28 05:16. From 1point 3acres bbs
他给了个void function 及时print吧 回溯一下点醒我啊 当时是完全傻了 脑子空白

.1point3acres缃LZ能详细说一下 怎么根据lca inplace 回溯 然后及时打印
回复 支持 反对

使用道具 举报

shinichish 发表于 2014-10-29 01:45:55 | 显示全部楼层
wstjpu 发表于 2014-10-28 06:49
LZ能详细说一下 怎么根据lca inplace 回溯 然后及时打印

不是lca,注意条件BST
回复 支持 反对

使用道具 举报

查理王子水果茶 发表于 2014-11-18 09:41:12 | 显示全部楼层
LZ出结果了吗?
回复 支持 反对

使用道具 举报

本版积分规则

关闭

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

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

custom counter

GMT+8, 2017-6-23 23:53

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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