v*****u
发帖数: 406 | 1 今天突然接到一个recuiter电话。然后被问及几个问题。
Array里找missing value.我说用int i遍历。被鄙视。
问multi-thread编程的pattern design。当时我说不知道。
人家要我补一补cs基础知识。
另外就是一问到身份问题，就嘎然而止。
唉......大家来教育下我吧。 |
c***2
发帖数: 838 | 2 1) Array里找missing value:
Linear scan with the help of either a hash table or a bit vector
2) multi-thread编程的pattern design
Don't know either |
l*****a
发帖数: 14598 | 3 1)
Use XOR if u know the scope of the numbers.
【在 c***2 的大作中提到】
: 1) Array里找missing value:
: Linear scan with the help of either a hash table or a bit vector
: 2) multi-thread编程的pattern design
: Don't know either
|
c***2
发帖数: 838 | 4 How to do it in o(n) using XOR?
Oh, XOR(all numbers in range and all numbers in array)?
this works if only one number is missing
won't work if multiple are missing?
【在 l*****a 的大作中提到】
: 1)
: Use XOR if u know the scope of the numbers.
|
j*****u
发帖数: 1133 | 5 array是连续的么？如果是连续找1个missing value的话可以扫一遍得到sum(注意溢出)
，min和max
missing=min + ... + max - sum
multi-thread的pattern deisign是啥，第一次听说这个名词
【在 v*****u 的大作中提到】
: 今天突然接到一个recuiter电话。然后被问及几个问题。
: Array里找missing value.我说用int i遍历。被鄙视。
: 问multi-thread编程的pattern design。当时我说不知道。
: 人家要我补一补cs基础知识。
: 另外就是一问到身份问题，就嘎然而止。
: 唉......大家来教育下我吧。
|
l*****a
发帖数: 14598 | 6 then could u tell me how will u solve it
if you don't know the scope of those numbers in the array
with bit sector.
【在 c***2 的大作中提到】
: How to do it in o(n) using XOR?
: Oh, XOR(all numbers in range and all numbers in array)?
: this works if only one number is missing
: won't work if multiple are missing?
|
c***2
发帖数: 838 | 7 "missing number" implies that the range of the array must be known.
Otherwise, this question won't make sense.
Suppose the range of the array is (min..max)
Then just use either a hashtable or bit vector with size of max-min+1. |
j*****u
发帖数: 1133 | 8 why collection needed? missing = sum(min, max) - sum(array)
time O(n), space O(1)
【在 c***2 的大作中提到】
: "missing number" implies that the range of the array must be known.
: Otherwise, this question won't make sense.
: Suppose the range of the array is (min..max)
: Then just use either a hashtable or bit vector with size of max-min+1.
|
v*****u
发帖数: 406 | 9
对呀对呀。就是这样的。
当时recruiter也说到这个方法。我没有听明白。
你怎么能够知道呢？哪里书可以看到？
【在 j*****u 的大作中提到】
: why collection needed? missing = sum(min, max) - sum(array)
: time O(n), space O(1)
|
