微软Microsoft面经集锦

onsite 2019/4
微软 五轮 :

  • 第一轮国人, 全程中文, 出了一道linked list, 找倒数第n个list node,

1 -> 3 -> 4 -> 5,   n = 1; 返回4, 秒做完, 老哥说他没怎么面人,没准备别的算法题,就面个设计题, 设计一个Google map…

      2.  第二轮面试,manage 面试问了很多简历经历,然后 find longest palidrom substring, 按小班讲的写dp方法,   dp represent, induction rule, base case, result, filling order, optimize讲完没让写code就过了, 看起来很满意。

     3  第三轮,find number of island I, and II.  常见题型, 前两周复习过图,写得也很快。

     4  第四轮, binary tree post order iterator,  聊简历

     5 第五轮 , 这个题是真实遇到的工作中的问题。 他手下有两个组, 每个组都给bing引擎写一个算法,第一组的人的算法,对长度为一的search key word 效果最好, 有90分,但是对长度为二的 search key word效果不好只有30分,第二组的算法对长度为一的效果30分, 但是长度为二的90分,找出一个方法, 可以让某些search key word用第一组的方法,某些用第二组的方法, 但是这些长度要连续, 例如
            长度:  1             2           3            4
第一组 :       30            60         60          30
第二组 :       90            30         30          90
这个例子中就要返回2 到3, 就是2到3这个范围用第一组的算法,  2 到 3必须连续,

我想了想可以用第一组的分数减去第二组的分数, 得到一个array,题目就变成了largest subarray sum.   又是一道dp.


总体感觉微软面试中等偏难, 需要很多小班知识, 内容不会超过小班范围, 也很重视交流,交流的好不用写code。 很多behavior questions,回答的时候一定要牵扯leadership principle,
这次反馈的note上写我爱学习新东西, 对自己项目负责等等。。


onsite 2019/1
MSFT
第一轮  bq 修bug的经历;给c type string 返回大小;给一个string 返回中间的字符;(忘记这两个是设计api还是方程);设计transcrpt audio的api;

第二轮  permutation 好像无bq

第三轮  bq 职业规划 why MS;meeting room ii

第四轮  bq 看我学的是ee,问我cs的这些技能在哪里学的;题是有n个娃娃 给一个数组是他们的价格,都是整数,现有买1赠k的活动,让写个函数,求最多花多少钱把娃娃都买走,最少花多少钱买走,活动必须参加;写完后然转换成api

OA
3 Qs, text editor, no testable,
1 - sort color (varied); 2 - fix bug - rotate array to right by N;3 - print integer vertically (with no char or string manipulation) -- 额 当时没记清这个题 现在看也不记得第三题是啥了 总体感觉非常基础


Microsoft 30min on campus
project description
1. Tell me what you know about MS and our products
2. What are the features that make you love OneNote, and how will you improve OneNote if you are working with OneNote Team?
3. How do you define BAD CODE?
4. If you and your team are working on a project, what would you do with your team?
5. Tell me a Computer Science concept that you are interested in
  6. Ask me

10/2018 Senior Position
闫老师MS面经来啦,万万没想到是最难的 但应该也不成问题 1 read4II multiple calls 还要thread safe 2. copy graph with random pointer, reformat Hex file to readable file. 3. Typeahead 整个system怎么部署 cache放在哪里 讨论LRU是怎样实现的 以及tire insert/search 写代码 4 HM问了factory design pattern [捂脸] 解释清楚之后还要写代码 然后把项目问的特别特别细 我说的时候一直打断我 问到底用了什么技术 为什么这样……

09/2018
Sep 7 Hiring Event Onsite
8:00 AM to 12:00 PM, 一共四轮,每一轮45分钟。每一个面试官都会在15分钟的休息时间给下一个面试官feedback,后面的面试官会根据前面的feedback选择面试侧重点。

