j******2
发帖数: 362 | 1 板上原来有人面经里的：
search box的search suggestion function。 不一定是exactly prefix matching. 例
如type一个人的middle 或者是last name, match 的也要出现在search box 里面。
用trie吧，没搞懂如果type in "xyz"， 姓"xyz"和名"xyz"的咋能都reach? |
x*********w
发帖数: 533 | 2
trie吧， 用trie存储所有名字的所有后缀？
【在 j******2 的大作中提到】
: 板上原来有人面经里的：
: search box的search suggestion function。 不一定是exactly prefix matching. 例
: 如type一个人的middle 或者是last name, match 的也要出现在search box 里面。
: 用trie吧，没搞懂如果type in "xyz"， 姓"xyz"和名"xyz"的咋能都reach?
|
w********p
发帖数: 948 | 3 这个要再清楚点。
比如一个人的名字是 Steven Paul Jobs
当你type "aul" 的时候 Steven Paul Jobs 要不要显示。
假设是说,当你type
S
St
Ste
Stev
Steve
P
Pa
Pau
Paul
J
Jo
Job
Jobs
的时候Steven Paul Jobs的名字都要被显示。
那么就很简单了
把每个单词 都放在Trie tree 里， 同时建个map，把每个单词和full nam对应起来。
Steven -> Steven Paul Jobs
-> Steven Gnome
Paul -> Steven Paul Jobs
-> Paul Xu
Jobs -> Steven Paul Jobs
-> Jessica Jobs
【在 j******2 的大作中提到】
: 板上原来有人面经里的：
: search box的search suggestion function。 不一定是exactly prefix matching. 例
: 如type一个人的middle 或者是last name, match 的也要出现在search box 里面。
: 用trie吧，没搞懂如果type in "xyz"， 姓"xyz"和名"xyz"的咋能都reach?
|
j******2
发帖数: 362 | 4 明白了，谢谢大牛！！
【在 w********p 的大作中提到】
: 这个要再清楚点。
: 比如一个人的名字是 Steven Paul Jobs
: 当你type "aul" 的时候 Steven Paul Jobs 要不要显示。
: 假设是说,当你type
: S
: St
: Ste
: Stev
: Steve
: P
|
d**e
发帖数: 6098 | 5 如果输入aul时也要显示呢？
【在 w********p 的大作中提到】
: 这个要再清楚点。
: 比如一个人的名字是 Steven Paul Jobs
: 当你type "aul" 的时候 Steven Paul Jobs 要不要显示。
: 假设是说,当你type
: S
: St
: Ste
: Stev
: Steve
: P
|
j******2
发帖数: 362 | 6 ［新加一问］：
怎么把priority加到trie的数据结构里
priority #1 : 在你的friend list 里面
priority #2 : 在你的second degree friend list 里面
priority #3 ： 当前hot query search like ipad3, iphone5 之类的. |
w********p
发帖数: 948 | 7 Trie 的建立或者搜索就要改。
或者Paul, aul, ul l 都塞到trie里。
或者trie的每个节点都要搜，－－ 这种就不如直接map了。
【在 d**e 的大作中提到】
: 如果输入aul时也要显示呢？
|
w********p
发帖数: 948 | 8 加priority 不过是多了些条件而已
有多种方法解决。
比如在map里first name/ last name/ middle name 对应的不是一个full name, 而是
一个class object 其中包括 full name，priority 等等。但是这个方法慢， memory
用的多
或者在你建立trie的时候，就是按照friendship degree 分的。
这样会快些，但是space 要多些。如果像是facebook, linkedin这种数据量很大的，这
个比上个方法好些。
仅供讨论，毕竟没有仔细想，和写。
【在 j******2 的大作中提到】
: 板上原来有人面经里的：
: search box的search suggestion function。 不一定是exactly prefix matching. 例
: 如type一个人的middle 或者是last name, match 的也要出现在search box 里面。
: 用trie吧，没搞懂如果type in "xyz"， 姓"xyz"和名"xyz"的咋能都reach?
|
c******a
发帖数: 789 | 9 按照friendship degree分建造trie，这是说：每个user按degree level得有好几个
trie，trie里是他同degree所有connection。这空间可是n^2哦。但因为pre－process
了，查起来会快很多。
第一个方法要online地sort，会慢。但不明白为啥memeory用得多。
memory
【在 w********p 的大作中提到】
: 加priority 不过是多了些条件而已
: 有多种方法解决。
: 比如在map里first name/ last name/ middle name 对应的不是一个full name, 而是
: 一个class object 其中包括 full name，priority 等等。但是这个方法慢， memory
: 用的多
: 或者在你建立trie的时候，就是按照friendship degree 分的。
: 这样会快些，但是space 要多些。如果像是facebook, linkedin这种数据量很大的，这
: 个比上个方法好些。
: 仅供讨论，毕竟没有仔细想，和写。
|
r**h
发帖数: 1288 | 10 感谢指点！不过有一种情况我不大明白：
可以想见每个用户的priority情况都不一样的（比如说A是B的好友但未必是C的好友）
。那种情况下应该如何处理呢？面对每个用户都建立一个包含所有用户信息的trie感觉
不现实啊
或者说每个用户，因为他的好友数这些都很有限。因此可以在他的好友里面直接先查了
，如果不行的话，再到general的trie里面去查？
memory
【在 w********p 的大作中提到】
: 加priority 不过是多了些条件而已
: 有多种方法解决。
: 比如在map里first name/ last name/ middle name 对应的不是一个full name, 而是
: 一个class object 其中包括 full name，priority 等等。但是这个方法慢， memory
: 用的多
: 或者在你建立trie的时候，就是按照friendship degree 分的。
: 这样会快些，但是space 要多些。如果像是facebook, linkedin这种数据量很大的，这
: 个比上个方法好些。
: 仅供讨论，毕竟没有仔细想，和写。
|
x*****0
发帖数: 452 | |
w******j
发帖数: 185 | |
s*******e
发帖数: 1630 | |
w******j
发帖数: 185 | |
