k****r
发帖数: 807 | 1 1. A file contains a billion integers, try to find any one integer that is
not in the file.
2. If you wanted to make a highly concurrent cache with a least recently
used replacement policy, what data structures would you use? How would this
scale per number of threads?
3. How would you implement hash table on your own? Write the code for
implementing your own hash table?
4. Generate a random 4 letter word from /usr/share/dict/words |
k****r
发帖数: 807 | 2 anyone's idea is welcome.
I provide mine for the question 1.
My way is like that
1. separate the file into many smaller files by this way. use (input%1000)
to decide which file to save; So each file includes some integers with same
remainder when divided by 1000.
2. read the file one by one. firstly, use hash table to save the elements of
the file. Then, check the complete list whose elements have some remainder
when divided by 1000 in this hashtable. the one not in it is the result.
Please help correct my idea. |
b***m
发帖数: 5987 | 3 第三题：关键是找到合适的hash function、处理collision、expanding。 |
k****r
发帖数: 807 | 4 高人，我觉得这4个题，你都不是问题啊，
能不能谈谈您的答案呢？谢谢
【在 b***m 的大作中提到】
: 第三题：关键是找到合适的hash function、处理collision、expanding。
|
l*****a
发帖数: 14598 | 5 如何找到合适的hash function呢？
【在 b***m 的大作中提到】
: 第三题：关键是找到合适的hash function、处理collision、expanding。
|
b***m
发帖数: 5987 | 6
如果是这种面试，我会假设是string到string的map，然后把string转成整数再对一个
质数取模。优秀的hash function是很难找的，作为面试官不会指望你自己临时发明或
者死记住某个hash function，你知道原理就好了。至于如何完美的实现，那是数学家
的事情。
【在 l*****a 的大作中提到】
: 如何找到合适的hash function呢？
|
s**s
发帖数: 70 | 7 第二题是考LRU实现吧？ linked list + hashtable 搞定。 “how would this
scale per number of threads” 是想问的啥？ 没搞懂
this
【在 k****r 的大作中提到】
: 1. A file contains a billion integers, try to find any one integer that is
: not in the file.
: 2. If you wanted to make a highly concurrent cache with a least recently
: used replacement policy, what data structures would you use? How would this
: scale per number of threads?
: 3. How would you implement hash table on your own? Write the code for
: implementing your own hash table?
: 4. Generate a random 4 letter word from /usr/share/dict/words
|
s**s
发帖数: 70 | 8 第一题先分块，然后找个未填满的块，在块内用bitset找个不在块内的数。
this
【在 k****r 的大作中提到】
: 1. A file contains a billion integers, try to find any one integer that is
: not in the file.
: 2. If you wanted to make a highly concurrent cache with a least recently
: used replacement policy, what data structures would you use? How would this
: scale per number of threads?
: 3. How would you implement hash table on your own? Write the code for
: implementing your own hash table?
: 4. Generate a random 4 letter word from /usr/share/dict/words
|
