A********d
发帖数: 558 | 1 【 以下文字转载自 JobHunting 讨论区 】
发信人: knut (Cute Knut), 信区: JobHunting
标 题: 微软面试题
发信站: BBS 未名空间站 (Sun Mar 6 02:05:29 2016, 美东)
一次去微软面试, 面试官是一个老印的principal engineer, 问我的题目是如何绕圈打
印一个二维矩阵。我老老实实说了算法，写了代码。老印问复杂度，我说O(mn)。老印
说，那就是O(n2)。我说对的。老印追问能不能做到O(n)。我说不可能，因为n2个元素
每个都要至少访问一次，然后老印给了个解法，让我目瞪口呆……
他说你可以把二维矩阵里的数先存到一个一维矩阵 然后遍历这个一位矩阵 就是O(n)
算法了！ |
D******g
发帖数: 2717 | |
d********f
发帖数: 43471 | 3 图灵奖
【在 A********d 的大作中提到】
: 【 以下文字转载自 JobHunting 讨论区 】
: 发信人: knut (Cute Knut), 信区: JobHunting
: 标 题: 微软面试题
: 发信站: BBS 未名空间站 (Sun Mar 6 02:05:29 2016, 美东)
: 一次去微软面试, 面试官是一个老印的principal engineer, 问我的题目是如何绕圈打
: 印一个二维矩阵。我老老实实说了算法，写了代码。老印问复杂度，我说O(mn)。老印
: 说，那就是O(n2)。我说对的。老印追问能不能做到O(n)。我说不可能，因为n2个元素
: 每个都要至少访问一次，然后老印给了个解法，让我目瞪口呆……
: 他说你可以把二维矩阵里的数先存到一个一维矩阵 然后遍历这个一位矩阵 就是O(n)
: 算法了！
|
d****o
发帖数: 32610 | 4 李菊福
【在 A********d 的大作中提到】
: 【 以下文字转载自 JobHunting 讨论区 】
: 发信人: knut (Cute Knut), 信区: JobHunting
: 标 题: 微软面试题
: 发信站: BBS 未名空间站 (Sun Mar 6 02:05:29 2016, 美东)
: 一次去微软面试, 面试官是一个老印的principal engineer, 问我的题目是如何绕圈打
: 印一个二维矩阵。我老老实实说了算法，写了代码。老印问复杂度，我说O(mn)。老印
: 说，那就是O(n2)。我说对的。老印追问能不能做到O(n)。我说不可能，因为n2个元素
: 每个都要至少访问一次，然后老印给了个解法，让我目瞪口呆……
: 他说你可以把二维矩阵里的数先存到一个一维矩阵 然后遍历这个一位矩阵 就是O(n)
: 算法了！
|
p*e
发帖数: 6785 | 5 能不能做到 O（1）
【在 A********d 的大作中提到】
: 【 以下文字转载自 JobHunting 讨论区 】
: 发信人: knut (Cute Knut), 信区: JobHunting
: 标 题: 微软面试题
: 发信站: BBS 未名空间站 (Sun Mar 6 02:05:29 2016, 美东)
: 一次去微软面试, 面试官是一个老印的principal engineer, 问我的题目是如何绕圈打
: 印一个二维矩阵。我老老实实说了算法，写了代码。老印问复杂度，我说O(mn)。老印
: 说，那就是O(n2)。我说对的。老印追问能不能做到O(n)。我说不可能，因为n2个元素
: 每个都要至少访问一次，然后老印给了个解法，让我目瞪口呆……
: 他说你可以把二维矩阵里的数先存到一个一维矩阵 然后遍历这个一位矩阵 就是O(n)
: 算法了！
|
x****o
发帖数: 21566 | 6 可以，告诉你的手下去把矩阵打印出来，你去喝咖啡
【在 p*e 的大作中提到】
: 能不能做到 O（1）
|
p*****d
发帖数: 183 | 7 Jeff Dean能做到O(1/n)
【在 p*e 的大作中提到】
: 能不能做到 O（1）
|
n****4
发帖数: 12553 | 8 学无止境，能否弄成O(logn)?
【在 A********d 的大作中提到】
: 【 以下文字转载自 JobHunting 讨论区 】
: 发信人: knut (Cute Knut), 信区: JobHunting
: 标 题: 微软面试题
: 发信站: BBS 未名空间站 (Sun Mar 6 02:05:29 2016, 美东)
: 一次去微软面试, 面试官是一个老印的principal engineer, 问我的题目是如何绕圈打
: 印一个二维矩阵。我老老实实说了算法，写了代码。老印问复杂度，我说O(mn)。老印
: 说，那就是O(n2)。我说对的。老印追问能不能做到O(n)。我说不可能，因为n2个元素
: 每个都要至少访问一次，然后老印给了个解法，让我目瞪口呆……
: 他说你可以把二维矩阵里的数先存到一个一维矩阵 然后遍历这个一位矩阵 就是O(n)
: 算法了！
|
k*******2
发帖数: 4163 | 9 老印的这个N就是人家前面说的nxn，即矩阵元素个数。
老印还需要脱裤放屁得先把矩阵遍历一遍存进数组，这遍历的功夫就直接打印了。
老印的方法，要多花时间分配一个数组，再写数组，然后再遍历数组，时间至少
多花一倍。当然复杂度没变，仍然是O(矩阵元素个数）。
【在 D******g 的大作中提到】
: 没毛病
|
r*******y
发帖数: 270 | |
|
|
B*******O
发帖数: 543 | 11 我还有更夸张的
一次面试微软，一烙印问我，你的研究方向是什么
我说是pattern recognition
这位大爷于是打出一页程序
说你把里面的pattern找出来
我当场石化了
【在 A********d 的大作中提到】
: 【 以下文字转载自 JobHunting 讨论区 】
: 发信人: knut (Cute Knut), 信区: JobHunting
: 标 题: 微软面试题
: 发信站: BBS 未名空间站 (Sun Mar 6 02:05:29 2016, 美东)
: 一次去微软面试, 面试官是一个老印的principal engineer, 问我的题目是如何绕圈打
: 印一个二维矩阵。我老老实实说了算法，写了代码。老印问复杂度，我说O(mn)。老印
: 说，那就是O(n2)。我说对的。老印追问能不能做到O(n)。我说不可能，因为n2个元素
: 每个都要至少访问一次，然后老印给了个解法，让我目瞪口呆……
: 他说你可以把二维矩阵里的数先存到一个一维矩阵 然后遍历这个一位矩阵 就是O(n)
: 算法了！
|
T*U
发帖数: 22634 | 12 能，刻个戳，要打印咔嚓一下。
【在 p*e 的大作中提到】
: 能不能做到 O（1）
|
d****z
发帖数: 9503 | 13 雕版印刷 O(1)
【在 p*e 的大作中提到】
: 能不能做到 O（1）
|
l******8
发帖数: 1691 | 14 人家这就是智慧。够索男学一辈子。
【在 A********d 的大作中提到】
: 【 以下文字转载自 JobHunting 讨论区 】
: 发信人: knut (Cute Knut), 信区: JobHunting
: 标 题: 微软面试题
: 发信站: BBS 未名空间站 (Sun Mar 6 02:05:29 2016, 美东)
: 一次去微软面试, 面试官是一个老印的principal engineer, 问我的题目是如何绕圈打
: 印一个二维矩阵。我老老实实说了算法，写了代码。老印问复杂度，我说O(mn)。老印
: 说，那就是O(n2)。我说对的。老印追问能不能做到O(n)。我说不可能，因为n2个元素
: 每个都要至少访问一次，然后老印给了个解法，让我目瞪口呆……
: 他说你可以把二维矩阵里的数先存到一个一维矩阵 然后遍历这个一位矩阵 就是O(n)
: 算法了！
|
n****4
发帖数: 12553 | 15 雕版印刷每个字难道不也得访问一遍至少，在刻字的时候？
【在 d****z 的大作中提到】
: 雕版印刷 O(1)
|
