一亩三分地论坛

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

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

Microsoft on-campus interview

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

2015(10-12月) 码农类 硕士 全职@Microsoft - Other - 校园招聘会 |Otherfresh grad应届毕业生

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

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

x
时间半小时
1. 聊简历
2. 什么是BST;如何判断一棵树是BST;follow up, 再来一种方法;刚才方法改进。

3. Q&A. from: 1point3acres.com/bbs


. 鍥磋鎴戜滑@1point 3 acres
补充内容 (2015-10-9 02:44):
面试官告别时说了一句祝你其他面试好运已经剧透了结局。。。

评分

1

查看全部评分

本帖被以下淘专辑推荐:

leixiang5 发表于 2015-10-9 03:28:41 | 显示全部楼层
。。。是吗。。good luck on other interviews就是据的意思吗?学习了。。。
回复 支持 反对

使用道具 举报

dwl1222 发表于 2015-10-9 03:46:58 | 显示全部楼层
楼主你这题怎么回答的他不满意阿
回复 支持 反对

使用道具 举报

 楼主| storm_hair 发表于 2015-10-9 05:22:20 | 显示全部楼层
dwl1222 发表于 2015-10-9 03:46
楼主你这题怎么回答的他不满意阿
.1point3acres缃
估计题得秒两道题才行
回复 支持 反对

使用道具 举报

honghsien5 发表于 2015-10-9 05:55:09 | 显示全部楼层
說不定他指的是on-site interview!?
這個可能是看口氣吧
回复 支持 反对

使用道具 举报

honghsien5 发表于 2015-10-9 05:55:16 | 显示全部楼层
說不定他指的是on-site interview!?-google 1point3acres
這個可能是看口氣吧
回复 支持 反对

使用道具 举报

zkfairytale 发表于 2015-10-9 06:20:59 | 显示全部楼层
判断一个树是不是BST,只用 check 一下它的 inorder traversal 是不是 increasing的就行了吧?请问一下还能如何改进啊?
回复 支持 反对

使用道具 举报

leixiang5 发表于 2015-10-9 06:25:17 | 显示全部楼层
zkfairytale 发表于 2015-10-9 06:20
判断一个树是不是BST,只用 check 一下它的 inorder traversal 是不是 increasing的就行了吧?请问一下还能 ...

看下cracking the interview 4.5 答案。inorder traversal和 The Min / Max Solution
回复 支持 反对

使用道具 举报

zkfairytale 发表于 2015-10-9 06:48:54 | 显示全部楼层
leixiang5 发表于 2015-10-9 06:25 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
看下cracking the interview 4.5 答案。inorder traversal和 The Min / Max Solution

inorder traversal如果用iterative方式来写的话,时间复杂度O(N),空间O(lgN),应该是最优的解了吧。
我没写过min/max solution,不太清楚它的复杂度。。。

补充内容 (2015-10-9 06:59):
空间的复杂度O(lgN)指的是stack的开销
回复 支持 反对

使用道具 举报

dwl1222 发表于 2015-10-9 06:51:01 | 显示全部楼层
zkfairytale 发表于 2015-10-9 06:48
inorder traversal如果用iterative方式来写的话,时间复杂度O(N),空间O(lgN),应该是最优的解了吧。
我 ...

min/max 用的是recursion.O(N)O(1)不算stackspace.  应该是最优。
回复 支持 反对

使用道具 举报

zkfairytale 发表于 2015-10-9 06:52:08 | 显示全部楼层
dwl1222 发表于 2015-10-9 06:51
min/max 用的是recursion.O(N)O(1)不算stackspace.  应该是最优。
.鏈枃鍘熷垱鑷1point3acres璁哄潧
为什么不算stackspace。。。
回复 支持 反对

使用道具 举报

dwl1222 发表于 2015-10-9 06:54:19 | 显示全部楼层
zkfairytale 发表于 2015-10-9 06:52
为什么不算stackspace。。。
. more info on 1point3acres.com
面试哪有算stack space。而且recursion 代码简短易懂。肯定最优阿。
回复 支持 反对

使用道具 举报

zkfairytale 发表于 2015-10-9 07:00:08 | 显示全部楼层
dwl1222 发表于 2015-10-9 06:54
面试哪有算stack space。而且recursion 代码简短易懂。肯定最优阿。

哦,了解了,谢谢啊。
感觉这两个方法复杂度都是最优的,只是处理问题的方式不一样,挺有意思的
回复 支持 反对

使用道具 举报

heroic 发表于 2015-10-9 07:00:14 | 显示全部楼层
用morris traversal inorder遍历也是O(n) O(1)啊
回复 支持 反对

使用道具 举报

aaa18918 发表于 2015-10-9 07:02:17 | 显示全部楼层
咦,是USC校友吗!
回复 支持 反对

使用道具 举报

leixiang5 发表于 2015-10-9 07:25:20 | 显示全部楼层
zkfairytale 发表于 2015-10-9 07:00
哦,了解了,谢谢啊。
感觉这两个方法复杂度都是最优的,只是处理问题的方式不一样,挺有意思的

inorder不能处理duplicate elements.
回复 支持 反对

使用道具 举报

zkfairytale 发表于 2015-10-9 07:29:56 | 显示全部楼层
leixiang5 发表于 2015-10-9 07:25
inorder不能处理duplicate elements.
. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
为什么不能?
遍历的时候,直接比较当前val与previous val的大小,一旦发现有val<=previous val就返回False啊
回复 支持 反对

使用道具 举报

leixiang5 发表于 2015-10-9 07:42:41 | 显示全部楼层
zkfairytale 发表于 2015-10-9 07:29 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
为什么不能?
遍历的时候,直接比较当前val与previous val的大小,一旦发现有val

看错了。以为你说的是用inorder to construct a sorted array然后看是不是真的sorted.
回复 支持 反对

使用道具 举报

youto 发表于 2015-10-9 08:21:37 | 显示全部楼层
为什么软软不来我们学校呢!哎~~~~
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-4 17:07

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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