j**w
发帖数: 382 | 1 ftp://ftp.cs.umd.edu/pub/skipLists/skiplists.pdf
It's shorter than you think, even for source code. |
|
p*****u
发帖数: 310 | 2 RT。 skiplist的概念网上都有，可没看见关于各种运算伪代码级的算法。不想要代码
级的，太长了。 |
|
s*****y
发帖数: 897 | 3 作者实现skiplist的那种C是什么C阿，语法很快，但是又似曾相识。 |
|
h********e
发帖数: 1972 | 4 来自主题: JobHunting版 - 问一道老题 仔细想啊-0- 。。。别重复找,每次min，max都是list的第一个元素，不需要扫一遍list。。找过的都扔掉了。。amortize下来肯定O(1).就两个指针，永远不回头的。不可能搞出n^2的复杂度。
应该叫skiplist。。不过这里的用法跟skiplist的本意应该不一样。反正很简单，就是个array里面每个元素都有可能有一个指针指向下一个要去的地方。这样就有O(1) access, which is better than linked list. |
|
H**r
发帖数: 10015 | 5 ftp://ftp.cs.umd.edu/pub/skipLists/skiplists.pdf |
|
b*****o
发帖数: 715 | 6 面试时我曾被问过skiplist的implementation。
不过有此也可见，面试官是expect你没有学过skiplist的，不然出这题就太小儿科了。 |
|
|
h*********n
发帖数: 11319 | 8 空间换时间，hashtable或者skiplist |
|
p*****u
发帖数: 310 | 9 Thanks a lot. I never thought it would be in the original paper. |
|
z*****n
发帖数: 447 | 10 来自主题: JobHunting版 - 问一道老题 跳表是不是skiplist
成的链表把。。 |
|
a*******y
发帖数: 1040 | 11 写code实现struct skip_list * find(struct skip_list *head, int value)
还有这个struct怎么定义？ |
|
|
|
w****x
发帖数: 2483 | 14 //How to find a value in a skip list
//about skip-list http://en.wikipedia.org/wiki/File:Skip_list.svg
struct SKIP_NODE
{
int nVal;
vector links;
};
//sort like binary search, scope down to decrease the searching range
SKIP_NODE* Find(SKIP_NODE* pHead, int x)
{
assert(pHead);
SKIP_NODE* pCur = pHead;
int nIndex = pHead->links.size() - 1;
while (nIndex >= 0)
{
if (pCur->nVal == x)
return pCur;
if (pCur->links[nIndex] == NULL ||
... 阅读全帖 |
|
p*****2
发帖数: 21240 | 15
牛x，这个有时间得学习一下。上次有人提到跳表我一点也不懂。 |
|
|
M*******a
发帖数: 1633 | 17 不学过怎么知道什么是skiplist聂
学过知道了implement应该蛮简单 |
|
b*****o
发帖数: 715 | 18 面试官直接拿了张skiplist示意图来，然后描述这个图是干什么的。 |
|
h*******e
发帖数: 125 | 19 【 以下文字转载自 Seattle 讨论区 】
发信人: hashtable (skiplist), 信区: Seattle
标 题: 请问微软面试
发信站: BBS 未名空间站 (Mon Apr 28 11:37:01 2014, 美东)
给offer是hiring manager说了算，还是有一个hiring committee来投票决定？ |
|
|
h*******e
发帖数: 125 | 21 【 以下文字转载自 JobHunting 讨论区 】
发信人: hashtable (skiplist), 信区: JobHunting
标 题: Netflix用什么Java Framework
发信站: BBS 未名空间站 (Wed Jan 29 17:13:17 2014, 美东)
用Spring, Hibernate吗？还是EJB?他家面试算法要达到什么水准？有狗家/非死不可难
吗？ |
|
