K*******i 发帖数: 399 | 1 如果准备不充分,经典题也会翻船的。我先贡献一个。
经典的数组求连续元素的最大和(Kadane算法),面试官是老印。
我当然很快就写出那个标准的O(n)解法,但这个解法在所有数都为负数的情况下返回0
。老印随后要求所有数都为负数的情况返回最大的那个负数,我马上给了如下方法:
// step 1, 判断是否全部是负数,如果是,设置flag
for (...)
{
}
// step 2, 如果flag为false, 最初的解法
for (...)
{
}
// step 3, 如果flag为true, 遍历寻找最大的负数
for (...)
{
}
虽然我和他说了,这个三次循环是并列的,整体复杂度其实还是O(n)的。但老印显然非
常不满,问我能否减少为一个循环。我思考了一下,又给出方案如下,
在最初的解法的一次循环里头增加一些操作
bool all_neg = true;
for (...)
{
largest_sum还是用最初的解法更新
用一个变量largest_neg keep当前最大的负数
如果有非负的数, all_neg = false
}
if (all_neg)
return largest_neg;
else
return largest_sum;
老印说OK,然后就让我问问题了。最后的结果当然是被拒了。
某天翻看编程珠玑,这题出现的那章的习题里头提到更好的方法
最初的解法,设置largest_sum初值为0, 所以对全负数的情况返回0
只需要设置largest_sum为负无穷大,或者设置largest_sum为数组的第一个元素,最初
的解法就对全负数的情况返回最大的那个负数了。
我看过后才恍然大悟,这个才是老印要的答案,我的最初方案在他看来愚蠢到家,第二
个方案好些,但在他看来还是愚蠢,所以他拒我没商量。 |
v***n 发帖数: 5085 | 2 错
因为他打定主意据你了
0
【在 K*******i 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 如果准备不充分,经典题也会翻船的。我先贡献一个。 : 经典的数组求连续元素的最大和(Kadane算法),面试官是老印。 : 我当然很快就写出那个标准的O(n)解法,但这个解法在所有数都为负数的情况下返回0 : 。老印随后要求所有数都为负数的情况返回最大的那个负数,我马上给了如下方法: : // step 1, 判断是否全部是负数,如果是,设置flag : for (...) : { : } : // step 2, 如果flag为false, 最初的解法 : for (...)
|
h*****3 发帖数: 1391 | 3 我觉得很多时候是自己对算法并没有真正的理解。所以只要加点限制或者变点形就傻眼
了。 |
e******x 发帖数: 184 | |
Z*****Z 发帖数: 723 | 5 挺有意思的话题,谢谢楼主分享。我也来一个。
面试官的是一个ex-G。
问题是shuffle一副牌,假设这副牌只有4张:1、2、3、4。写完程序之后问怎么测试,
怎么证明是随机分布的。
答:多run几次,统计每个元素出现的位置。当run的次数足够多了以后,每个元素应该
均匀的出现在各个位置。反之亦然,每个位置应该均匀的出现各个元素。
被鄙视,说如何区分这种情况:算法每次只是rotate一下原数组:1234,2341,3412,412
3,1234。。。
答不上来,跪了
后来想想,应该给牌的每个permutation assign一个number,run结果,看这个number
是随机的出现。
可是要再问我怎么测那个number算不算随机出现,我就又跪了。。。
0
【在 K*******i 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 如果准备不充分,经典题也会翻船的。我先贡献一个。 : 经典的数组求连续元素的最大和(Kadane算法),面试官是老印。 : 我当然很快就写出那个标准的O(n)解法,但这个解法在所有数都为负数的情况下返回0 : 。老印随后要求所有数都为负数的情况返回最大的那个负数,我马上给了如下方法: : // step 1, 判断是否全部是负数,如果是,设置flag : for (...) : { : } : // step 2, 如果flag为false, 最初的解法 : for (...)
|
p*****2 发帖数: 21240 | 6
412
number
不对吧?是要测试均匀分布还是随机性呢?如果均匀分布,你那个应该就够了吧?
【在 Z*****Z 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 挺有意思的话题,谢谢楼主分享。我也来一个。 : 面试官的是一个ex-G。 : 问题是shuffle一副牌,假设这副牌只有4张:1、2、3、4。写完程序之后问怎么测试, : 怎么证明是随机分布的。 : 答:多run几次,统计每个元素出现的位置。当run的次数足够多了以后,每个元素应该 : 均匀的出现在各个位置。反之亦然,每个位置应该均匀的出现各个元素。 : 被鄙视,说如何区分这种情况:算法每次只是rotate一下原数组:1234,2341,3412,412 : 3,1234。。。 : 答不上来,跪了 : 后来想想,应该给牌的每个permutation assign一个number,run结果,看这个number
|
Z*****Z 发帖数: 723 | 7 不是均匀分布,是随机性。如何证明是uniform distributed
【在 p*****2 的大作中提到】![](/moin_static193/solenoid/img/up.png) : : 412 : number : 不对吧?是要测试均匀分布还是随机性呢?如果均匀分布,你那个应该就够了吧?
|
p*****2 发帖数: 21240 | 8
随机性的话比较麻烦。不知道有没有什么简单的办法。我能想到的是
1. 每种组合出现的概率是1/24, 如果你给每种组合花一个图的话,他们应该是非常类
似的。我不知道这种图怎么称呼,但是你可以想像基本上是24位置有个peak,然后往两
边下走,左边到1,右边可以接近无穷。
2. 24种组合可以代表24种颜色,画图。图画不应该有规律。
3. 连续序列不应该有规律的出现。比如A->B->C, 每次出现这个序列的间隔应该随机的
。
【在 Z*****Z 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 不是均匀分布,是随机性。如何证明是uniform distributed
|
Z*****Z 发帖数: 723 | 9
不是很懂
对我也是这个意思。如果把24种组合映射到1到24之间的数,这个数应该是随机分布的。
任何序列都不应该有规律的出现。面试官当时的point是,对于我那种做法任何改进都
是徒劳的,总会有一个算法能模拟我想测的“随机性”
【在 p*****2 的大作中提到】![](/moin_static193/solenoid/img/up.png) : : 随机性的话比较麻烦。不知道有没有什么简单的办法。我能想到的是 : 1. 每种组合出现的概率是1/24, 如果你给每种组合花一个图的话,他们应该是非常类 : 似的。我不知道这种图怎么称呼,但是你可以想像基本上是24位置有个peak,然后往两 : 边下走,左边到1,右边可以接近无穷。 : 2. 24种组合可以代表24种颜色,画图。图画不应该有规律。 : 3. 连续序列不应该有规律的出现。比如A->B->C, 每次出现这个序列的间隔应该随机的 : 。
|
c*******r 发帖数: 610 | 10 这问题也太恶心了吧? 如何证明shuffle是随机的?随机数不都是伪随机吗?没法证明
吧....
直接跪了
412
number
【在 Z*****Z 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 挺有意思的话题,谢谢楼主分享。我也来一个。 : 面试官的是一个ex-G。 : 问题是shuffle一副牌,假设这副牌只有4张:1、2、3、4。写完程序之后问怎么测试, : 怎么证明是随机分布的。 : 答:多run几次,统计每个元素出现的位置。当run的次数足够多了以后,每个元素应该 : 均匀的出现在各个位置。反之亦然,每个位置应该均匀的出现各个元素。 : 被鄙视,说如何区分这种情况:算法每次只是rotate一下原数组:1234,2341,3412,412 : 3,1234。。。 : 答不上来,跪了 : 后来想想,应该给牌的每个permutation assign一个number,run结果,看这个number
|
c*******r 发帖数: 610 | 11 如果你一开始设largest_sum 为了,后来还是为0, 是不是就意味着数组全负数呢(或
者全是0)?
这样的话不需要再设其他Tag,如果larges_sum为0, 那么找出最大的负数(对全0应该
也可以),返回就可
以了...
对不?
0
【在 K*******i 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 如果准备不充分,经典题也会翻船的。我先贡献一个。 : 经典的数组求连续元素的最大和(Kadane算法),面试官是老印。 : 我当然很快就写出那个标准的O(n)解法,但这个解法在所有数都为负数的情况下返回0 : 。老印随后要求所有数都为负数的情况返回最大的那个负数,我马上给了如下方法: : // step 1, 判断是否全部是负数,如果是,设置flag : for (...) : { : } : // step 2, 如果flag为false, 最初的解法 : for (...)
|
Z*****Z 发帖数: 723 | 12 争取扫一遍解决吧
【在 c*******r 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 如果你一开始设largest_sum 为了,后来还是为0, 是不是就意味着数组全负数呢(或 : 者全是0)? : 这样的话不需要再设其他Tag,如果larges_sum为0, 那么找出最大的负数(对全0应该 : 也可以),返回就可 : 以了... : 对不? : : 0
|
c*******r 发帖数: 610 | 13 哦,这样的话设Tag还比较合理....
【在 Z*****Z 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 争取扫一遍解决吧
|