一亩三分地论坛

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

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

Microsoft on-site

[复制链接] |试试Instant~ |关注本帖
pro 发表于 2014-11-26 09:33:41 | 显示全部楼层 |阅读模式

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

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

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

x
感觉地里发Microsoft面经的不多啊……
. Waral 鍗氬鏈夋洿澶氭枃绔,
反正微软没让我签NDA,那我就不客气了。

早上到 building 111,和recruiter扯扯淡,聊聊offer deadline等等。

然后被dispatch到另一幢楼。开始找第一个面试官。
.鏈枃鍘熷垱鑷1point3acres璁哄潧
第一轮:.鐣欏璁哄潧-涓浜-涓夊垎鍦
聊天气,聊trip,聊简历,聊project(聊了好久!)
题目:evaluate this:
{"3", "+", "2", "*", "(", "4", "+", "2", ")", "-", "-", "1"}

第二轮:. visit 1point3acres.com for more.
聊简历,聊project。
check if two BSTs are same
write a iterator class, with constructor and getNext() (whatever-order) (我用queue写了个level-order)
how about in-order?

第三轮:
上来就做题……
symmetric binary tree
find length of longest consecutive subsequence S in an unsorted array where min * 2 > max
之后一起吃饭聊天

第四轮:
integer to roman numerals
similar to "Word Search", but the path can go in 8 directions and the input is the grid and a dictionary, return all valid words appered in the grid.

第五轮:
没做题,纯扯淡……类似于答疑,专门让我问各种问题的。
于是就从Seattle的天气聊到.net的开源、xcode被vs爆出翔等等

第六轮:(不是说好3~5轮的吗!). 1point3acres.com/bbs
聊简历,聊project。这一轮是个manager,面试之前很仔细的看过我的简历,每个project都很详细的问了过来。
题目:a memory segment is filled with c-style strings (separated by '\0'), and all strings are sorted in dictionary order. Perform a binary search on them.




补充内容 (2014-11-27 08:50):
offer已到 recruiter效率好高啊……

评分

2

查看全部评分

本帖被以下淘专辑推荐:

 楼主| pro 发表于 2014-11-26 09:37:58 | 显示全部楼层

卧槽zhu神
回复 支持 反对

使用道具 举报

neusharon 发表于 2014-11-26 09:49:04 | 显示全部楼层
find length of longest consecutive subsequence S in an unsorted array where min[s] * 2 > max[s]

这个能解释一下嘛。。
回复 支持 反对

使用道具 举报

 楼主| pro 发表于 2014-11-26 09:52:26 | 显示全部楼层
neusharon 发表于 2014-11-26 09:49-google 1point3acres
find length of longest consecutive subsequence S in an unsorted array where min * 2 > max
. more info on 1point3acres.com
...

就是比如这么一个subsequence 4 7 6, max是7,min是4,所以符合要求。
如果是4 7 6 2,min是2,就不行了。
因此 3 4 7 2 5 6 9 10 这样的,longest就是5 6 9,长度是3。
回复 支持 反对

使用道具 举报

neusharon 发表于 2014-11-26 10:07:07 | 显示全部楼层
pro 发表于 2014-11-26 09:52
就是比如这么一个subsequence 4 7 6, max是7,min是4,所以符合要求。. Waral 鍗氬鏈夋洿澶氭枃绔,
如果是4 7 6 2,min是2,就不行 ...

理解了,谢谢~
回复 支持 反对

使用道具 举报

aivanessa 发表于 2014-11-27 17:01:10 | 显示全部楼层
原来叫兽已经怒拿offer了!明年求罩!
回复 支持 反对

使用道具 举报

OPPOTIDUS 发表于 2014-12-4 07:10:27 | 显示全部楼层
求问楼主,word search 那题怎么做的啊?我之前也遇到过要输出“所有单词”的情况。我用的是第一个字母如果相同就开始往周围搜的方法。但是对方说时间复杂度太大。请问楼主是怎么做的啊?
回复 支持 反对

使用道具 举报

 楼主| pro 发表于 2014-12-4 07:17:03 | 显示全部楼层
OPPOTIDUS 发表于 2014-12-4 07:10
求问楼主,word search 那题怎么做的啊?我之前也遇到过要输出“所有单词”的情况。我用的是第一个字母如果 ...

关键是要把字典先处理成trie tree吧……
回复 支持 反对

使用道具 举报

OPPOTIDUS 发表于 2014-12-4 07:21:26 | 显示全部楼层
如果已经处理成了Trie树接下来lz是怎么做的能否简要的讲一下呢?
回复 支持 反对

使用道具 举报