第一轮白人大叔,先问了一些BQ,然后问了SQL和NOSQL的区别,extends和implements的区别, design pattern和应用以及function overriding
Coding: 打印一个带环的有向图。我是用DFS(recursion)解的,面试官想的是BFS,我写完DFS又说了BFS。面试官follow up了recursion的缺点,答stackoverfollow, 改进方法是自己maintain stack。继续follow up了还有什么缺点?答mapreduce不方便。

第二轮国人大姐,也是先问了一些简历和BQ,coding merge 2 sorted linkedlist,秒。接了一个sys design相关的,问一个distrubuted的系统如果忽然变慢会有哪些可能性和解决方法。

第三轮印度manager,迟到5分钟。简历过了5分钟,让我在白板上列举出angular 和 react的各自优缺点,(angular主要的缺点就是heavy weight,不如react自由),并告诉我他们正准备从angular过渡到react。接一个system design:设计一个问卷调查系统,这个系统的问题用户可以自己创建,也可以从question bank自选,每个问题可以expand成细分的小问题,然后这些问题可以群发给用户,并且这些问题可以save 到一个question bank。设计完DB之后,面试官说就到这里把,然后问了一些BQ,感觉这一轮面的不太好。

第四轮印度大哥,设计netflix,秒。接BQ。

6/2018
Roud1 白人男:

deep copy Linked List with random pointer,

首先bf,把原数组过一遍,每个node生成一个copy,再过一遍,把copy的next和random连一下,用map记录原节点和copy的结点。

优化,在过原list第一遍的时候就判断下next和random节点有没有生成过,有的话直接从map里面拿出来并且把cur在map里的镜像节点连上next copy和random copy,没有的话生成一个再练然后放入map里面。一遍过,问我如果random pointer,是链接自己怎么办,我说一样的work,他问了我一些case,感觉都覆盖了就没问题了。

Round2 印度人女:

两个list,list1有一部分排序好的数字,剩下的只是空位,空位的数量刚好等于list2的元素的数量,排序好的数字在list1前面。list2是排序好的数字,没有多余空位,让你返回一个排好序的数组包含这list1,list2的所有数字。她说她想听我的所有思路。

bf: 把list2的数字直接加在list1的后面,然后排序

sol2: 谁小移谁,把结果丢进新数组里面返回,时间降低,空间变高

sol3: 把array1的元素移动到右边部分,和array2的元素谁小移谁,把结果从array1的头部开始填。这样空间和时间都优化了。

实现了这个代码,然后问我需要先移动到右边吗,我说不用,改成谁大移谁就好,改了code,很满意。问我如果不让我把array1的valid number的个数做为参数传进来,怎么办,和她确认了空位其实是null,把array1改成了Integer[],  问我怎么知道array1valid number的个数,我说用既然确保valid number都集中在数组最左边用binay search就好。问了我怎么测试代码,说先检查输入的valid,再看算法的valid,和她说了几个case,她很满意就走了。

Round3 白人男:

问项目,他对我的项目很满意,说应该写在简历上,10-15分钟。

把string转换float,和他花了好长时间把所有能想到的case都想到了,就是合理的输入。然后实现,left num和right num, left num是小数点左边的数,right num是小数点右边的数,判断下如果我们原来找到过小数点就把结果累加在right num,否则加在left num上。最后写了个bug,走了个例子,如果我们前面的boolean isPositive是false,那就应该转换成负数。最后问我代码优化,我说不用right num就好,他还问有什么优化,我说先不考虑小数点,全当整数的法则运算,最后再乘以Math.pow(10, -(array.length - 小数点的位置))就好。他说math.pow的时间复杂度太高了,然后他说了自己的做法就是累乘0.1就好,再小数点右边。改了我两个代码上的nit,不是错误,可能更适合他的代码风格。

Round4 白人男:

干了17年,是个经理级别,开头问了我些问题,我说我直接背景介绍吧,和他介绍到我那个项目,他说某某面试官和他说过了,我问了他你是怎么小组间合作的,他画了层级图,我才知道他是经理级别的。

题目是扑克牌,有两个人每个人手上有五张牌,叫你判断问你谁赢。他在说问题的时候,特意说这个题目其实很难,我只关注你problem solving的过程,代码怎样无所谓。

