K*****k
发帖数: 430 | 1 从自己的经历和他人的面经看，很多时候，70%或者更多的题目都是版上见过的简单题
，常见题，经典题，也就是你onsite的时候绝对有思路.
但是有思路不等于能写对,能写好。
如果70%的轮次,你都出现了这样或那样的小bug, 或者：
1) 代码过于冗长，变量引入太多，重复代码摆在那（可以抽取成函数），不善于利用
现有的类，Java的数据结构或者C++的STL（比如没有必要写一个基于数组的，自己维护
top指针的裸stack)
2) 代码风格不好，命名，缩进，空行有问题
3）做完不检查，忙把代码交，漏了边界条件，非法输入，溢出。
4）不探讨其它的方法，不引申关联的主题和扩展
我想因为这样失败的例子肯定不少。
我有一个MSFT失败的电面例子：
题目很简单，就是经典的数组求连续的子数组最大和，心中暗喜，很快搞定。
老印接着问，如果数组全是负数怎么办？我说这个方法返回0
老印说，如果要求返回最大的负数呢？
我说检查这个特殊情况单独处理，然后开始写代码
1）先写了第一个一重循环，判断是否全部是负数
2) 如果不全是负数，用先前的方法，第二个一重循环
3）如果全是负数，在用第三个一重循环找到最大的负数
老印说，这样写太麻烦了。我说是，但是三个并列的一重循环，结果还是O(N)的
老印说，你还有什么改进么？
我看了看说，可以在1）中就同时求得最大负数，这样就减少为两个一重循环
老印说，你还能改进么？
我想了想说，可以在2)那个循环中,keep最大的负数和判断是否全部是负数，这样就减
少为一个一重循环了。
老印说OK
电面后看了看编程珠玑的这题，在课后习题中有提到全部负数情况，只需要
一开始的时候不用max = 0; 而用max = -INF或者max = A[0]就可以处理全部负数的情
况。
我想完了，老印肯定知道这个方法，但他没有说，而在心中暗笑我的愚蠢的拙劣代码。
果然N天后，被默拒了。 |
e*********l
发帖数: 136 | 2 Can not agree more...
第一次onsite就挂在最简单的题目上的。 |
A**u
发帖数: 2458 | 3 看来 还要多写，
光讨论算法是远远不够的
【在 K*****k 的大作中提到】
: 从自己的经历和他人的面经看，很多时候，70%或者更多的题目都是版上见过的简单题
: ，常见题，经典题，也就是你onsite的时候绝对有思路.
: 但是有思路不等于能写对,能写好。
: 如果70%的轮次,你都出现了这样或那样的小bug, 或者：
: 1) 代码过于冗长，变量引入太多，重复代码摆在那（可以抽取成函数），不善于利用
: 现有的类，Java的数据结构或者C++的STL（比如没有必要写一个基于数组的，自己维护
: top指针的裸stack)
: 2) 代码风格不好，命名，缩进，空行有问题
: 3）做完不检查，忙把代码交，漏了边界条件，非法输入，溢出。
: 4）不探讨其它的方法，不引申关联的主题和扩展
|
f*******t
发帖数: 7549 | |
b***e
发帖数: 383 | |
K*****k
发帖数: 430 | 6 对经典题，知道了解法，自己也练过后，我想应该去找最简洁的写法。一些技巧可以减
少代码的行数或者不必要的判断。
比如Carrer Cup上的解答有类似的语句
...
if (!Func(x))
return false;
return true;
其实可以简化为写成
return Func(x);
把三行代码缩小为一行了。
还记得费马的话吗：
对于这个问题我有了一个巧妙的解法，可惜书页里的边缘太小，写不下了。
对于我们：
对这道题我有一个绝对可行的解法，可惜这个白板太小了，写不下了。 |
q****x
发帖数: 7404 | 7 这个算法本身有二义性。
如果连续子数组包括空集，那么即使全是负数也应该返回0。老印说的是变种，子数组
至少包括一个元素。
【在 K*****k 的大作中提到】
: 从自己的经历和他人的面经看，很多时候，70%或者更多的题目都是版上见过的简单题
: ，常见题，经典题，也就是你onsite的时候绝对有思路.
: 但是有思路不等于能写对,能写好。
: 如果70%的轮次,你都出现了这样或那样的小bug, 或者：
: 1) 代码过于冗长，变量引入太多，重复代码摆在那（可以抽取成函数），不善于利用
: 现有的类，Java的数据结构或者C++的STL（比如没有必要写一个基于数组的，自己维护
: top指针的裸stack)
: 2) 代码风格不好，命名，缩进，空行有问题
: 3）做完不检查，忙把代码交，漏了边界条件，非法输入，溢出。
: 4）不探讨其它的方法，不引申关联的主题和扩展
|
K*****k
发帖数: 430 | 8 是这样没错，但这是由面试官来决定全部负数你怎么处理。
老印明确了要求，全部负数返回最大的负数。
但是我不假思索的写了个三重循环，最后缩到一个，但是还是写得不够优美，不如编程
珠玑的解答。
编程珠玑课后的习题绝对是宝贵的财富，不看是可惜的
【在 q****x 的大作中提到】
: 这个算法本身有二义性。
: 如果连续子数组包括空集，那么即使全是负数也应该返回0。老印说的是变种，子数组
: 至少包括一个元素。
|
A**u
发帖数: 2458 | 9 你很推崇编程珠玑啊
我先前翻了一遍，看它是用c写的， 讨论二分，递归，分治等基础
就没看下去
真的很有帮助吗
你看过 algorithms for interview没
那个也不错
【在 K*****k 的大作中提到】
: 是这样没错，但这是由面试官来决定全部负数你怎么处理。
: 老印明确了要求，全部负数返回最大的负数。
: 但是我不假思索的写了个三重循环，最后缩到一个，但是还是写得不够优美，不如编程
: 珠玑的解答。
: 编程珠玑课后的习题绝对是宝贵的财富，不看是可惜的
|
q****x
发帖数: 7404 | 10 按照他的要求，你应该马上考虑变种算法，硬套经典算法不行。
我的观点是你显然当时没有想清楚他的要求和经典题的区别，而是有点硬套答案的意思
。如果老印也这么想，你就坏了。因为他会觉得你是事先准备过，并不是自己发挥出来
的。
如果你当时反应过来返回0和返回最大负数的区别，就应该能想到和初值有关。
【在 K*****k 的大作中提到】
: 是这样没错，但这是由面试官来决定全部负数你怎么处理。
: 老印明确了要求，全部负数返回最大的负数。
: 但是我不假思索的写了个三重循环，最后缩到一个，但是还是写得不够优美，不如编程
: 珠玑的解答。
: 编程珠玑课后的习题绝对是宝贵的财富，不看是可惜的
|
|
|
K*****k
发帖数: 430 | 11 是在我完成经典算法后他才说要是全部是负数怎么办...
不过还是经验不足.如果事先没有看过，现场又不能灵光一闪,首先能想到的肯定还是比
较笨的方法,包括Brute-Force的方法。
【在 q****x 的大作中提到】
: 按照他的要求，你应该马上考虑变种算法，硬套经典算法不行。
: 我的观点是你显然当时没有想清楚他的要求和经典题的区别，而是有点硬套答案的意思
: 。如果老印也这么想，你就坏了。因为他会觉得你是事先准备过，并不是自己发挥出来
: 的。
: 如果你当时反应过来返回0和返回最大负数的区别，就应该能想到和初值有关。
|
q****x
发帖数: 7404 | 12 其实我觉得他的引申是个好问题。
如果学习经典算法时想过为什么max初值是0，就会想到这里的0对应的是解为空集的情
况，对算法的认识也就深了一层。
【在 K*****k 的大作中提到】
: 是在我完成经典算法后他才说要是全部是负数怎么办...
: 不过还是经验不足.如果事先没有看过，现场又不能灵光一闪,首先能想到的肯定还是比
: 较笨的方法,包括Brute-Force的方法。
|
r****t
发帖数: 10904 | 13 这个太搞了，不过谢谢分享（包括楼主的其他帖子），楼主加油！
【在 K*****k 的大作中提到】
: 从自己的经历和他人的面经看，很多时候，70%或者更多的题目都是版上见过的简单题
: ，常见题，经典题，也就是你onsite的时候绝对有思路.
: 但是有思路不等于能写对,能写好。
: 如果70%的轮次,你都出现了这样或那样的小bug, 或者：
: 1) 代码过于冗长，变量引入太多，重复代码摆在那（可以抽取成函数），不善于利用
: 现有的类，Java的数据结构或者C++的STL（比如没有必要写一个基于数组的，自己维护
: top指针的裸stack)
: 2) 代码风格不好，命名，缩进，空行有问题
: 3）做完不检查，忙把代码交，漏了边界条件，非法输入，溢出。
: 4）不探讨其它的方法，不引申关联的主题和扩展
|
w****x
发帖数: 2483 | 14 int BiggestSubArry(int a[], int n)
{
assert(a && n > 0);
int nSum = INT_MIN;
int nTmp = INT_MIN;
for (int i = 0; i < n; i++)
{
if (nTmp < 0)
nTmp = max(nTmp, a[i]);
else
nTmp = nTmp + a[i] <= 0 ? 0 : nTmp + a[i];
nSum = max(nTmp, nSum);
}
return nSum;
}
说实话, 真够绕的, 别看就这几行 |
b*****c
发帖数: 1103 | 15 其实f,g,m onsite都是简单题，但还是有些难度的，简单不代表不需要trick，可惜板上面
经很多没有完美答案滴 |
