Microsoft 2题面经 - 未名空间MITBBS历史存档

国际科技财经博客移民网络热点娱乐民生时事公众号

Redian新闻

>未名空间

>JobHunting - 待字闺中

Microsoft 2题面经

Microsoft 2题面经# JobHunting - 待字闺中

b*12017-09-21 07:09

1 楼

感觉难度不亚于G
第一题
2D matrix 1D形式的transpose O(1) space.
比如 [1, 2, 3, 4, 5, 6]表示
[1, 2, 3]
[4, 5, 6]
转置后
[1, 4]
[2, 5]
[3, 6]
返回
[1, 4, 2, 5, 3, 6]
完全不会
第二题 convex hull
勉强写了code
但是面试官都是manager级的，说convex hull的时候她们也不太懂，不知道想什么

H*52017-09-21 07:09

2 楼

那就是说bar都增高了呗，坑少了。

z*n2017-09-21 07:09

3 楼

感觉软家题目一直都不简单，但是他家好像你答个80分就过，一线的得答个95才过。上
回面他家出了个矩阵乘法，那个算法早就忘了，最后naive for循环做的，也过了。

W*o2017-09-21 07:09

4 楼

软家那么多team/group，而且又没有固定题库，我觉得难度比FB这种有题库的，光从题
目难度本身来看要难一点；
但是他们面试的侧重点不太一样，软家好像考察思路和交流更多一点，FB这种要求bug
free更高；
面fb，只要lc刷了前300题，再多看看面经，之后就看表演技术和运气了，呵呵

f*n2017-09-21 07:09

5 楼

lol。思维过程---都不需要了这是。

【在 z*********n 的大作中提到】

: 感觉软家题目一直都不简单，但是他家好像你答个80分就过，一线的得答个95才过。上
: 回面他家出了个矩阵乘法，那个算法早就忘了，最后naive for循环做的，也过了。

z*n2017-09-21 07:09

6 楼

你正好练练呗，就做做naive矩阵乘法，20分钟，看看能不能bug free？

【在 f*****n 的大作中提到】

: lol。思维过程---都不需要了这是。

f*n2017-09-21 07:09

7 楼

并不去微软。

【在 z*********n 的大作中提到】

:
: 你正好练练呗，就做做naive矩阵乘法，20分钟，看看能不能bug free？

t*r2017-09-21 07:09

8 楼

第一题算个公式出来就可以了...

z*n2017-09-21 07:09

9 楼

还能这么操作？你上段代码，或者跑个例子看看？

r*s2017-09-21 07:09

10 楼

如果不考虑运行时间的话（时间换空间，基本是平均 O(N^4) )
以下不是人话讲解，不用纸笔比较麻烦。。。
那么对于每一个点，沿着其置换群走一圈，肯定回到该点，第一次走的时候先看该点是
不是置换群中最早的一个点。如果是就可以再走一遍进行置换。举例子来说，题目中的
1 2 3 4 5 6 -> 1 4 2 5 3 6
1一看直接换成1，这个不说了
处理到index = 1的时候不断算当前元素应该置换到什么位置，可以得知
2->3->5->4->2的下标(1->2->4->3->1)形成一个置换群，而
2所在的位置idx=1是最早的
一个，所以做一次置换，形成
1 4 2 5 3 6
然后再到下一个idx=2,一看这不是置换群中第一个元素，那么就不进行置换，直到6.
也就是说，WxH->HxW, idx -> idx%W*H 加 idx/W
如果能证明这个变换总是先增后减（我直觉上是，正在找规律），那么O(1)时间可以知
道当前idx是不是一个置换群的第一个元素。则马上可以降低复杂度到N^2
(找到反例了。。。 4x7 idx=2 : 2->14->17->11->23->26->20-&
gt;5->8->2)增减若干次，所以每次必须重新判断。。。
妈的，这道题是十年前我面试MSRA的时候manager给我出的题，时隔这么多年终于破案了
突然有一种茫然的感觉。。。妈的。。

: 还能这么操作？你上段代码，或者跑个例子看看？

【在 z*********n 的大作中提到】

:
: 还能这么操作？你上段代码，或者跑个例子看看？