问我玩扑克吗,我说几乎不玩。题目不考虑花色,只考虑大小,每张牌范围在1 - 13。

规则一,如果两个人每个人五张牌的value都不一样,则比较那张最大的。
规则二,如果两个人有个人有两张牌是一样的,而另一个人的五张牌都不一样,则有两张牌一样的人获胜。
player1: [1,1,3,4,5] player2:[2,3,4,5,6] player1获胜
player1: [1,1,3,4,5] player2:[2,2,4,5,6] player2获胜,因为player2也有两张牌是一样的并且2 > 1
player1: [2,2,3,4,5] player2:[2,2,4,5,6] payer2获胜,两个各有两张2,所以只比较 单只里面值最大的
player1: [1,1,3,5,5] player2:[2,2,4,5,6] player1获胜,play1有两个5

规则三, 出现了三张一样的牌

player1有三张一样的牌,player2 length of the subarray which has the same number is <= 2, player1 wins,不用管player1那三张牌的大小,player1直接就赢了。

player1 and player2 both have the subarray which has the same number and its length is 3. the one with the biggest value wins if there is a tie, use the rule2 to check, if still a tie, use rule1 to check.

规则四,出现了四张一样的牌,

和前面的说明一样。


bf解,就是player1有四个bucket, player2有四个bucket,bucket, 表示的是出现了i次的所有的value(如果value出现了i次就放到这个bucket里面)。这里我记不清是四个还是五个bucket,面试官的意思是不那么重要。

player1: bucket1 bucket2 bucket3 bucket4

player2: bucket1 bucket2 bucket3 bucket4

都从尾部开始扫,如果有个人bucket是空的,对方的bucket里面有值,则有值的获胜,如果都有值,看看谁最大,如果是个tie,找第二个大,一直往下找,如果这两个bucket里面都是一样的,就换到bucket[i - 1]里面继续看,如果实在不能分出胜负就返回0(tie),否则返回player的id。


更好的解法,谁当前输了就移动谁

2wins up to now, using the rule1, and number is 3
nums1: [1,2,3,4,5]
              i

nums2:[3,4,5,7,9]
             j





2wins up to now, using the rule1, and number is 3,
nums1: [1,2,3,4,5]
                 i

nums2:[3,4,5,7,9]
             j
after we move pointer1, 2前面没有与它相同的数字所以只能按rule1比较,还是输


tie, using the rule1, and number is 3,
nums1: [1,2,3,4,5]
                     i

nums2:[3,4,5,7,9]
             j
这个随便移动哪一个

。。。。


2wins up to now, using the rule1, and number is 9,
nums1: [1,2,3,4,5]
                              i

nums2:[3,4,5,7,9]
                         j
因为1已经移到边界外了,直接返回2赢了

另一个example:

当前是player1 win, using rule 2, number is 3

nums1: [3,3,4,5,6]
                 i

nums2:[2,2,5,7,9]
                 j
...................

当前是player1 win, using rule 2, number is 3

nums1: [3,3,4,5,6]
                          i

nums2:[2,2,5,7,9]
                          j

这里还是player1赢了,虽然9比6大,但是9没有连续的


这种解法面试官举了个反例,没有考虑到就是如果某个高等级的rule出现了tie这种情况,应该去考虑次一等级的rule,我当时头晕了,漏了这个地方,面试官说可能要trace back了,我说最brute force的办法是把tie的去掉再走一遍。

最后面试官说没事就是想看看我解决一个全新问题的思路和出发点。他的意思是他也没有标准答案。说我从brute force的bucket那里出发点很好,想走一遍过的思路也和不错。他说其实扑克里面还有别的rules,我说这样的话我们的思路和出发点完全就不能这么考虑了,他也完全认同。



他说这个问题比较难,市面上有很多solver都在尝试解决这个问题,我说我其实有很多思路,只是时间原因来不及一一验证,我说我回去写个论证发到您邮箱吧,他同意了,然后给了我个邮箱。这轮一直在讨论过程