OPPOTIDUS 发表于 2014-12-4 07:30:29 | 显示全部楼层
另外关于求最长的子串,min*2>max那题,我的思路是这样的, 三个变量max,min,len保存以A【i】为结尾的min*2>max子串的最大,最小,长度。max=min=len=A【0】,然后从1开始搜,如果A【i】在i-1子串的max/2,min*2的范围内的话,直接更新minmax,len++,如果不行的话,从i开始往前搜,知道到达前一个最长子串的起点,搜到第一个不符合要求的字符时记下index,以index+1为新的子串的起点,在搜索的过程中也更新min,max,然后得到以i为结束点的子串的长度和min,max。lz是这么做的么?
回复 支持 反对

使用道具 举报

 楼主| pro 发表于 2014-12-4 07:40:05 | 显示全部楼层
OPPOTIDUS 发表于 2014-12-4 07:21
如果已经处理成了Trie树接下来lz是怎么做的能否简要的讲一下呢?

然后就你说的那样从每个格子出发开始搜啊……这个n^2应该是没法避免的。用trie的话整体复杂度会小很多。
回复 支持 反对

使用道具 举报

 楼主| pro 发表于 2014-12-4 07:42:33 | 显示全部楼层
OPPOTIDUS 发表于 2014-12-4 07:30
另外关于求最长的子串,min*2>max那题,我的思路是这样的, 三个变量max,min,len保存以A【i】为结尾的min*2 ...

差不多……没必要从i开始往前搜吧。维护一个头一个尾,平时只把尾往后推,发现推过去之后不满足条件了再把头往前收,收到满足条件位置。如果发现收头的时候放走了min或者max就更新min/max。
回复 支持 反对

使用道具 举报

zude 发表于 2014-12-4 08:28:53 | 显示全部楼层
第一题怎么做啊? 计算器程序只会逆波兰计算器....
回复 支持 反对

使用道具 举报

OPPOTIDUS 发表于 2014-12-4 10:22:31 | 显示全部楼层
求问楼主还是子串那题,如果增起点的时候最小值和最大值踢出了,你是怎么更新最大最小值的啊?
回复 支持 反对

使用道具 举报

 楼主| pro 发表于 2014-12-4 10:34:28 | 显示全部楼层
OPPOTIDUS 发表于 2014-12-4 10:22
求问楼主还是子串那题,如果增起点的时候最小值和最大值踢出了,你是怎么更新最大最小值的啊?
. Waral 鍗氬鏈夋洿澶氭枃绔,
在新的子串里重新扫……我面试的时候其实就是在纠结这个。我总觉得我可以用两个队列分别负责最大最小来实现O(1)更新(类似leetcode有一题用一个额外的栈实现O(1)的栈内最小值查询的),但搞了半天没搞出来,最后还是忿忿不平的写了个每次重扫一遍的_(:з」∠)_
回复 支持 反对

使用道具 举报

OPPOTIDUS 发表于 2014-12-4 11:00:53 | 显示全部楼层
谢谢楼主了,祝工作顺利~
回复 支持 反对

使用道具 举报

peter8996 发表于 2014-12-4 11:54:42 | 显示全部楼层
pro 发表于 2014-12-4 10:34
在新的子串里重新扫……我面试的时候其实就是在纠结这个。我总觉得我可以用两个队列分别负责最大最小来实 ...

先恭喜lz! 鏉ユ簮涓浜.涓夊垎鍦拌鍧.

这样的话,复杂度会是N2嘛?
还有第一题,两个最后减号是怎么回事儿?-1?这题lz怎么做的,转成postfix么?
回复 支持 反对

使用道具 举报

 楼主| pro 发表于 2014-12-4 11:57:09 | 显示全部楼层
peter8996 发表于 2014-12-4 11:54
先恭喜lz!. 1point 3acres 璁哄潧

这样的话,复杂度会是N2嘛?

N^2*k吧……k是字典里最长的词的长度。. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
意思就是连续两个-的时候后面那个的意思其实是负号不是减……加减乘除后面都可以跟负数。这个情况分开来专门处理一下就好了。我是用两个栈,一个放操作符,一个放操作数和括号。

补充内容 (2014-12-4 11:57):
哦看错了还以为你说找词的那题……那个子序列的是N^2
回复 支持 反对

使用道具 举报

peter8996 发表于 2014-12-4 12:25:41 | 显示全部楼层
pro 发表于 2014-12-4 11:57. 1point3acres.com/bbs
N^2*k吧……k是字典里最长的词的长度。
意思就是连续两个-的时候后面那个的意思其实是负号不是减……加 ...

是啊,我还想哪儿来的字典呢。。。算式那个题,两个stack其实还是转成postfix了吧?但是省去了中间步骤,相当于on the fly了,如果我理解的对的话。。。总之多谢lz!祝工作顺利!
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-6 09:03

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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