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 的大作中提到】
: 如果准备不充分，经典题也会翻船的。我先贡献一个。
: 经典的数组求连续元素的最大和(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 的大作中提到】
: 如果准备不充分，经典题也会翻船的。我先贡献一个。
: 经典的数组求连续元素的最大和(Kadane算法)，面试官是老印。
: 我当然很快就写出那个标准的O(n)解法，但这个解法在所有数都为负数的情况下返回0
: 。老印随后要求所有数都为负数的情况返回最大的那个负数，我马上给了如下方法：
: // step 1, 判断是否全部是负数，如果是，设置flag
: for (...)
: {
: }
: // step 2, 如果flag为false, 最初的解法
: for (...)
|
p*****2
发帖数: 21240 | 6
412
number
不对吧？是要测试均匀分布还是随机性呢？如果均匀分布，你那个应该就够了吧？
【在 Z*****Z 的大作中提到】
: 挺有意思的话题，谢谢楼主分享。我也来一个。
: 面试官的是一个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 的大作中提到】
:
: 412
: number
: 不对吧？是要测试均匀分布还是随机性呢？如果均匀分布，你那个应该就够了吧？
|
p*****2
发帖数: 21240 | 8
随机性的话比较麻烦。不知道有没有什么简单的办法。我能想到的是
1. 每种组合出现的概率是1／24, 如果你给每种组合花一个图的话，他们应该是非常类
似的。我不知道这种图怎么称呼，但是你可以想像基本上是24位置有个peak，然后往两
边下走，左边到1,右边可以接近无穷。
2. 24种组合可以代表24种颜色，画图。图画不应该有规律。
3. 连续序列不应该有规律的出现。比如A->B->C, 每次出现这个序列的间隔应该随机的
。
【在 Z*****Z 的大作中提到】
: 不是均匀分布，是随机性。如何证明是uniform distributed
|
Z*****Z
发帖数: 723 | 9
不是很懂
对我也是这个意思。如果把24种组合映射到1到24之间的数，这个数应该是随机分布的。
任何序列都不应该有规律的出现。面试官当时的point是，对于我那种做法任何改进都
是徒劳的，总会有一个算法能模拟我想测的“随机性”
【在 p*****2 的大作中提到】
:
: 随机性的话比较麻烦。不知道有没有什么简单的办法。我能想到的是
: 1. 每种组合出现的概率是1／24, 如果你给每种组合花一个图的话，他们应该是非常类
: 似的。我不知道这种图怎么称呼，但是你可以想像基本上是24位置有个peak，然后往两
: 边下走，左边到1,右边可以接近无穷。
: 2. 24种组合可以代表24种颜色，画图。图画不应该有规律。
: 3. 连续序列不应该有规律的出现。比如A->B->C, 每次出现这个序列的间隔应该随机的
: 。
|
c*******r
发帖数: 610 | 10 这问题也太恶心了吧？ 如何证明shuffle是随机的？随机数不都是伪随机吗？没法证明
吧....
直接跪了
412
number
【在 Z*****Z 的大作中提到】
: 挺有意思的话题，谢谢楼主分享。我也来一个。
: 面试官的是一个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 的大作中提到】
: 如果准备不充分，经典题也会翻船的。我先贡献一个。
: 经典的数组求连续元素的最大和(Kadane算法)，面试官是老印。
: 我当然很快就写出那个标准的O(n)解法，但这个解法在所有数都为负数的情况下返回0
: 。老印随后要求所有数都为负数的情况返回最大的那个负数，我马上给了如下方法：
: // step 1, 判断是否全部是负数，如果是，设置flag
: for (...)
: {
: }
: // step 2, 如果flag为false, 最初的解法
: for (...)
|
Z*****Z
发帖数: 723 | 12 争取扫一遍解决吧
【在 c*******r 的大作中提到】
: 如果你一开始设largest_sum 为了，后来还是为0， 是不是就意味着数组全负数呢（或
: 者全是0）？
: 这样的话不需要再设其他Tag，如果larges_sum为0， 那么找出最大的负数（对全0应该
: 也可以），返回就可
: 以了...
: 对不？
:
: 0
|
c*******r
发帖数: 610 | 13 哦，这样的话设Tag还比较合理....
【在 Z*****Z 的大作中提到】
: 争取扫一遍解决吧
|
