R********n
发帖数: 3601 | 1 【 以下文字转载自 JobHunting 讨论区 】
发信人: Kramnik (克拉姆尼克), 信区: JobHunting
标 题: 电面最经典的题却栽了
发信站: BBS 未名空间站 (Mon Mar 3 22:16:25 2014, 美东)
那是四年以前的事了，一个MSFT失败的电面经历：
题目很简单，就是经典的数组求连续的子数组最大和，心中暗喜，很快搞定。
老印接着问，如果数组全是负数怎么办？我说这个方法返回0
老印说，如果要求返回最大的负数呢？
我说检查这个特殊情况单独处理，然后开始写代码
1）先写了第一个一重循环，判断是否全部是负数
2) 如果不全是负数，用先前的方法，第二个一重循环
3）如果全是负数，在用第三个一重循环找到最大的负数
老印说，这样写太麻烦了。我说是，但是三个并列的一重循环，结果还是O(N)的
老印说，你还有什么改进么？
我看了看说，可以在1）中就同时求得最大负数，这样就减少为两个一重循环
老印说，你还能改进么？
我想了想说，可以在2)那个循环中,keep最大的负数和判断是否全部是负数，这样就减
少为一个一重循环了。
老印说OK
电面后看了看编程珠玑的这题，在课后习题中有提到全部负数情况，只需要
一开始的时候不用max = 0; 而用max = -INF或者max = A[0]就可以处理全部负数的情
况。
老印肯定知道这个方法，但他没有说，而在心中暗笑我的愚蠢的拙劣代码。
果然N天后，被默拒了。 |
|
