r***u
发帖数: 241 | 1 有一个排好序的词典，大小未知，唯一的接口就是查询某个index对应的单词，如果该
index超出词典大小则返回null
如何最快的判断一个给定的单词是否在词典中。 |
l*****a
发帖数: 14598 | 2 可以对这个字典进行重新处理吗？
可以的话就弄个trie...
不可以的话就按照index 2,4,8,16,32 去search,
比较target与index那个词的大小，然后再binary search
【在 r***u 的大作中提到】
: 有一个排好序的词典，大小未知，唯一的接口就是查询某个index对应的单词，如果该
: index超出词典大小则返回null
: 如何最快的判断一个给定的单词是否在词典中。
|
A*********r
发帖数: 564 | 3 呵呵，貌似是一个以前的on-site题。。
大小未知，估计要doubling+binary search。
不过不知道这道题要考察什么？是否知道doubling?
【在 r***u 的大作中提到】
: 有一个排好序的词典，大小未知，唯一的接口就是查询某个index对应的单词，如果该
: index超出词典大小则返回null
: 如何最快的判断一个给定的单词是否在词典中。
|
r***u
发帖数: 241 | 4 什么是doubling？我说了binary search，但不够perfect。
他希望既能快速找到index小的，又能找到大的
【在 A*********r 的大作中提到】
: 呵呵，貌似是一个以前的on-site题。。
: 大小未知，估计要doubling+binary search。
: 不过不知道这道题要考察什么？是否知道doubling?
|
c**********e
发帖数: 2007 | 5 Step 1. Double/half bah. Start with a guess, say n=10000. If the w[n] is "less" than the given word, double it, check w[2n]. If w[n] is "greater" than, check w[n/2].
Step 2. Binary search. Eventually, you will find a range m...n, the word is between w[m] and w[n]. Then perform binary search to figure it out.
【在 r***u 的大作中提到】
: 有一个排好序的词典，大小未知，唯一的接口就是查询某个index对应的单词，如果该
: index超出词典大小则返回null
: 如何最快的判断一个给定的单词是否在词典中。
|
r***u
发帖数: 241 | 6 I said something like this. He then asked why start with such a guess?
It's inefficient for small dictionaries.
less" than the given word, double it, check w[2n]. If w[n] is "greater" than
, check w[n/2].
is between w[m] and w[n]. Then perform binary search to figure it out.
【在 c**********e 的大作中提到】
: Step 1. Double/half bah. Start with a guess, say n=10000. If the w[n] is "less" than the given word, double it, check w[2n]. If w[n] is "greater" than, check w[n/2].
: Step 2. Binary search. Eventually, you will find a range m...n, the word is between w[m] and w[n]. Then perform binary search to figure it out.
|
s*****n
发帖数: 5488 | 7 因为大小不知道。不能直接上binary search。所有回帖的算法是正确的。
【在 r***u 的大作中提到】
: 什么是doubling？我说了binary search，但不够perfect。
: 他希望既能快速找到index小的，又能找到大的
|
r***u
发帖数: 241 | 8 可是面试官貌似还是不满意的样子。难道是交流出了问题？碰到了阿三哥哥
【在 s*****n 的大作中提到】
: 因为大小不知道。不能直接上binary search。所有回帖的算法是正确的。
|
A*********r
发帖数: 564 | 9 呵呵，如果你感觉他还是不满意，可以问一下hint..
【在 r***u 的大作中提到】
: 可是面试官貌似还是不满意的样子。难道是交流出了问题？碰到了阿三哥哥
|
s*****n
发帖数: 5488 | 10 看你回帖，他不是让你解释一下最初的n怎么选择吗？
我感觉是个open 问题。
这个算法有两个cases:
1.直接
2. result > n,那么需要doubling+ binary search:复杂度：lg r/lg n +lg r - 1
直观上，n足够大能够让result落入case 1.
那么给出一个middle size的n应该不错。
不知道还有什么更好的方法。
【在 r***u 的大作中提到】
: 可是面试官貌似还是不满意的样子。难道是交流出了问题？碰到了阿三哥哥
|
s*****n
发帖数: 5488 | 11
应该是lg r/n：然后是变成2 lg r - lg n - 1
【在 s*****n 的大作中提到】
: 看你回帖，他不是让你解释一下最初的n怎么选择吗？
: 我感觉是个open 问题。
: 这个算法有两个cases:
: 1.直接: 2. result > n,那么需要doubling+ binary search:复杂度：lg r/lg n +lg r - 1
: 直观上，n足够大能够让result落入case 1.
: 那么给出一个middle size的n应该不错。
: 不知道还有什么更好的方法。
|
h***o
发帖数: 1494 | 12 index是什么type? 知道了就知道最大的可能值。 |
r***u
发帖数: 241 | 13 开始给的unsigned int，我指出后改为BigInt
【在 h***o 的大作中提到】
: index是什么type? 知道了就知道最大的可能值。
|
