微软面试题 - 未名空间MITBBS历史存档

k*t2016-03-06 08:03

1 楼

一次去微软面试, 面试官是一个老印的principal engineer, 问我的题目是如何绕圈打
印一个二维矩阵。我老老实实说了算法，写了代码。老印问复杂度，我说O(mn)。老印
说，那就是O(n2)。我说对的。老印追问能不能做到O(n)。我说不可能，因为n2个元素
每个都要至少访问一次，然后老印给了个解法，让我目瞪口呆……
他说你可以把二维矩阵里的数先存到一个一维矩阵然后遍历这个一位矩阵就是O(n)
算法了！

J*v2016-03-06 08:03

2 楼

这里没有说清楚，就是n表示的是元素的个数还是行数，属于交流问题。
但烙印这个解法是傻逼。

b*y2016-03-06 08:03

3 楼

只有我笑喷了吗

b*y2016-03-06 08:03

4 楼

这就别往下面了，以后要怎么交流。。。

M*62016-03-06 08:03

5 楼

哈哈哈…听上去很有道理，但是先把二维存为一维是不是又是个O（mn）呢…
;所以最后还是O（mn）+O（n）= O（mn）
[在 knut (Cute Knut) 的大作中提到：]
：一次去微软面试, 面试官是一个老印的principal engineer, 问我的题目是如何绕圈
打印一个二维矩阵。我老老实实说了算法，写了代码。老印问复杂度，我说O(mn)。老印
：说，那就是O(n2)。我说对的。老印追问能不能做到O(n)。我说不可能，因为n2个元素
：...........

C*n2016-03-06 08:03

6 楼

笑喷了。
你说都不用遍历了，存成一维怎样做到o(n)

【在 k**t 的大作中提到】

: 一次去微软面试, 面试官是一个老印的principal engineer, 问我的题目是如何绕圈打
: 印一个二维矩阵。我老老实实说了算法，写了代码。老印问复杂度，我说O(mn)。老印
: 说，那就是O(n2)。我说对的。老印追问能不能做到O(n)。我说不可能，因为n2个元素
: 每个都要至少访问一次，然后老印给了个解法，让我目瞪口呆……
: 他说你可以把二维矩阵里的数先存到一个一维矩阵然后遍历这个一位矩阵就是O(n)
: 算法了！

n*e2016-03-06 08:03

7 楼

这种问题不是很常见吗？以前被问过如何最快的从一维数组找到一个数。
我说必须O（n），因为至少每个元素要访问一遍吧，不然怎么比较。对方说可以更快。
我只好耐心的打个比喻说，这好比你拿着个名片去party找人，你只能一个一个问对吧。
傻逼面试官充满正义感的说到，可以log n, 先把数组转化成一个tree。我都没法往下
听了，操他妈屄的祖宗十八代加所有后代干死妈屄的老母。

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

: 笑喷了。
: 你说都不用遍历了，存成一维怎样做到o(n)

k*g2016-03-06 08:03

8 楼

你可以说，存hashtable里面还是O(1)了呢

吧。

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

: 这种问题不是很常见吗？以前被问过如何最快的从一维数组找到一个数。
: 我说必须O（n），因为至少每个元素要访问一遍吧，不然怎么比较。对方说可以更快。
: 我只好耐心的打个比喻说，这好比你拿着个名片去party找人，你只能一个一个问对吧。
: 傻逼面试官充满正义感的说到，可以log n, 先把数组转化成一个tree。我都没法往下
: 听了，操他妈屄的祖宗十八代加所有后代干死妈屄的老母。

A*d2016-03-06 08:03

9 楼

hahaha, this made my day!

【在 k***g 的大作中提到】

: 你可以说，存hashtable里面还是O(1)了呢
:
: 吧。

z*82016-03-06 08:03

10 楼

其实面试官说的没错

吧。

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

: 这种问题不是很常见吗？以前被问过如何最快的从一维数组找到一个数。
: 我说必须O（n），因为至少每个元素要访问一遍吧，不然怎么比较。对方说可以更快。
: 我只好耐心的打个比喻说，这好比你拿着个名片去party找人，你只能一个一个问对吧。
: 傻逼面试官充满正义感的说到，可以log n, 先把数组转化成一个tree。我都没法往下
: 听了，操他妈屄的祖宗十八代加所有后代干死妈屄的老母。

j*32016-03-06 08:03

11 楼

哈哈哈哈哈哈哈哈哈哈，我笑死了，，，，，，，不带这么黑大微软的哈哈哈哈

t*42016-03-06 08:03

12 楼

