w**z
发帖数: 8232 | 1 The program is pretty easy compared to M and F, just for reference
shows a collection of linked-lists.
The bottom-most linked-list contains all the elements sorted in ascending
order (ie: 5, 8, 25, 28, etc ...).
Each linked-list above it allows you to jump to specific nodes in the bottom
list.
Each linked-list is sparser and contains fewer nodes than the linked-list
below it.
If a linked-list has a node for a particular value, then all the other
linked-lists below it will also contain that node, allowing you to cross
from one linked-list to another at these nodes.
For example, at the node with value 8 you can cross from the top-most linked
-list to any of the other linked-lists below it.
Using this structure, how would you efficiently find a value, for example,
70?
class Node {
int value;
Node next;
Node below;
}
X ------> X -----------------------------------------> NULL
X ------> X ------> X ------> X ---------------------> NULL
X ------> X -> X -> X ------> X -----------> X ------> NULL
X -> X -> X -> X -> X -> X -> X -> X -> X -> X -> X -> NULL
H 5 8 25 28 33 52 55 70 81 83 | t**********h
发帖数: 2273 | 2 dropbox么？AppNexus？
bottom
【在 w**z 的大作中提到】
: The program is pretty easy compared to M and F, just for reference
: shows a collection of linked-lists.
: The bottom-most linked-list contains all the elements sorted in ascending
: order (ie: 5, 8, 25, 28, etc ...).
: Each linked-list above it allows you to jump to specific nodes in the bottom
: list.
: Each linked-list is sparser and contains fewer nodes than the linked-list
: below it.
: If a linked-list has a node for a particular value, then all the other
: linked-lists below it will also contain that node, allowing you to cross
| m*****g
发帖数: 226 | | p*****2
发帖数: 21240 | 4 感觉就是从第一个开始找，找到currentNode <= value, currentNode.next>=value
然后往下走 （如果不等于，等于就找到了）。 | w**z
发帖数: 8232 | 5 从 Palo Alto 沿着101北上到SF， startup没有1000，也有500吧。有点.com bubble的
劲头。
【在 t**********h 的大作中提到】
: dropbox么？AppNexus？
:
: bottom
| t**********h
发帖数: 2273 | 6 真好。。。好好找个startup，上市就退休，然后来鄙视我们把 | y**********u
发帖数: 6366 | 7 那他那个就是副帅高，你这个就是高帅富，差别不大啊
【在 t**********h 的大作中提到】
: 真好。。。好好找个startup，上市就退休，然后来鄙视我们把
| i***e
发帖数: 452 | 8 恩。 应该是skip list 查找了！ 从顶上开始找，如果发现比当前的大，则跳到下一层
。O（logn） | v********4
发帖数: 40 | |
|
