k**t
发帖数: 35 | 1 一次去微软面试, 面试官是一个老印的principal engineer, 问我的题目是如何绕圈打
印一个二维矩阵。我老老实实说了算法，写了代码。老印问复杂度，我说O(mn)。老印
说，那就是O(n2)。我说对的。老印追问能不能做到O(n)。我说不可能，因为n2个元素
每个都要至少访问一次，然后老印给了个解法，让我目瞪口呆……
他说你可以把二维矩阵里的数先存到一个一维矩阵 然后遍历这个一位矩阵 就是O(n)
算法了！ |
J*****v
发帖数: 314 | 2 这里没有说清楚，就是n表示的是元素的个数还是行数，属于交流问题。
但烙印这个解法是傻逼。 |
b*******y
发帖数: 2048 | |
b*******y
发帖数: 2048 | |
M***6
发帖数: 895 | 5 哈哈哈…听上去很有道理，但是先把二维存为一维是不是又是个O（mn）呢…
;所以最后还是O（mn）+O（n）= O（mn）
[在 knut (Cute Knut) 的大作中提到：]
：一次去微软面试, 面试官是一个老印的principal engineer, 问我的题目是如何绕圈
打印一个二维矩阵。我老老实实说了算法，写了代码。老印问复杂度，我说O(mn)。老印
：说，那就是O(n2)。我说对的。老印追问能不能做到O(n)。我说不可能，因为n2个元素
：........... |
C*****n
发帖数: 1049 | 6 笑喷了。
你说都不用遍历了，存成一维怎样做到o(n)
【在 k**t 的大作中提到】
: 一次去微软面试, 面试官是一个老印的principal engineer, 问我的题目是如何绕圈打
: 印一个二维矩阵。我老老实实说了算法，写了代码。老印问复杂度，我说O(mn)。老印
: 说，那就是O(n2)。我说对的。老印追问能不能做到O(n)。我说不可能，因为n2个元素
: 每个都要至少访问一次，然后老印给了个解法，让我目瞪口呆……
: 他说你可以把二维矩阵里的数先存到一个一维矩阵 然后遍历这个一位矩阵 就是O(n)
: 算法了！
|
n****e
发帖数: 2401 | 7 这种问题不是很常见吗？以前被问过如何最快的从一维数组找到一个数。
我说必须O（n），因为至少每个元素要访问一遍吧，不然怎么比较。对方说可以更快。
我只好耐心的打个比喻说，这好比你拿着个名片去party找人，你只能一个一个问对吧。
傻逼面试官充满正义感的说到，可以log n, 先把数组转化成一个tree。我都没法往下
听了，操他妈屄的祖宗十八代加所有后代干死妈屄的老母。
【在 C*****n 的大作中提到】
: 笑喷了。
: 你说都不用遍历了，存成一维怎样做到o(n)
|
k***g
发帖数: 166 | 8 你可以说，存hashtable里面还是O(1)了呢
吧。
【在 n****e 的大作中提到】
: 这种问题不是很常见吗？以前被问过如何最快的从一维数组找到一个数。
: 我说必须O（n），因为至少每个元素要访问一遍吧，不然怎么比较。对方说可以更快。
: 我只好耐心的打个比喻说，这好比你拿着个名片去party找人，你只能一个一个问对吧。
: 傻逼面试官充满正义感的说到，可以log n, 先把数组转化成一个tree。我都没法往下
: 听了，操他妈屄的祖宗十八代加所有后代干死妈屄的老母。
|
A********d
发帖数: 558 | 9 hahaha, this made my day!
【在 k***g 的大作中提到】
: 你可以说，存hashtable里面还是O(1)了呢
:
: 吧。
|
z*********8
发帖数: 2070 | 10 其实面试官说的没错
吧。
【在 n****e 的大作中提到】
: 这种问题不是很常见吗？以前被问过如何最快的从一维数组找到一个数。
: 我说必须O（n），因为至少每个元素要访问一遍吧，不然怎么比较。对方说可以更快。
: 我只好耐心的打个比喻说，这好比你拿着个名片去party找人，你只能一个一个问对吧。
: 傻逼面试官充满正义感的说到，可以log n, 先把数组转化成一个tree。我都没法往下
: 听了，操他妈屄的祖宗十八代加所有后代干死妈屄的老母。
|
|
|
j**********3
发帖数: 3211 | 11 哈哈哈哈哈哈哈哈哈哈，我笑死了，，，，，，，不带这么黑大微软的哈哈哈哈 |
t******4
发帖数: 134 | 12 有没可能人家抛出一个负面观点，看看你怎么应对这种场合。
有时候我面试也会搞一个坑，看对方情商咋样
到底是无条件服从，还是情绪激动反驳，还是委婉指出错误
【在 k**t 的大作中提到】
: 一次去微软面试, 面试官是一个老印的principal engineer, 问我的题目是如何绕圈打
: 印一个二维矩阵。我老老实实说了算法，写了代码。老印问复杂度，我说O(mn)。老印
: 说，那就是O(n2)。我说对的。老印追问能不能做到O(n)。我说不可能，因为n2个元素
: 每个都要至少访问一次，然后老印给了个解法，让我目瞪口呆……
: 他说你可以把二维矩阵里的数先存到一个一维矩阵 然后遍历这个一位矩阵 就是O(n)
: 算法了！
|
q*****t
发帖数: 152 | 13 其实这个也是面试，只不过不属于技术面试
人家要面你的不是你的技术
而是看你怎么反应，考你的情商
在组内解决问题的时候肯定有不同意见，人家要看你是怎么处理的，其实就是看你好不
好相处 |
m**********s
发帖数: 518 | 14 我软躺枪
【在 k**t 的大作中提到】
: 一次去微软面试, 面试官是一个老印的principal engineer, 问我的题目是如何绕圈打
: 印一个二维矩阵。我老老实实说了算法，写了代码。老印问复杂度，我说O(mn)。老印
: 说，那就是O(n2)。我说对的。老印追问能不能做到O(n)。我说不可能，因为n2个元素
: 每个都要至少访问一次，然后老印给了个解法，让我目瞪口呆……
: 他说你可以把二维矩阵里的数先存到一个一维矩阵 然后遍历这个一位矩阵 就是O(n)
: 算法了！
|
R*********4
发帖数: 293 | 15 这个面试官以前可能是做过嵌入式。
嵌入式有些就是这样。即使全部列出来。 |
g**c
发帖数: 2339 | |
r*******y
发帖数: 270 | 17 O(mn)跟O(n2)完全是两个概念，你当时就不应该说对。他估计是误解你最初的做法了，
他应该始终就认为n是元素个数的。我觉得是交流问题。 |
c***z
发帖数: 6348 | 18 Why would you want to test that? Is that the common case working with you?
【在 t******4 的大作中提到】
: 有没可能人家抛出一个负面观点，看看你怎么应对这种场合。
: 有时候我面试也会搞一个坑，看对方情商咋样
: 到底是无条件服从，还是情绪激动反驳，还是委婉指出错误
|
L*******k
发帖数: 42 | 19 这是杀敌八百自损一千的面法。忍辱负重承担着面完别人在背后骂傻叉的臭名，也要测
测 candidate的 soft skill，真是好面试官，为公司招人才不拘一格啊！
【在 q*****t 的大作中提到】
: 其实这个也是面试，只不过不属于技术面试
: 人家要面你的不是你的技术
: 而是看你怎么反应，考你的情商
: 在组内解决问题的时候肯定有不同意见，人家要看你是怎么处理的，其实就是看你好不
: 好相处
|
j*******7
发帖数: 6300 | 20 我的经验是：老中想拒你，就提高问题的难度；烙印想拒你，就提高问题的荒诞度。 |
|
|
M******i
发帖数: 468 | 21 lz可以淡定地说，他是对的。 不过你前面估错了，应该也是o(n). 看烙印啥反应。
如果这样都不行，趁早不要去那里工作。 |
t******4
发帖数: 134 | 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***e
发帖数: 1931 | 23 这跟嵌入式有啥关系
【在 R*********4 的大作中提到】
: 这个面试官以前可能是做过嵌入式。
: 嵌入式有些就是这样。即使全部列出来。
|
w****5
发帖数: 46 | 24
然后你咋回答他的呢？还是直接被shock得不省人事了？
【在 k**t 的大作中提到】
: 一次去微软面试, 面试官是一个老印的principal engineer, 问我的题目是如何绕圈打
: 印一个二维矩阵。我老老实实说了算法，写了代码。老印问复杂度，我说O(mn)。老印
: 说，那就是O(n2)。我说对的。老印追问能不能做到O(n)。我说不可能，因为n2个元素
: 每个都要至少访问一次，然后老印给了个解法，让我目瞪口呆……
: 他说你可以把二维矩阵里的数先存到一个一维矩阵 然后遍历这个一位矩阵 就是O(n)
: 算法了！
|
