z***e
发帖数: 14 | 1 I saw a similar post in this board, and recalled my recent interview
experience. Got this question in Amazon interview. Although I failed, it is
still a good one.
My answer:
1. Create a hash table to store all integers in this array. O(n)
2. For each int, look for sum - int in the created hash tree. Since hash
tree is the fastest look-up table, we can take advantage from it. n*O(1)
3. So this is O(n) algorithm.
Then the guy gave me the array 1, 2, 10, 20, sum is 2. My answer will return
true obv | o******r
发帖数: 259 | 2 What if you have a collision in setting up hash table.
Do you use list?
A simple solution is just count occurrence of a value.
Since it only needs to be checked when value == S/2,
the occurrence count doesn't affect much.
is
return
【在 z***e 的大作中提到】
: I saw a similar post in this board, and recalled my recent interview
: experience. Got this question in Amazon interview. Although I failed, it is
: still a good one.
: My answer:
: 1. Create a hash table to store all integers in this array. O(n)
: 2. For each int, look for sum - int in the created hash tree. Since hash
: tree is the fastest look-up table, we can take advantage from it. n*O(1)
: 3. So this is O(n) algorithm.
: Then the guy gave me the array 1, 2, 10, 20, sum is 2. My answer will return
: true obv
|
|