2018/2
Microsoft:
1. Topo sort
2. For a given matrix, find the number appears in all rows
Follow up: use only one data structure and do it in O(m * n)
3. Top K frequency words
4.1 For a list of integers (size is n), if all the integers belong to a range [0,m), sort it in O(n)

Answer: bucket sort

4.2 For a given array, each cell contains a pair <ID, data>, ID is an integer and data size is unknown. ID falls into range [0,m). Sort the array by ID with Time Complexity O(n) and Space Complexity O(m)

Answer: use bucket sort to calculate a range for each id, and use swap to move each row into desired row group

2018/2
1月26号面了MS, 但是最终没有offer。有些面经之前把面经发地里了, 后知后觉发现应该回报下lai offer一同奋斗的同学,后来又整理了一下,去掉了些没用的内容,详情如下

附件中 201801-MS-OTA-总结 和 201801-地里面经 是我之前准备时整理的一点面经。

Onsite 一个月前面的,已尽力回想整理了。
1. 这轮是楼主挂的一轮,一个欧洲小哥,没聊好,介绍了一堆楼主不太了解的network底层的东西。BQ也没答好,可能从东岸飞过去,早上8点面试人还不清醒。。。
题目大概是一个后端服务器throughput是有限制的,前段服务器会发超过这个限制的请求进来,问怎么handle。楼主以为是设计题,扯了一堆scalability如kafka,增加服务器什么的,结果最后小哥的意思是。。。别跟我扯犊子,不能handle drop掉额外的就行了。。。有点出乎意料。然后实现代码时也被揪出了2个错误。。。当时就知道gg了。
2. 欧洲大哥,后来hr说是级别最高的。 聊的不错,大哥很满意,题目是给dict, 给string,找string中的是正确单词所有的anagram,用的permutation。 follow up,实现字典查词的功能,用的trie(只解释,没有写)。follow up,第一问不用permutation怎么做,用hashmap count字符出现次数。
3. 不知道哪里的小弟,中东?。找数组中的peaks,比如132, 3就是peak其中一个peak。 说了O(n)的解法,不满意,要提供O(lgn)解法。 整了半天没整太明白,先写了O(n)的。 写完又说了下lgn的解法,merge的思路。
4. 印度大哥。次senior的面试官。链表压平输出, 图的topo排序。很多时间在聊天,聊的“比较happy”。这一轮扯的比较多,扯了bq,扯了楼主背景,扯了老印自己一堆经历。最后送楼主到门口握手离开。

HR反馈
1. 第一轮答的不好。
2. 第二轮答的最好。这轮楼主写的比较多,聊的也不错,扯了下楼主正在做东西的一些背景。
3. 第三轮代码写的不错但是lgn解法没写出来,多中肯的feedback。。。我也知道没写出来阿,这轮应该可以答的更好。
4. 第四轮反馈不好不坏。

自己感觉,跟我联系的hr onsite前还电话我说没有bq,说ms是科技公司,上去就是code,实际发现其中3轮bq的时间还挺长的,大概都在15到25分钟之间。每轮面试45分钟,到了有人来提醒面试官,然后基本立马就收场准备走, 只有一轮稍微拖了5分钟。

on campus
projects
conflict with team mates
selling and buying stock one transaction
production web service完全不懂


Round 1:
Behavior: discuss your impact in your current project.

Algorithm:
Given an unsorted array of size n, all the elements are guaranteed to be within the range [0, n], but there may have duplicate elements in it. Find an integer x, so that the total number of elements smaller than x and larger than x in the array are closest.

Present as many solutions as you can.

follow-up: need to be done in time O(nlogn) and space O(1)

Round 2:  
Algorithm:
Q1: Leetcode 171. Excel Sheet Column Number
Q2: 168. Excel Sheet Column Title
Q3: Suppose we have a small team with odd num of members, and we have a task timeline with odd num of tasks. We want to find out a schedule for all the team members so that all the members can finish their tasks as soon as possible and we could go out for a team lunch. For example,

