z********c
发帖数: 72 | 1 都是老题了，FB面了这个，我以前做过，很自信。结果写码以后烙印说我有bug，找半
天没找出来，悲剧啊。。。到现在都不知道哪错了
problem: 给一个int array，对于每个元素，调用
is_red
is_white
is_blue
有且仅有一个为true
要求把这个array重排，使得顺序变成[all red, all white, all blue]
我的代码是：
void dutchFlag (int A[], int n)
{
int red = -1;
int blue = n;
int white = 0;
while (white < blue) {
if (is_red (A[white])) {
swap (A[white], A[red + 1]);
white ++;
red ++;
} else
if (is_blue (A[white])) {
swap (A[white], A[blue - 1]);
blue --;
} else {
white ++;
}
}
}
求指导这段代码哪错了呢？他提示我这段代码会提前退出 |
S******t
发帖数: 151 | |
z********c
发帖数: 72 | 3 ？arxor？不知道这个id啊，我也不是大牛！！！
【在 S******t 的大作中提到】
: 大牛，请回答，您是不是arxor!!!!
|
l*****a
发帖数: 14598 | 4 他忽悠你呢？还是他搞错了？
每次white++ or blue--
the only possible outlet is white==blue
but that is really the end //
【在 z********c 的大作中提到】
: 都是老题了，FB面了这个，我以前做过，很自信。结果写码以后烙印说我有bug，找半
: 天没找出来，悲剧啊。。。到现在都不知道哪错了
: problem: 给一个int array，对于每个元素，调用
: is_red
: is_white
: is_blue
: 有且仅有一个为true
: 要求把这个array重排，使得顺序变成[all red, all white, all blue]
: 我的代码是：
: void dutchFlag (int A[], int n)
|
z********c
发帖数: 72 | 5 烙印是个newbie面试官，旁边有个老美watch，我一写完，两人同时说有bug，我就囧了
找了两分钟，没找出来，他提示我，我还没找出来，然后烙印拍照了。。。。当时我都
快哭了
【在 l*****a 的大作中提到】
: 他忽悠你呢？还是他搞错了？
: 每次white++ or blue--
: the only possible outlet is white==blue
: but that is really the end //
|
S******t
发帖数: 151 | 6 好吧……我认错人了，囧 =____=
【在 z********c 的大作中提到】
: ？arxor？不知道这个id啊，我也不是大牛！！！
|
Z*****Z
发帖数: 723 | 7 程序应该是没有问题的。我觉得是三哥看走眼了。。。
鸡蛋里挑骨头一下，个人觉得变量white应该叫current更好，因为它只是你遍历时候的
一个指针。
cmft
【在 z********c 的大作中提到】
: 都是老题了，FB面了这个，我以前做过，很自信。结果写码以后烙印说我有bug，找半
: 天没找出来，悲剧啊。。。到现在都不知道哪错了
: problem: 给一个int array，对于每个元素，调用
: is_red
: is_white
: is_blue
: 有且仅有一个为true
: 要求把这个array重排，使得顺序变成[all red, all white, all blue]
: 我的代码是：
: void dutchFlag (int A[], int n)
|
l*****a
发帖数: 14598 | 8 你应该给他解释”没问题“
或者要求他给出反例。。
【在 z********c 的大作中提到】
: 烙印是个newbie面试官，旁边有个老美watch，我一写完，两人同时说有bug，我就囧了
: 找了两分钟，没找出来，他提示我，我还没找出来，然后烙印拍照了。。。。当时我都
: 快哭了
|
z********c
发帖数: 72 | 9 面试的时候哪有这胆啊，如果真有问题，那应该就直接被拒了
【在 l*****a 的大作中提到】
: 你应该给他解释”没问题“
: 或者要求他给出反例。。
|
s****m
发帖数: 160 | 10 这道题允许用count sort吗？计算各个颜色的数目，然后依次写入。 |
|
|
l*****a
发帖数: 14598 | 11 这个题一般来说会禁止你这么做
当然你可以提出来。。。
【在 s****m 的大作中提到】
: 这道题允许用count sort吗？计算各个颜色的数目，然后依次写入。
|
s****m
发帖数: 160 | 12 我觉得问题是在swap(A[i], A[j])上，应该改成
swap(A, i, j)。楼主可能是太紧张了。 |
z********c
发帖数: 72 | 13 不可能是这么trivial的地方的
【在 s****m 的大作中提到】
: 我觉得问题是在swap(A[i], A[j])上，应该改成
: swap(A, i, j)。楼主可能是太紧张了。
|
z********c
发帖数: 72 | 14 如果大家觉得没问题，我觉得那很有可能是我当时笔误了，检查的时候只管算法，没注
意检查变量啥的是不是写错了
【在 Z*****Z 的大作中提到】
: 程序应该是没有问题的。我觉得是三哥看走眼了。。。
: 鸡蛋里挑骨头一下，个人觉得变量white应该叫current更好，因为它只是你遍历时候的
: 一个指针。
: cmft
|
s****m
发帖数: 160 | 15 你是推迟了一周去FB面试的吧。其它题目怎么样？
我想以后碰到类似的境况，可以walk through几个实例（包括边界条件的），
这样可以看出到底是他们是在bluffing，还是自己的程序有问题。不能
保证他们是不是在试探你是否能够顶住压力，能够说服别人。 |
c****p
发帖数: 6474 | 16 这确实是个问题。。。。
【在 z********c 的大作中提到】
: 不可能是这么trivial的地方的
|
l*********8
发帖数: 4642 | 17 swap function is like this:
void swap ( int& a, int& b );
So swap(A[i], A[j]) should be fine.
【在 s****m 的大作中提到】
: 我觉得问题是在swap(A[i], A[j])上，应该改成
: swap(A, i, j)。楼主可能是太紧张了。
|
l*****a
发帖数: 14598 | 18 不是说循环中止条件有问题吗
【在 c****p 的大作中提到】
: 这确实是个问题。。。。
|
l*********8
发帖数: 4642 | 19 lz程序是对的，循环中止条件有问题的是这样：
void dutchFlag (int A[], int n)
{
int red = 0;
int blue = n-1;
int white = 0;
while (white < blue) {
if (is_red (A[white])) {
swap (A[white], A[red]);
white ++;
red ++;
} else
if (is_blue (A[white])) {
swap (A[white], A[blue]);
blue --;
} else {
white ++;
}
}
}
【在 l*****a 的大作中提到】
: 不是说循环中止条件有问题吗
|
z****h
发帖数: 164 | 20 自己也做了一遍，没发现lz的程序有什么问题。
不过white这个变量确实让人难受。如前所述，改成curr更好。
会不会是white让面试官产生误解？
抱歉没能提供什么有用信息。 |
