s****t
发帖数: 36 | 1 刚刚面的电面，心里没底啊。
1. Given a sorted integer array and a specific integer, find the
first position of that integer. Array contains lots of
duplicate.
我说用binary search， 找到之后然后左移找到第一个于它前一个不一样的，就是
first position。然后他说如果有很多很多的duplicate的话，有没有更快的方
法。然后我就想先binary search找到了middle之后，再在left和middle之间进行
多一次binary search，用一些边界条件什么的判断。 这样算不算改进啊，我觉得应
该是会快点啊。
2. 有很多doc，里面有很多电话，怎么查找电话。
我说只是一次用的，hash一下找，如果以后还得用的话，就sort他们，然后按area
code做一个B tree什么的。
3. 在一个resume里面找电话。
我说如果是US的话找一个连续是10个digit的，或者中间有（）或-的，然后查头三个
digits是不是va |
g*******y
发帖数: 1930 | 2 1. preprocessing the array to get an array of pair
4. also preprocessing the dictionary. |
h**k
发帖数: 3368 | 3
duplicate的值形成一个list？
【在 g*******y 的大作中提到】
: 1. preprocessing the array to get an array of pair
: 4. also preprocessing the dictionary.
|
g*******y
发帖数: 1930 | 4 hehe, I realized no need to build a bst(I was thinking about something else.
..), just preprocess to get：
vector>
where first int is the data, second int is the first occurrence index(
position)
【在 h**k 的大作中提到】
:
: duplicate的值形成一个list？
|
g*******y
发帖数: 1930 | 5 btw,楼主说的
“我说用binary search， 找到之后然后左移找到第一个于它前一个不一样的”
这个是完全没必要的，完全可以调整搜索条件搜索到想找的位置，你这个一个一个的移
，可能是消耗线性的时间
else.
【在 g*******y 的大作中提到】
: hehe, I realized no need to build a bst(I was thinking about something else.
: ..), just preprocess to get：
: vector>
: where first int is the data, second int is the first occurrence index(
: position)
|
m*****y
发帖数: 93 | 6
index>
In case no preprocessing, if find the key, store current index and keep
searching to the left until reach the leaf. If finds other keys, update
current index. This is O(logn)
How to preprocess? thanks
【在 g*******y 的大作中提到】
: 1. preprocessing the array to get an array of pair
: 4. also preprocessing the dictionary.
|
g*******y
发帖数: 1930 | 7 不做preprocessing就是一个普通的binary search，没啥好多讲的了，只是楼主一个一个左移的方法太差了，他面试官才问他怎么优化的。
【在 m*****y 的大作中提到】
:
: index>
: In case no preprocessing, if find the key, store current index and keep
: searching to the left until reach the leaf. If finds other keys, update
: current index. This is O(logn)
: How to preprocess? thanks
|
m*****y
发帖数: 93 | 8 嗯，不过面试应该从易到难吧，第一题应该不难
第四题怎样preprocess？按数字查询的B-tree？
Thanks LZ for posting, bless
一个左移
的方法太差了，他面试官才问他怎么优化的。
【在 g*******y 的大作中提到】
: 不做preprocessing就是一个普通的binary search，没啥好多讲的了，只是楼主一个一个左移的方法太差了，他面试官才问他怎么优化的。
|
r****o
发帖数: 1950 | 9 第3题是考算法吗，还是regular expression?
【在 s****t 的大作中提到】
: 刚刚面的电面，心里没底啊。
: 1. Given a sorted integer array and a specific integer, find the
: first position of that integer. Array contains lots of
: duplicate.
: 我说用binary search， 找到之后然后左移找到第一个于它前一个不一样的，就是
: first position。然后他说如果有很多很多的duplicate的话，有没有更快的方
: 法。然后我就想先binary search找到了middle之后，再在left和middle之间进行
: 多一次binary search，用一些边界条件什么的判断。 这样算不算改进啊，我觉得应
: 该是会快点啊。
: 2. 有很多doc，里面有很多电话，怎么查找电话。
|
w*****r
发帖数: 2061 | 10 电话是那种字母表示的怎么办?
【在 s****t 的大作中提到】
: 刚刚面的电面，心里没底啊。
: 1. Given a sorted integer array and a specific integer, find the
: first position of that integer. Array contains lots of
: duplicate.
: 我说用binary search， 找到之后然后左移找到第一个于它前一个不一样的，就是
: first position。然后他说如果有很多很多的duplicate的话，有没有更快的方
: 法。然后我就想先binary search找到了middle之后，再在left和middle之间进行
: 多一次binary search，用一些边界条件什么的判断。 这样算不算改进啊，我觉得应
: 该是会快点啊。
: 2. 有很多doc，里面有很多电话，怎么查找电话。
|
|
|
r****o
发帖数: 1950 | 11 preprocessing这一步的的复杂度是不是O(n)？
考官是不是要O(lgn)的复杂度？
一个左移的方法太差了，他面试官才问他怎么优化的。
【在 g*******y 的大作中提到】
: 不做preprocessing就是一个普通的binary search，没啥好多讲的了，只是楼主一个一个左移的方法太差了，他面试官才问他怎么优化的。
|
g*******y
发帖数: 1930 | 12 预处理在于一个预字上
【在 r****o 的大作中提到】
: preprocessing这一步的的复杂度是不是O(n)？
: 考官是不是要O(lgn)的复杂度？
:
: 一个左移的方法太差了，他面试官才问他怎么优化的。
|
r****o
发帖数: 1950 | 13 就是说为了方便后面的处理，预处理可以复杂度很高?
【在 g*******y 的大作中提到】
: 预处理在于一个预字上
|
g*******y
发帖数: 1930 | 14 一般预处理的目的是这个，
不过这个题的情况下，预处理也提高不了太多。
【在 r****o 的大作中提到】
: 就是说为了方便后面的处理，预处理可以复杂度很高?
|
g*******y
发帖数: 1930 | 15 其实第四题也是我电面遇到的题，一模一样的。
【在 m*****y 的大作中提到】
: 嗯，不过面试应该从易到难吧，第一题应该不难
: 第四题怎样preprocess？按数字查询的B-tree？
: Thanks LZ for posting, bless
:
: 一个左移
: 的方法太差了，他面试官才问他怎么优化的。
|
s*****i
发帖数: 355 | 16 预处理是把字典的词转换成数字，然后sort
binary search找给定的要查找的数
【在 g*******y 的大作中提到】
: 其实第四题也是我电面遇到的题，一模一样的。
|
c****s
发帖数: 241 | 17 第四题就是把字典里面的单词都用2～9来表示，然后存下来，可以提高直接查找。
还有没有什么更好的方法？
【在 g*******y 的大作中提到】
: 其实第四题也是我电面遇到的题，一模一样的。
|
g*******y
发帖数: 1930 | 18 why sort？
what's the benefit if you sort?
can you do something other than sort?
【在 s*****i 的大作中提到】
: 预处理是把字典的词转换成数字，然后sort
: binary search找给定的要查找的数
|
m****u
发帖数: 3915 | 19 第一题如果中数与目标数相等，当大于处理就行了吧 |
r****o
发帖数: 1950 | 20 hash?
【在 g*******y 的大作中提到】
: why sort？
: what's the benefit if you sort?
: can you do something other than sort?
|
|
|
r****o
发帖数: 1950 | 21 顶一下。
【在 r****o 的大作中提到】
: 第3题是考算法吗，还是regular expression?
|
s*****i
发帖数: 355 | 22 为啥不sort，你可以指点一下我嘛，不要这么凶 谢谢
还有一个办法是把字典做成trie map，DFS
【在 g*******y 的大作中提到】
: why sort？
: what's the benefit if you sort?
: can you do something other than sort?
|
w******k
发帖数: 917 | 23 你sort怎么弄？
最后找到1256这个是一个word,你怎么返回build word?
【在 s*****i 的大作中提到】
: 为啥不sort，你可以指点一下我嘛，不要这么凶 谢谢
: 还有一个办法是把字典做成trie map，DFS
|
g*******y
发帖数: 1930 | 24 我是学面试官的口吻向你提问
【在 s*****i 的大作中提到】
: 为啥不sort，你可以指点一下我嘛，不要这么凶 谢谢
: 还有一个办法是把字典做成trie map，DFS
|
w******k
发帖数: 917 | 25 in an A3 way
【在 g*******y 的大作中提到】
: 我是学面试官的口吻向你提问
|
B*****t
发帖数: 335 | 26 1. 这题比较无聊。不过如果知道expected number of duplicate k(>4)的话，二分找
到后每次跳k/2，k/4...步找first position。
好像可以预处理，搞个hash岂不很快？
谁有不预处理更快一些的方法？
2. 觉得没有必要sort， 同一个电话号码可能出现在几个不同的doc中，预处理的话，
对每个doc设计一个相同的hash函数，能节省一些search的时间。不知道还有没有更好
的办法。
3. 好像也是比较无聊的题。
4. 这种题一般来说字典里的word的数目是一定的。可以构造一个trie，检查一个数的
valid就是检查这个trie中有没有valid 的path。 不知道还有什么更好的方法。
【在 s****t 的大作中提到】
: 刚刚面的电面，心里没底啊。
: 1. Given a sorted integer array and a specific integer, find the
: first position of that integer. Array contains lots of
: duplicate.
: 我说用binary search， 找到之后然后左移找到第一个于它前一个不一样的，就是
: first position。然后他说如果有很多很多的duplicate的话，有没有更快的方
: 法。然后我就想先binary search找到了middle之后，再在left和middle之间进行
: 多一次binary search，用一些边界条件什么的判断。 这样算不算改进啊，我觉得应
: 该是会快点啊。
: 2. 有很多doc，里面有很多电话，怎么查找电话。
|
g*******y
发帖数: 1930 | 27 你准备面试的时候，难道都不假定面试官都是刁难你的？我以前就说过，做题后要不停
的继续思考为什么这么做，有没有其他的方法，不要以为做出一个题目就好了。准备面
试的目的就是不停的用题目去扩展自己的思路，磨炼自己的头脑。你事先准备的充分了
，面试的时候遇到面试官换着花样问，你也就不怕不会呆在那里发愣了。
这种问了一个问题后不停的问why，what else can you think of的例子太多了，跟阿
三没关系
【在 w******k 的大作中提到】
: in an A3 way
|
w******k
发帖数: 917 | 28 第一题我觉得你们想复杂了
考官说如果很多很多重复，明显就是针对lz说的传统binary search加向前线形，这样可
能o(n),只要稍微修改算法，如果mid is equal就search前半部分（同理如果找最后一个
occurence就找后半部分）
我觉得interviewer的意图就这么简单
【在 B*****t 的大作中提到】
: 1. 这题比较无聊。不过如果知道expected number of duplicate k(>4)的话，二分找
: 到后每次跳k/2，k/4...步找first position。
: 好像可以预处理，搞个hash岂不很快？
: 谁有不预处理更快一些的方法？
: 2. 觉得没有必要sort， 同一个电话号码可能出现在几个不同的doc中，预处理的话，
: 对每个doc设计一个相同的hash函数，能节省一些search的时间。不知道还有没有更好
: 的办法。
: 3. 好像也是比较无聊的题。
: 4. 这种题一般来说字典里的word的数目是一定的。可以构造一个trie，检查一个数的
: valid就是检查这个trie中有没有valid 的path。 不知道还有什么更好的方法。
|
s*****i
发帖数: 355 | 29 1256是个key，后面带一个数组存着所有符合条件的单词
这个主要就是预处理了，用hash也可以
【在 w******k 的大作中提到】
: 你sort怎么弄？
: 最后找到1256这个是一个word,你怎么返回build word?
|
w******k
发帖数: 917 | 30 开玩笑的啦
这种穷追猛打的面试，一般公司都这样的呵呵
你说的很有效
【在 g*******y 的大作中提到】
: 你准备面试的时候，难道都不假定面试官都是刁难你的？我以前就说过，做题后要不停
: 的继续思考为什么这么做，有没有其他的方法，不要以为做出一个题目就好了。准备面
: 试的目的就是不停的用题目去扩展自己的思路，磨炼自己的头脑。你事先准备的充分了
: ，面试的时候遇到面试官换着花样问，你也就不怕不会呆在那里发愣了。
: 这种问了一个问题后不停的问why，what else can you think of的例子太多了，跟阿
: 三没关系
|
|
|
g*******y
发帖数: 1930 | 31 right
样可
一个
【在 w******k 的大作中提到】
: 第一题我觉得你们想复杂了
: 考官说如果很多很多重复，明显就是针对lz说的传统binary search加向前线形，这样可
: 能o(n),只要稍微修改算法，如果mid is equal就search前半部分（同理如果找最后一个
: occurence就找后半部分）
: 我觉得interviewer的意图就这么简单
|
s****t
发帖数: 36 | 32 preprocessing 不是也要花时间吗？你是说做linear的然后把每个的第一个存起来
啊？
但是他好像没有要求多次使用啊，只是说找一个数的第一个，所有后来改了个两次
binary
search啊。linear 一个一个的记录的话不是要用o（n）吗？
个一个左移的方法太差了，他面试官才问他怎么优化的。
【在 g*******y 的大作中提到】
: 不做preprocessing就是一个普通的binary search，没啥好多讲的了，只是楼主一个一个左移的方法太差了，他面试官才问他怎么优化的。
|
w******k
发帖数: 917 | 33 u only need one round of binary search
【在 s****t 的大作中提到】
: preprocessing 不是也要花时间吗？你是说做linear的然后把每个的第一个存起来
: 啊？
: 但是他好像没有要求多次使用啊，只是说找一个数的第一个，所有后来改了个两次
: binary
: search啊。linear 一个一个的记录的话不是要用o（n）吗？
:
: 个一个左移的方法太差了，他面试官才问他怎么优化的。
|
g*******y
发帖数: 1930 | 34 your concern is right, whether or not to use preprocessing is determined by:
the performance boost + processing cost + how many queries in the future
by the way, as already explained in previous posts, there's no need to do
binary search twice.
【在 s****t 的大作中提到】
: preprocessing 不是也要花时间吗？你是说做linear的然后把每个的第一个存起来
: 啊？
: 但是他好像没有要求多次使用啊，只是说找一个数的第一个，所有后来改了个两次
: binary
: search啊。linear 一个一个的记录的话不是要用o（n）吗？
:
: 个一个左移的方法太差了，他面试官才问他怎么优化的。
|
P****i
发帖数: 1362 | 35 第一个，找x-0.5，只剩两个数时判断一下
【在 s****t 的大作中提到】
: 刚刚面的电面，心里没底啊。
: 1. Given a sorted integer array and a specific integer, find the
: first position of that integer. Array contains lots of
: duplicate.
: 我说用binary search， 找到之后然后左移找到第一个于它前一个不一样的，就是
: first position。然后他说如果有很多很多的duplicate的话，有没有更快的方
: 法。然后我就想先binary search找到了middle之后，再在left和middle之间进行
: 多一次binary search，用一些边界条件什么的判断。 这样算不算改进啊，我觉得应
: 该是会快点啊。
: 2. 有很多doc，里面有很多电话，怎么查找电话。
|
k***e
发帖数: 556 | 36 终于可以鄙视下小羊了 哈哈
exactly the same problem in programming pearls, binary search chapter
note that, we need to keep loop invariant [l,r) such that a[l]<= wanted
stop when l = r - 1
index>
【在 g*******y 的大作中提到】
: 1. preprocessing the array to get an array of pair
: 4. also preprocessing the dictionary.
|
h*******x
发帖数: 12808 | 37 大赞，//bless
【在 s****t 的大作中提到】
: 刚刚面的电面，心里没底啊。
: 1. Given a sorted integer array and a specific integer, find the
: first position of that integer. Array contains lots of
: duplicate.
: 我说用binary search， 找到之后然后左移找到第一个于它前一个不一样的，就是
: first position。然后他说如果有很多很多的duplicate的话，有没有更快的方
: 法。然后我就想先binary search找到了middle之后，再在left和middle之间进行
: 多一次binary search，用一些边界条件什么的判断。 这样算不算改进啊，我觉得应
: 该是会快点啊。
: 2. 有很多doc，里面有很多电话，怎么查找电话。
|
g*******y
发帖数: 1930 | 38 汗，晕，我知道这个啊
r]
【在 k***e 的大作中提到】
: 终于可以鄙视下小羊了 哈哈
: exactly the same problem in programming pearls, binary search chapter
: note that, we need to keep loop invariant [l,r) such that a[l]<= wanted: stop when l = r - 1
:
: index>
|
s********f
发帖数: 510 | 39 1如果preprocess不就O(n)了.
index>
【在 g*******y 的大作中提到】
: 1. preprocessing the array to get an array of pair
: 4. also preprocessing the dictionary.
|
r****o
发帖数: 1950 | 40 这个第3题是不是考regular expression啊？还是考算法的？
【在 s****t 的大作中提到】
: 刚刚面的电面，心里没底啊。
: 1. Given a sorted integer array and a specific integer, find the
: first position of that integer. Array contains lots of
: duplicate.
: 我说用binary search， 找到之后然后左移找到第一个于它前一个不一样的，就是
: first position。然后他说如果有很多很多的duplicate的话，有没有更快的方
: 法。然后我就想先binary search找到了middle之后，再在left和middle之间进行
: 多一次binary search，用一些边界条件什么的判断。 这样算不算改进啊，我觉得应
: 该是会快点啊。
: 2. 有很多doc，里面有很多电话，怎么查找电话。
|
|
|
h*******x
发帖数: 12808 | 41 suffix tree?
【在 r****o 的大作中提到】
: hash?
|
h*******x
发帖数: 12808 | 42 第一个都是整数的话，这样做如何？
比如要a，我就去查找a-0.5。bsearch找到第一个比a-0.5大的数，对比一下就好了，这
样就是o（logn）了。
【在 B*****t 的大作中提到】
: 1. 这题比较无聊。不过如果知道expected number of duplicate k(>4)的话，二分找
: 到后每次跳k/2，k/4...步找first position。
: 好像可以预处理，搞个hash岂不很快？
: 谁有不预处理更快一些的方法？
: 2. 觉得没有必要sort， 同一个电话号码可能出现在几个不同的doc中，预处理的话，
: 对每个doc设计一个相同的hash函数，能节省一些search的时间。不知道还有没有更好
: 的办法。
: 3. 好像也是比较无聊的题。
: 4. 这种题一般来说字典里的word的数目是一定的。可以构造一个trie，检查一个数的
: valid就是检查这个trie中有没有valid 的path。 不知道还有什么更好的方法。
|
d******a
发帖数: 238 | 43 For the second problem, maybe we should also consider the number and size of
files. when I meet the problems about finding sth in files, I might say
mergesort (external sorting)first. Because the memory may not contain the
whole hash table. If the interviewer has performance requirement, I will
think some other solution such as hash.
【在 s****t 的大作中提到】
: 刚刚面的电面，心里没底啊。
: 1. Given a sorted integer array and a specific integer, find the
: first position of that integer. Array contains lots of
: duplicate.
: 我说用binary search， 找到之后然后左移找到第一个于它前一个不一样的，就是
: first position。然后他说如果有很多很多的duplicate的话，有没有更快的方
: 法。然后我就想先binary search找到了middle之后，再在left和middle之间进行
: 多一次binary search，用一些边界条件什么的判断。 这样算不算改进啊，我觉得应
: 该是会快点啊。
: 2. 有很多doc，里面有很多电话，怎么查找电话。
|
i**********b
发帖数: 77 | 44 I don't think sorting is needed. The numbers converted from letters are
naturally sorted.
I'm thinking if some other utilities can be provided by the dictionary, such
as get the set of words that have the
same length.
No chinese input. sorry.
【在 g*******y 的大作中提到】
: why sort？
: what's the benefit if you sort?
: can you do something other than sort?
|
a***o
发帖数: 118 | 45 我怎么觉得第一题是不是想多了? 面试官是不是只是意在优化第二步:一步一步左移?
继续用二叉查找直到找到左边数字不同了就行了吧?
脑子浆糊, 见笑了----- |
b**********7
发帖数: 103 | 46 哈，第一题不用preProcessing, 因为preProcessing 已经是O(n)了。
Programming Perl上有原题，就是把loop的invariant condition 改了，这样
O(log N) 就一定能找到第一次出现的位置。
invariant:
given range A[U, L], query integer t, A[U]
剩两个数的时候，A[L]就是t 第一次出现的位置，或者t不在range中。
occurence index>
【在 g*******y 的大作中提到】
: 1. preprocessing the array to get an array of pair
: 4. also preprocessing the dictionary.
|
b**********7
发帖数: 103 | 47 哈哈，被你抢先一步了，正解！
chapter
wanted
【在 k***e 的大作中提到】
: 终于可以鄙视下小羊了 哈哈
: exactly the same problem in programming pearls, binary search chapter
: note that, we need to keep loop invariant [l,r) such that a[l]<= wanted: stop when l = r - 1
:
: index>
|
r****o
发帖数: 1950 | 48 geniusxys has mentioned before that the preprocessing is a good option in
some cases even if it needs more time, because it saves the time of the
following operations.
【在 b**********7 的大作中提到】
: 哈哈，被你抢先一步了，正解！
:
: chapter
: wanted
|
v****s
发帖数: 1112 | 49 aglee
【在 w******k 的大作中提到】
: in an A3 way
|
v****s
发帖数: 1112 | 50 i vote for trie in problem 4 as well
【在 B*****t 的大作中提到】
: 1. 这题比较无聊。不过如果知道expected number of duplicate k(>4)的话，二分找
: 到后每次跳k/2，k/4...步找first position。
: 好像可以预处理，搞个hash岂不很快？
: 谁有不预处理更快一些的方法？
: 2. 觉得没有必要sort， 同一个电话号码可能出现在几个不同的doc中，预处理的话，
: 对每个doc设计一个相同的hash函数，能节省一些search的时间。不知道还有没有更好
: 的办法。
: 3. 好像也是比较无聊的题。
: 4. 这种题一般来说字典里的word的数目是一定的。可以构造一个trie，检查一个数的
: valid就是检查这个trie中有没有valid 的path。 不知道还有什么更好的方法。
|
|
|
k*******s
发帖数: 134 | 51 第一题很简单吧。我就用java的binary search大概写了一下，3行code
public int FindFirstInteger(double[] arr,int i) {
double x = i - 0.1;
int ret = Arrays.binarySearch(arr,x);
return -(ret+1);
} |
b**********7
发帖数: 103 | 52 Of course preprocessing is good. but if it's allowed for every
questions, and in any extend, then there is no need for algorithm
design. :>
just preprocess everything, and make a hashtable with
answer>, then every query will be answered in O(1).
option in
of the
【在 r****o 的大作中提到】
: geniusxys has mentioned before that the preprocessing is a good option in
: some cases even if it needs more time, because it saves the time of the
: following operations.
|
q*********u
发帖数: 280 | 53 我记得原来有一个帖子，说是成倍的或者指数型倍的向前或者向后跳跃，来搞这种大量
重复元素的数组。
1, 2, 4, 8, 16的跳或者1, 2, 4, 16, 256的跳，
具体怎么写出代码倒是忘了，是不是这样，先binarysearch, 二分的时候，从那个二分
的点开始向前（给定数小于等于的情况），或者向后（给定数大于的情况），然后跳跃？
比如我给定找第一个４，有这么个数组
1, 1, 1, 1,... 1, 2, 2, 2,...2, 3, 3, 3 .... 3, 4444444, 5, 5, 5, ...5, 6, 6
, 6, 6, 6... 6
如果是这样，光是二分，然后外加<=的时候就向前半部分找，丢弃后半部分，这么搞是
不是还是可以再用这个跳跃的办法改进？ 每次对半分的时候都对那个对半的点做跳跃？
Of course preprocessing is good. but if it's allowed for every
questions, and in any extend, then there is no need for algorithm
design.
【在 b**********7 的大作中提到】
: Of course preprocessing is good. but if it's allowed for every
: questions, and in any extend, then there is no need for algorithm
: design. :>
: just preprocess everything, and make a hashtable with : answer>, then every query will be answered in O(1).
:
: option in
: of the
|
m*****g
发帖数: 226 | 54 1. Modify binary search. when u don't find one, find one. when u find one,
check if it is already first occurrence. if not, look for left half.
2. sounds like unix command?
3. sounds open question?
4. for a lot of digits, the possible permutations may be big
maybe preprocessing dict, convert words into numbers, then search for hit in
the orig digits?
【在 s****t 的大作中提到】
: 刚刚面的电面，心里没底啊。
: 1. Given a sorted integer array and a specific integer, find the
: first position of that integer. Array contains lots of
: duplicate.
: 我说用binary search， 找到之后然后左移找到第一个于它前一个不一样的，就是
: first position。然后他说如果有很多很多的duplicate的话，有没有更快的方
: 法。然后我就想先binary search找到了middle之后，再在left和middle之间进行
: 多一次binary search，用一些边界条件什么的判断。 这样算不算改进啊，我觉得应
: 该是会快点啊。
: 2. 有很多doc，里面有很多电话，怎么查找电话。
|
f***g
发帖数: 214 | 55 1. 原题：PP P93
2. 如果没有理解错的话, PP, 第一章
3. 貌似Open Question
4. 好像是PIE原题。 |
l*****a
发帖数: 14598 | 56 for 4,
if only need to care the unique number which the interviewer gave,
(ordered digits) that is the issue in PIE.
if the interviewer just gave a collection of digits, ask the words
they can combined, need pre-processing
【在 f***g 的大作中提到】
: 1. 原题：PP P93
: 2. 如果没有理解错的话, PP, 第一章
: 3. 貌似Open Question
: 4. 好像是PIE原题。
|
P********l
发帖数: 452 | 57 Depends.
suppose there are 1,000 words in the dictionary.
If the telephone number is only 3 digits, you can transform the numbers into
words and lookup the dictionary
to see if it is there. Because there are only 3**3 = 27 kinds of combination
. no pre prcessing needed.
If the telephone is 10 digits, the corresponding space of words is too large
. you have to invert index the
dictionary by telephone numbers. Build a suffix tree and you can directly
lookup the numbers.
【在 c****s 的大作中提到】
: 第四题就是把字典里面的单词都用2～9来表示，然后存下来，可以提高直接查找。
: 还有没有什么更好的方法？
|
P********l
发帖数: 452 | 58 binary search find the number 1 less than the value, return the position.
Check if arr[position+1] is the value.
Or just change the invariant condition. simple.
【在 b**********7 的大作中提到】
: 哈，第一题不用preProcessing, 因为preProcessing 已经是O(n)了。
: Programming Perl上有原题，就是把loop的invariant condition 改了，这样
: O(log N) 就一定能找到第一次出现的位置。
: invariant:
: given range A[U, L], query integer t, A[U]: 剩两个数的时候，A[L]就是t 第一次出现的位置，或者t不在range中。
:
: occurence index>
|
