一亩三分地论坛

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

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

microsoft onsite面经热腾腾出炉

[复制链接] |试试Instant~ |关注本帖
lyc1994 发表于 2016-10-20 23:55:53 | 显示全部楼层 |阅读模式

2016(10-12月) 码农类 硕士 全职@Microsoft - Other - Onsite |Otherfresh grad应届毕业生

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

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

x
LZ十月十八号刚面的Microsoft,感觉他们家的题目会很多涉及到design,以及有些问题虽然看上去简单但需要仔细思考。一共五轮,午饭二十刀,细节与其他面经帖都一致,组是office 365组.鏈枃鍘熷垱鑷1point3acres璁哄潧
1.东欧或俄罗斯大叔,问题是给一串数,找出相减不同于其他的那对pair,例如:
1, 3, 5, 6, 8, 10, 12,应该返回(5, 6),这道题LZ折腾了很久,一开始用暴力解法做的。正确做法是首先找到前两对pair,在这个例子里面就是1,3,5,如果他们做减法相等,说明我们找到了正确的pattern,然后用Binary search 找到不正常的。如果不相等,那么说明这两对pair间一定有一对是不正常的,找到那一对即可。
2.白人大叔,设计一个出text editor的undo与redo功能,使用两个stack,并将用户的operation放到stack里,用户的operation应该建立一个类,有三种操作类型,add, delete, replace
3.白人老大爷,说已经在微软工作二三十年,当时刚开始工作的时候还是用assembly language,题目是设计数据库,有用户,文档,permission,用户对文档可以有read 与write操作,设计query判断某个用户是否有权限访问某个文档,比较简单,follow-up是引入directory,意思大概是如果一个用户对某个文档没有权限,但是对这个文档的母文件夹具有权限,那么对这个文档也可以具有权限,解决办法是在file table中加入一个parent id entry,循环向上一层找是否有权限(这边逻辑很奇怪)-google 1point3acres

鏉ユ簮涓浜.涓夊垎鍦拌鍧. 4.三姐,问题是常见的压缩string, "xxxhhhj" -> "3x3hj",不过LZ答得也不是很好,交流了很久
5.白人大叔,让设计个microsoft word, LZ的内心是崩溃的,不是说最后一轮是面Boss, 谈笑风声的吗?要求用户可以快速输入text,改变某一段text的format,加粗变斜等等,以及实现search功能,实现应该是用一个deck(Linked List加char array,每个ListNode是指向char array的指针),所以用户在中间插入的时候,可以通过增加一个ListNode与一个char array实现。

大米,原来发帖都有大米求问现在怎么没了?
LZ之前找实习找工作都从一亩三分地收益很多,感谢愿意承担风险发帖的坛友们,以后也会尽量发我的面经贴。

. From 1point 3acres bbs





补充内容 (2016-10-29 23:12):
10/27 收到offer, office 365组

评分

3

查看全部评分

 楼主| lyc1994 发表于 2016-10-31 12:06:23 | 显示全部楼层
aimingnetwork 发表于 2016-10-31 04:55
请问楼主 那种design 之类的问题你是怎么准备的啊, 有没有经验可以分享 感激不尽!
估计一个月后on site  ...

这些design LZ其实都没有准备过,undo stack 和redo stack是以前上课自己实现过,另外那个design microsoft word也是当场自己想的,感觉他们家并不需要立刻想出最优解,可以一步步与面试官讨论
回复 支持 1 反对 0

使用道具 举报

 楼主| lyc1994 发表于 2016-10-22 00:19:14 | 显示全部楼层
say543 发表于 2016-10-21 14:28. 鍥磋鎴戜滑@1point 3 acres
第三轮 需要设定database schema 吗? 像是 user table, file table 还有relational table 等等 follow up  ...

嗯需要建立三个table: user, entry(包括file与directory) 和permission,follow up 应该只需要在entry table里面加入parent id, 是母目录的id。第五轮其实我直接说的LinkedList,因为没有写code,所以很多细节没有考虑,这里用linkelist确实没办法O(1) insert,不过O(N/k)(k是char array)的长度应该可以。
回复 支持 1 反对 0

使用道具 举报

龙威不改 发表于 2016-10-21 04:08:57 | 显示全部楼层
楼主你好 想问问第一轮那个 做二分的时候怎么样算是遇到不正常的?
回复 支持 反对

使用道具 举报

 楼主| lyc1994 发表于 2016-10-21 04:34:42 | 显示全部楼层
龙威不改 发表于 2016-10-21 04:08
楼主你好 想问问第一轮那个 做二分的时候怎么样算是遇到不正常的?

例如之前的例子,我们已经知道2是正常的pattern,那么将array分为两部分,0-3 与 3-6,array[3] - array[0] = 6 - 1 = 5 不等于pattern * 3,所以不正常的部分肯定在0-3里面
回复 支持 反对

使用道具 举报

say543 发表于 2016-10-21 14:28:50 | 显示全部楼层
第三轮 需要设定database schema 吗? 像是 user table, file table 还有relational table 等等 follow up 的想法 是file table 跟directory path 在建relation table?  第五轮  Linkedlist<char []> 我猜楼主说的是一个双向linkedlist 问题是 这样没办法直接o(1) 到要insert 的地方 ? 因为cursor 因该是可以直接locate 到一个定点呗?
回复 支持 反对

使用道具 举报

xiaozhuxiaozhu 发表于 2016-10-21 14:54:26 | 显示全部楼层
第4题,需要in place的那题?
回复 支持 反对

使用道具 举报

lidafu 发表于 2016-10-21 23:17:55 | 显示全部楼层
原来考那么多数据结构的,感谢lz
回复 支持 反对