有没可能人家抛出一个负面观点，看看你怎么应对这种场合。
有时候我面试也会搞一个坑，看对方情商咋样
到底是无条件服从，还是情绪激动反驳，还是委婉指出错误

【在 k**t 的大作中提到】

: 一次去微软面试, 面试官是一个老印的principal engineer, 问我的题目是如何绕圈打
: 印一个二维矩阵。我老老实实说了算法，写了代码。老印问复杂度，我说O(mn)。老印
: 说，那就是O(n2)。我说对的。老印追问能不能做到O(n)。我说不可能，因为n2个元素
: 每个都要至少访问一次，然后老印给了个解法，让我目瞪口呆……
: 他说你可以把二维矩阵里的数先存到一个一维矩阵然后遍历这个一位矩阵就是O(n)
: 算法了！

q*t2016-03-06 08:03

13 楼

其实这个也是面试，只不过不属于技术面试
人家要面你的不是你的技术
而是看你怎么反应，考你的情商
在组内解决问题的时候肯定有不同意见，人家要看你是怎么处理的，其实就是看你好不
好相处

m*s2016-03-06 08:03

14 楼

我软躺枪

【在 k**t 的大作中提到】

: 一次去微软面试, 面试官是一个老印的principal engineer, 问我的题目是如何绕圈打
: 印一个二维矩阵。我老老实实说了算法，写了代码。老印问复杂度，我说O(mn)。老印
: 说，那就是O(n2)。我说对的。老印追问能不能做到O(n)。我说不可能，因为n2个元素
: 每个都要至少访问一次，然后老印给了个解法，让我目瞪口呆……
: 他说你可以把二维矩阵里的数先存到一个一维矩阵然后遍历这个一位矩阵就是O(n)
: 算法了！

R*42016-03-06 08:03

15 楼

这个面试官以前可能是做过嵌入式。
嵌入式有些就是这样。即使全部列出来。

g*c2016-03-06 08:03

16 楼

微软烙印水平真高！！！难怪公司作死路上走了

r*y2016-03-06 08:03

17 楼

O(mn)跟O(n2)完全是两个概念，你当时就不应该说对。他估计是误解你最初的做法了，
他应该始终就认为n是元素个数的。我觉得是交流问题。

c*z2016-03-06 08:03

18 楼

Why would you want to test that? Is that the common case working with you?

【在 t******4 的大作中提到】

: 有没可能人家抛出一个负面观点，看看你怎么应对这种场合。
: 有时候我面试也会搞一个坑，看对方情商咋样
: 到底是无条件服从，还是情绪激动反驳，还是委婉指出错误

L*k2016-03-06 08:03

19 楼

这是杀敌八百自损一千的面法。忍辱负重承担着面完别人在背后骂傻叉的臭名，也要测
测 candidate的 soft skill，真是好面试官，为公司招人才不拘一格啊！

【在 q*****t 的大作中提到】

: 其实这个也是面试，只不过不属于技术面试
: 人家要面你的不是你的技术
: 而是看你怎么反应，考你的情商
: 在组内解决问题的时候肯定有不同意见，人家要看你是怎么处理的，其实就是看你好不
: 好相处

j*72016-03-06 08:03

20 楼

我的经验是：老中想拒你，就提高问题的难度；烙印想拒你，就提高问题的荒诞度。

M*i2016-03-06 08:03

21 楼

lz可以淡定地说，他是对的。不过你前面估错了，应该也是o(n). 看烙印啥反应。
如果这样都不行，趁早不要去那里工作。

t*42016-03-06 08:03

22 楼

因为情商低的很难共事啊，情绪激动的那种真的还是算了吧

：Why would you want to test that? Is that the common case working with you?
：彪悍的人生不需要解释

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

: Why would you want to test that? Is that the common case working with you?

k*e2016-03-06 08:03

23 楼

这跟嵌入式有啥关系

【在 R*********4 的大作中提到】

: 这个面试官以前可能是做过嵌入式。
: 嵌入式有些就是这样。即使全部列出来。

w*52016-03-06 08:03

24 楼

然后你咋回答他的呢？还是直接被shock得不省人事了？

【在 k**t 的大作中提到】

: 一次去微软面试, 面试官是一个老印的principal engineer, 问我的题目是如何绕圈打
: 印一个二维矩阵。我老老实实说了算法，写了代码。老印问复杂度，我说O(mn)。老印
: 说，那就是O(n2)。我说对的。老印追问能不能做到O(n)。我说不可能，因为n2个元素
: 每个都要至少访问一次，然后老印给了个解法，让我目瞪口呆……
: 他说你可以把二维矩阵里的数先存到一个一维矩阵然后遍历这个一位矩阵就是O(n)
: 算法了！