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,可惜板上面
经很多没有完美答案滴 |