使用道具 举报

 楼主| lyc1994 发表于 2016-10-22 00:11:22 | 显示全部楼层
xiaozhuxiaozhu 发表于 2016-10-21 14:54
第4题,需要in place的那题?

对的,需要in place
回复 支持 反对

使用道具 举报

assq 发表于 2016-10-22 01:29:49 | 显示全部楼层
lyc1994 发表于 2016-10-22 00:11
对的,需要in place

lz问下输入是string还是char*哇
回复 支持 反对

使用道具 举报

 楼主| lyc1994 发表于 2016-10-22 05:18:29 | 显示全部楼层
assq 发表于 2016-10-22 01:29
lz问下输入是string还是char*哇

输入是一个char array,函数是void不返回东西
回复 支持 反对

使用道具 举报

xiaozhuxiaozhu 发表于 2016-10-22 05:37:04 | 显示全部楼层
lyc1994 发表于 2016-10-22 05:18
输入是一个char array,函数是void不返回东西
鏉ユ簮涓浜.涓夊垎鍦拌鍧.
你怎么做的,可以分享下么。
比如abcc, 这种。
回复 支持 反对

使用道具 举报

edisonhua 发表于 2016-10-22 05:40:33 | 显示全部楼层
请问lz电面是一轮嘛?难不难呀是不是主要注重cultural fit?
回复 支持 反对

使用道具 举报

 楼主| lyc1994 发表于 2016-10-22 08:18:56 | 显示全部楼层
xiaozhuxiaozhu 发表于 2016-10-22 05:37
你怎么做的,可以分享下么。
比如abcc, 这种。

我的方法挺简单的,就是维护一个current char和一个count,然后扫一遍,array如果与current char不同,就把count和current char写到char array里面,array如果与current char一样,则count++。

补充内容 (2016-10-22 08:19):
有Bug, array[j]
回复 支持 反对

使用道具 举报

xiaozhuxiaozhu 发表于 2016-10-22 08:20:49 | 显示全部楼层
lyc1994 发表于 2016-10-22 08:18
我的方法挺简单的,就是维护一个current char和一个count,然后扫一遍,array如果与current char不同,就 ...

谢谢回复。
这个方法,是没有办法handle, abcc, 或者abcdefgtttttttttttt这种例子吧?
回复 支持 反对

使用道具 举报

 楼主| lyc1994 发表于 2016-10-22 08:21:08 | 显示全部楼层
edisonhua 发表于 2016-10-22 05:40
请问lz电面是一轮嘛?难不难呀是不是主要注重cultural fit?
. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
我是intern on campus 过了后来说招满了没给onsite,全职就直接给了onsite
回复 支持 反对

使用道具 举报

 楼主| lyc1994 发表于 2016-10-22 08:25:34 | 显示全部楼层
xiaozhuxiaozhu 发表于 2016-10-22 08:20
谢谢回复。
这个方法,是没有办法handle, abcc, 或者abcdefgtttttttttttt这种例子吧?
. From 1point 3acres bbs
为什么不能够handle这些例子?
回复 支持 反对

使用道具 举报

xiaozhuxiaozhu 发表于 2016-10-22 09:37:35 | 显示全部楼层
lyc1994 发表于 2016-10-22 08:25
为什么不能够handle这些例子?

abababccccccc
你in place的话,
变成1a, 这时候a,占据了原来b的位置。。
回复 支持 反对

使用道具 举报

 楼主| lyc1994 发表于 2016-10-22 11:36:04 | 显示全部楼层
xiaozhuxiaozhu 发表于 2016-10-22 09:37
abababccccccc
你in place的话,
变成1a, 这时候a,占据了原来b的位置。。
. 1point3acres.com/bbs
对我一开始这样写是有问题,后来我想出的解决办法是先把char array扩展到原来两倍长度,然后从后往前扫,避免位置冲突,最后前面没有用到的部分再删掉。不过三姐后来说一个字母还要加一个数字的话达不到compress的目的,让我转换成abab7c这样的格式就行了。。
. 鍥磋鎴戜滑@1point 3 acres
补充内容 (2016-10-22 11:41):. 1point 3acres 璁哄潧
或者先扫一遍求得需要的总长度,那样可以不需要之后再删除了

评分

1

查看全部评分

回复 支持 反对

使用道具 举报

xiaozhuxiaozhu 发表于 2016-10-22 11:42:42 | 显示全部楼层
lyc1994 发表于 2016-10-22 11:36
对我一开始这样写是有问题,后来我想出的解决办法是先把char array扩展到原来两倍长度,然后从后往前扫, ...

你把char array扩展到原来2倍,就不是in place了。
等于开了以个新的 char[] 长度为n。
这题可以in place做,就是麻烦点。
.鏈枃鍘熷垱鑷1point3acres璁哄潧
补充内容 (2016-10-22 11:44):.1point3acres缃
每次遇到ab这种类似的情况,开始往后扫,用借位的思想。不过,我也不太清楚,这题出的是有啥意思。。
回复 支持 反对

使用道具 举报

 楼主| lyc1994 发表于 2016-10-22 11:52:11 | 显示全部楼层
xiaozhuxiaozhu 发表于 2016-10-22 11:42-google 1point3acres
你把char array扩展到原来2倍,就不是in place了。. From 1point 3acres bbs
等于开了以个新的 char[] 长度为n。.鏈枃鍘熷垱鑷1point3acres璁哄潧
这题可以in pla ...

感谢加米!借位是个什么意思?不过如果结果得到的char array比原来的长,那就无法in place,一定需要增加长度了
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-11 03:07

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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