f****v
发帖数: 5 | 1 本人在东岸，申了加州小start up。第一轮电面题如下
1.What is the complexity of insertion in a hash table?
2.What is the complexity of searching in a balanced binary search tree?
3.Why use binary search tree when hash table is faster?
4.How many bits will be used in the binary representation of 100,000?
5.How to sort large amount of numbers when memory is limited?
6.What is the difference between thread and process?
题并不难, 但是因为工作太忙, 没有时间复习，大概只回答上来一半。但是又收到信约
了第二轮电
面, 结果被放了鸽子. 其实心里庆幸， 能多几天时间准备. 骑驴找马不容易啊。 |
s******a
发帖数: 35 | |
n*******0
发帖数: 2002 | |
a***y
发帖数: 547 | 4 空间问题？ hash需要的空间比较多
【在 n*******0 的大作中提到】
: 俺圡，敢问3这个有什么好的思路么？
|
s*******n
发帖数: 344 | 5
Balanced binary trees and skip lists preserve ordering — allowing one to
efficiently iterate over the keys in
order or to efficiently locate an association whose key is nearest to a
given value. Hash tables do not preserve
ordering and therefore cannot perform these operations as efficiently.
Balanced binary trees can be easily adapted to efficiently assign a single
value to a large ordered range of
keys, or to count the number of keys in an ordered range.
http://en.wikipedia.org/wiki/Associative_array
【在 n*******0 的大作中提到】
: 俺圡，敢问3这个有什么好的思路么？
|
z**********u
发帖数: 754 | 6 for certain applications, it can be rather difficult to choose a good hash
function
【在 n*******0 的大作中提到】
: 俺圡，敢问3这个有什么好的思路么？
|
h**********c
发帖数: 4120 | |
j*****2
发帖数: 457 | 8 Representations: Hash Table vs Binary Search Tree (self-balancing)
There are two main efficient data structures used to represent associative
arrays, the hash table and the self-balancing binary search tree. Skip lists
are also an alternative, though relatively new and not as widely used.
Relative advantages and disadvantages include:
* Hash tables have faster average lookup and insertion time (O(1)),
while some kinds of binary search tree have faster worst-case lookup and
insertion time (O(log n) instead of O(n)). Hash tables have seen extensive
use in real time systems, but trees can be useful in high-security real time
systems where untrusted users may deliberately supply information that
triggers worst-case performance in a hash table, although careful design can
remove that issue. Hash tables shine in very large arrays, where O(1)
performance is important. Skip lists have worst-case operation time of O(n),
but average-case of O(log n), with much less insertion and deletion
overhead than balanced binary trees.
* Hash tables can have more compact storage for small value types,
especially when the values are bits.
* There are simple persistent versions of balanced binary trees, which
are especially prominent in functional languages.
* Building a hash table requires a reasonable hash function for the key
type, which can be difficult to write well, while balanced binary trees and
skip lists only require a total ordering on the keys. On the other hand,
with hash tables the data may be cyclically or partially ordered without any
problems.
* Balanced binary trees and skip lists preserve ordering — allowing one
to efficiently iterate over the keys in order or to efficiently locate an
association whose key is nearest to a given value. Hash tables do not
preserve ordering and therefore cannot perform these operations as
efficiently.
* Balanced binary trees can be easily adapted to efficiently assign a
single value to a large ordered range of keys, or to count the number of
keys in an ordered range. |
P**l
发帖数: 3722 | |
n*******0
发帖数: 2002 | |
|
|
s*******n
发帖数: 344 | 11 我认为是。amazon面我的时候就问这个了。
【在 P**l 的大作中提到】
: 第五题是merge sort吗？
|
H**d
发帖数: 152 | 12 骑驴找马不容易，理解，BLESS！
请问你是LOCAL的么？ |
g*********s
发帖数: 1782 | 13
average O(1)
tree?
O(lgN)
less memory
lg2(100k) = 17.
merge sort for external sort.
【在 f****v 的大作中提到】
: 本人在东岸，申了加州小start up。第一轮电面题如下
: 1.What is the complexity of insertion in a hash table?
: 2.What is the complexity of searching in a balanced binary search tree?
: 3.Why use binary search tree when hash table is faster?
: 4.How many bits will be used in the binary representation of 100,000?
: 5.How to sort large amount of numbers when memory is limited?
: 6.What is the difference between thread and process?
: 题并不难, 但是因为工作太忙, 没有时间复习，大概只回答上来一半。但是又收到信约
: 了第二轮电
: 面, 结果被放了鸽子. 其实心里庆幸， 能多几天时间准备. 骑驴找马不容易啊。
|
H**d
发帖数: 152 | 14 O(n) space
不是吧？
【在 P**l 的大作中提到】
: 第五题是merge sort吗？
|
n********p
发帖数: 708 | 15 mark~~~~~~~~~~bless~~~~~~~~~~~~ |
w*******m
发帖数: 27 | 16 面过一模一样这些题目，应该是同一家公司,SF的social network公司？ |
f****v
发帖数: 5 | 17 回楼上,我在东海岸, 非local. 确实是一家social network小公司. |