We have 3 people, and the task timeline is [4, 1, 13, 5, 6, 8], each num here means how much time (you can think it as minutes) each task can be finished.

behavior: Why Microsoft and XX team?


Round 3:

behavior: Biggest challenge in your previous work experience

Algorithm:
Given the list head of an input list of characters which represent a sentence, reverse each word inside the list. You need to do it in place.

For example: M -> Y -> ' ' -> N -> A -> M -> E -> ' ' -> I -> S -> '' -> J -> H -> O -> N, the result should be

Y -> M -> ' ' -> E -> M -> A -> N -> ' ' -> S -> I -> ' ' -> N -> O -> H -> J

+++++++
clarify question need to be asked
Do we have leading whitespace chars or the end of the list? Or maybe white space between each word is not only one, maybe two or more.


Round 4:

Algorithm: Basketball match
Given two score timeline represent our team and another team individually, find the time range that our team wins most. For example
Time
              0     1    2    3   4   5   6
our team:           3         6       2
other team:   2          2        7       10

then we have the time range 1 to 3 which we have the most win or our team for score 7.

new grad - CDN onedrive
Microsoft面经:
8/23 内推
8/26 phone
9/18 onsite
9/22 offer letter

azure network 组
phone interview: abc小哥,大致聊了简历上的内容,题目是remove kth node from end 和 力特扣得 642 design autocomplete search
onsite: 第一轮: 东欧manager 面得是时针分针夹角,后来就考了system design,如果有一个只能处理100个request得database,防止黑客攻击,该怎么办
            第二轮: 美国小哥,问了问简历,开始考coding。number of digit 4 less than int n。 corner case真的很多
            第三轮: 印度manager,考了3 sum变种
            第四轮: 中国manager, 考了图的克隆
            第五轮: manager说四轮都是strong hire 所以直接给了口头offer


code review
topological order
throttling system design


Text Editor:
Actions we want to support for undo are:
- character added/removed to the text
- color for one or more characters
Color is achieved using Graphical resources like brushes, which needs to be released
I want you to:
- describe the design you would use to implement the undo functionality
- describe how you would organize the actions
- describe how would you design your actions in such a way a developer not familiar with your code hasn't to worry too much about releasing resources


输入php代码,key是class name,value是method name
还会有global method
遇到的最大的bug是什么
微软4轮 - 前两轮不好
90旋转 - 只做了一题

是否是anargram不能用HashMap -
missing number - HashMap实现
number of island 8个方向 bfs+dfs
找String里面有多少个palindrome - dp
骑士 start - destination最少步数 - bfs
map是无限延伸的地图,如何生成障碍物
corner case讨论 - 都被障碍物block,bi-direction
dfs能不能做

计算多少个单词,两个单词之间有多个空格,头尾空格
combine空格,再数空格
2 sum分布系统设计,看重customer,session,怎么得到客户需求,space可以很多calculation不够resource,提示用map reduce,pseudo code
battleship 游戏,生成board,behavior聊久,
实现malloc,给了data structure,table-resourceId,起点,size,整个内存的byte array,free函数,

--------------
以下是我的软软面经
1.SDE
B: An example that you initiate a project or bug fix by yourself.
C1:reverse+merge two sorted linked list
C2:Maximal Rectangle of 1s in a matrix
2.SDE
B:How to learn a new thing?
C1:Boundary Traversal of binary tree
D1:How to make a aggregation query more efficient?
3. manager
C1:Convert a real-world problem to a computer problem(Combination Sum II)
4. manager
B: what you have learned from your previous project?
D1esign a cooking robot
C1eep copy random linked list
5. Senior manager
B:Conflict with teammate / why microsoft/ what do you want to be in 3-5 years/ how to learn a new thing


标签: 暂无标签
Swervin

写了 124 篇文章,拥有财富 2,被 0 人关注

转播转播
回复

使用道具

您需要登录后才可以回帖 登录 | 立即注册
B Color Link Quote Code Smilies

成为第一个吐槽的人

返回顶部