a*****g
发帖数: 336 | 1 【 以下文字转载自 Georgia 讨论区,原文如下 】
发信人: atugong (阿土), 信区: Georgia
标 题: CS interview question
发信站: Unknown Space - 未名空间 (Fri Jun 3 20:18:40 2005) WWW-POST
If you knew that a large array of integers only had one element that was
repeated an odd number of times in the array, how might you process the array
to locate it? |
b***y
发帖数: 157 | 2 Say the scale of the array is n, how much space you have?
【在 a*****g 的大作中提到】
: 【 以下文字转载自 Georgia 讨论区,原文如下 】
: 发信人: atugong (阿土), 信区: Georgia
: 标 题: CS interview question
: 发信站: Unknown Space - 未名空间 (Fri Jun 3 20:18:40 2005) WWW-POST
: If you knew that a large array of integers only had one element that was
: repeated an odd number of times in the array, how might you process the array
: to locate it?
|
a*****g
发帖数: 336 | 3 i just saw the question. not solution provided.
array
【在 b***y 的大作中提到】
: Say the scale of the array is n, how much space you have?
|
g***n
发帖数: 29 | 4 k = a[1] xor a[2] xor .... a[n]
【在 a*****g 的大作中提到】
: 【 以下文字转载自 Georgia 讨论区,原文如下 】
: 发信人: atugong (阿土), 信区: Georgia
: 标 题: CS interview question
: 发信站: Unknown Space - 未名空间 (Fri Jun 3 20:18:40 2005) WWW-POST
: If you knew that a large array of integers only had one element that was
: repeated an odd number of times in the array, how might you process the array
: to locate it?
|
a*****g
发帖数: 336 | 5 This one is good.
array
【在 g***n 的大作中提到】
: k = a[1] xor a[2] xor .... a[n]
|
r****c
发帖数: 2585 | 6 yeah, it is the most efficient,
【在 a*****g 的大作中提到】
: This one is good.
:
: array
|
b***y
发帖数: 157 | 7 I recalled one similar problem,
Say you get an array of n-1 numbers, that are from 1,2,3...n but one of
them was missing, design an algorithm using (log n ) space to find the m
issing number:)
【在 r****c 的大作中提到】
: yeah, it is the most efficient,
|
f*****p
发帖数: 235 | 8 Just sum them up ah. constant space. :)
【在 b***y 的大作中提到】
: I recalled one similar problem,
: Say you get an array of n-1 numbers, that are from 1,2,3...n but one of
: them was missing, design an algorithm using (log n ) space to find the m
: issing number:)
|
b***y
发帖数: 157 | 9 I was stupid that time, suggested such a silly algorithm, and the instru
ctor said I used (log n)^2
My algorithm is, first, use the information theory (information shang do
not know how to say in eng),
set ceil(log n) unit, and then binary encode each number in the array, h
ash(just sequentially) the bit of each number in to the log n slots, and
we will get those slot with one less than others to be effective bits,
then dec code them to get the answer. My classmates was shocked by my .
.. algor
【在 f*****p 的大作中提到】
: Just sum them up ah. constant space. :)
|
b***y
发帖数: 157 | 10 Could anyone help me to take a look @ 5509. My mom miss me too much.
【在 f*****p 的大作中提到】
: Just sum them up ah. constant space. :)
|
|
|
c*z
发帖数: 62 | 11 Can anyone explain it to me why this one works?
I cannot figure this out.
and I did a small test, it doesn't work.
thanks.
【在 r****c 的大作中提到】
: yeah, it is the most efficient,
|
f*****p
发帖数: 235 | 12 A xor A = 0, 0 xor A = A.
【在 c*z 的大作中提到】
: Can anyone explain it to me why this one works?
: I cannot figure this out.
: and I did a small test, it doesn't work.
: thanks.
|
a*****g
发帖数: 336 | 13 can you paste your code here? mine works
public class TestXOR {
public static void main(String[] args) {
int[] testArray = {52938, 38529, 52938, 32093909, 52938, 38529, 32093909};
int a = 0;
for (int i = 0; i < testArray.length; i++) {
a = a ^ testArray[i];
}
System.out.println(a);
}
}
【在 c*z 的大作中提到】
: Can anyone explain it to me why this one works?
: I cannot figure this out.
: and I did a small test, it doesn't work.
: thanks.
|
c*z
发帖数: 62 | 14 [1, 2, 3, 1, 1]
what do you get by xor these numbers? nothing
【在 a*****g 的大作中提到】
: can you paste your code here? mine works
: public class TestXOR {
: public static void main(String[] args) {
: int[] testArray = {52938, 38529, 52938, 32093909, 52938, 38529, 32093909};
: int a = 0;
: for (int i = 0; i < testArray.length; i++) {
: a = a ^ testArray[i];
: }
: System.out.println(a);
: }
|
c*z
发帖数: 62 | 15 what about a xor b?
【在 f*****p 的大作中提到】
: A xor A = 0, 0 xor A = A.
|
f*****p
发帖数: 235 | 16 The original problem says only one element has odd occurence, man.
【在 c*z 的大作中提到】
: [1, 2, 3, 1, 1]
: what do you get by xor these numbers? nothing
|
f*****p
发帖数: 235 | 17 = b xor a, hehe.
【在 c*z 的大作中提到】
: what about a xor b?
|
c*z
发帖数: 62 | 18 dude, cannot you read or count?
【在 f*****p 的大作中提到】
: The original problem says only one element has odd occurence, man.
|
f*****p
发帖数: 235 | 19 This is a good question to ask yourself. [1, 2, 3, 1, 1]. Fingers in
one hand is enough.
【在 c*z 的大作中提到】
: dude, cannot you read or count?
|
l******t
发帖数: 108 | 20 haha, ambiguity
only one element/only element "1"
【在 f*****p 的大作中提到】
: This is a good question to ask yourself. [1, 2, 3, 1, 1]. Fingers in
: one hand is enough.
|
|
|
f*****p
发帖数: 235 | 21
His example is wrong even if the words are understood in the second way.
BTW, the second explanation is a special case of the first one.
【在 l******t 的大作中提到】
: haha, ambiguity
: only one element/only element "1"
|
b********n
发帖数: 609 | 22 行了行了，这道破题500年前就有了，现在是人都知道用xor，别争了。
【在 c*z 的大作中提到】
: dude, cannot you read or count?
|
c*z
发帖数: 62 | 23 I still cannot understant this.
Can you give a good example please?
【在 f*****p 的大作中提到】
:
: His example is wrong even if the words are understood in the second way.
: BTW, the second explanation is a special case of the first one.
|
c*z
发帖数: 62 | 24 I am very new to this board.
This is the first time I heard of this problem.
I just to want to know how to solve it.
【在 b********n 的大作中提到】
: 行了行了，这道破题500年前就有了，现在是人都知道用xor，别争了。
|
f*****p
发帖数: 235 | 25 ft to death.
【在 c*z 的大作中提到】
: I still cannot understant this.
: Can you give a good example please?
|
c*z
发帖数: 62 | 26 then you can etch this problem onto your
tomb stone, :)
【在 f*****p 的大作中提到】
: ft to death.
|
f*****p
发帖数: 235 | 27 The solution is there and the rest part is your understanding. Read the
problem carefully first.
【在 c*z 的大作中提到】
: I am very new to this board.
: This is the first time I heard of this problem.
: I just to want to know how to solve it.
|
f*****p
发帖数: 235 | 28 No, I will put ur id there.
【在 c*z 的大作中提到】
: then you can etch this problem onto your
: tomb stone, :)
|
c*z
发帖数: 62 | 29 There must be a serious misunderstanding.
here is how I understand this problem.
An array of integers, with one element repeated an odd number of times.
Array [1,2,3,1,1]
Element 1
repeated 3 times
The problem is to find element 1
What is wrong with my understanding?
【在 f*****p 的大作中提到】
: The solution is there and the rest part is your understanding. Read the
: problem carefully first.
|
f*****p
发帖数: 235 | 30 You missed an important word: "only".
【在 c*z 的大作中提到】
: There must be a serious misunderstanding.
: here is how I understand this problem.
: An array of integers, with one element repeated an odd number of times.
: Array [1,2,3,1,1]
: Element 1
: repeated 3 times
: The problem is to find element 1
: What is wrong with my understanding?
|
|
|
a*****g
发帖数: 336 | 31 firstep是个好银呐, 脾气真好
【在 f*****p 的大作中提到】
: You missed an important word: "only".
|
f*****p
发帖数: 235 | 32 哪里哪里，借机又灌水一篇而已。:)
【在 a*****g 的大作中提到】
: firstep是个好银呐, 脾气真好
|
a*****g
发帖数: 336 | 33 你的数组里面, 2 只有一个, 3 只有一个, 1有三个, 全是奇数, 看清楚条件先.
【在 c*z 的大作中提到】
: There must be a serious misunderstanding.
: here is how I understand this problem.
: An array of integers, with one element repeated an odd number of times.
: Array [1,2,3,1,1]
: Element 1
: repeated 3 times
: The problem is to find element 1
: What is wrong with my understanding?
|
c*z
发帖数: 62 | 34 2, 3 are not repeated, they appear only once.
【在 a*****g 的大作中提到】
: 你的数组里面, 2 只有一个, 3 只有一个, 1有三个, 全是奇数, 看清楚条件先.
|
c*z
发帖数: 62 | 35 if you articulate this problem saying "appear" instead of
"was repeated", it will save 20 posts.
【在 a*****g 的大作中提到】
: 【 以下文字转载自 Georgia 讨论区,原文如下 】
: 发信人: atugong (阿土), 信区: Georgia
: 标 题: CS interview question
: 发信站: Unknown Space - 未名空间 (Fri Jun 3 20:18:40 2005) WWW-POST
: If you knew that a large array of integers only had one element that was
: repeated an odd number of times in the array, how might you process the array
: to locate it?
|
f*****p
发帖数: 235 | 36 I fule u.
【在 c*z 的大作中提到】
: if you articulate this problem saying "appear" instead of
: "was repeated", it will save 20 posts.
|
c*z
发帖数: 62 | 37 why?
Look at "repeat", it has a root "re-", which means again,
more than once.
【在 f*****p 的大作中提到】
: I fule u.
|
b********n
发帖数: 609 | 38 你这对题目的理解能力还是别面试了
【在 c*z 的大作中提到】
: why?
: Look at "repeat", it has a root "re-", which means again,
: more than once.
|
f*****p
发帖数: 235 | 39 So I say I fule u ah. You should go to law school. :)
【在 c*z 的大作中提到】
: why?
: Look at "repeat", it has a root "re-", which means again,
: more than once.
|
a*****g
发帖数: 336 | 40 兄台见解独特, 根骨奇佳,
以如此天赋异禀, 学CS真是屈才了
【在 c*z 的大作中提到】
: why?
: Look at "repeat", it has a root "re-", which means again,
: more than once.
|
|
|
p****s
发帖数: 3184 | 41 The original problem statement is WRONG.
The problem should be "to find what the value is",
not "to locate it".
"To locate it" means to find the array index of the special value.
If the interviewer did give such a problem statement,
the interviewer should be screwed.
【在 c*z 的大作中提到】
: Can anyone explain it to me why this one works?
: I cannot figure this out.
: and I did a small test, it doesn't work.
: thanks.
|
p****s
发帖数: 3184 | 42
This is also wrong. 1 appears 3 times, 2 and 3 appear 1 time each.
This is not the array in the problem statement.
【在 c*z 的大作中提到】
: [1, 2, 3, 1, 1]
: what do you get by xor these numbers? nothing
|
f*****p
发帖数: 235 | 43 See 5579.
【在 p****s 的大作中提到】
:
: This is also wrong. 1 appears 3 times, 2 and 3 appear 1 time each.
: This is not the array in the problem statement.
|
b***y
发帖数: 157 | 44
~~~~~~~~~~~~~~~~~~~~
Do a sequential search, same time complexity.
Forget about the problem, our scientists, engineers and lowyers
【在 p****s 的大作中提到】
: The original problem statement is WRONG.
: The problem should be "to find what the value is",
: not "to locate it".
: "To locate it" means to find the array index of the special value.
: If the interviewer did give such a problem statement,
: the interviewer should be screwed.
|
p****s
发帖数: 3184 | 45
The XOR solution already assumes a sequential scan.
So I don't know what's new in your claim.
It is clear that "to locate it" is completely different from
"to find what the value is".
For the latter one, O(1) space-complexity and O(N) time-complexity
given an array of N elements. That is, the XOR solution did it.
For the former one, O(N) time-complexity is trivial, but there is no
way you can get O(1) space-complexity. The XOR solution fails.
But I believe the interviewer was thinking about t
【在 b***y 的大作中提到】
:
: ~~~~~~~~~~~~~~~~~~~~
: Do a sequential search, same time complexity.
: Forget about the problem, our scientists, engineers and lowyers
|
b***y
发帖数: 157 | 46 U do not know how many times that special number will appear, thus the s
pace you need to store the location(s) is uncertain, and the upper bound
could be (log n) to store n index. Thus O(1) space is not possible.
My point is that after you get the value of the number, if you wanna loc
ate it (them), you need to do sequential search again, but this time you
have the value, and it takes O(n) time but O(log n) space.
You are pretty aggressive, wish you succeed.
【在 p****s 的大作中提到】
:
: The XOR solution already assumes a sequential scan.
: So I don't know what's new in your claim.
: It is clear that "to locate it" is completely different from
: "to find what the value is".
: For the latter one, O(1) space-complexity and O(N) time-complexity
: given an array of N elements. That is, the XOR solution did it.
: For the former one, O(N) time-complexity is trivial, but there is no
: way you can get O(1) space-complexity. The XOR solution fails.
: But I believe the interviewer was thinking about t
|
r****c
发帖数: 2585 | 47 I fule you
there is a word called refund, do you mean you are fund twice?
【在 c*z 的大作中提到】
: why?
: Look at "repeat", it has a root "re-", which means again,
: more than once.
|
a*****g
发帖数: 336 | 48 整一个linked list不就得了, java 里的arraylist 也行,
扫两趟是O(N), 对linked list最多插N次, 还是O(N)
就一脑筋急转弯似的破题, 看了, 解了, 知道嘛回事了, 就行了
【在 b***y 的大作中提到】
: U do not know how many times that special number will appear, thus the s
: pace you need to store the location(s) is uncertain, and the upper bound
: could be (log n) to store n index. Thus O(1) space is not possible.
: My point is that after you get the value of the number, if you wanna loc
: ate it (them), you need to do sequential search again, but this time you
: have the value, and it takes O(n) time but O(log n) space.
: You are pretty aggressive, wish you succeed.
|
f*****p
发帖数: 235 | 49 Sure. A fund B, B refund A. Twice. haha
【在 r****c 的大作中提到】
: I fule you
: there is a word called refund, do you mean you are fund twice?
|
r****c
发帖数: 2585 | 50 hehe
thank
when you say this, it means that A fund B: fund one time
B refund A: fund one time,
it is what is just mean: refund = fund instead refund = 2* fund
【在 f*****p 的大作中提到】
: Sure. A fund B, B refund A. Twice. haha
|
|
|
d*******e
发帖数: 49 | 51 same here. I understand the problem same as you.
I can not figure out the soluion.
But after I saw the solution, I knew what I was missing. hehe
【在 c*z 的大作中提到】
: if you articulate this problem saying "appear" instead of
: "was repeated", it will save 20 posts.
|
