问个f家的设计题 - 未名空间MITBBS历史存档

国际科技财经博客移民网络热点娱乐民生时事公众号

Redian新闻

>未名空间

>JobHunting - 待字闺中

问个f家的设计题

问个f家的设计题# JobHunting - 待字闺中

j*22013-05-21 07:05

1 楼

板上原来有人面经里的：
search box的search suggestion function。不一定是exactly prefix matching. 例
如type一个人的middle 或者是last name, match 的也要出现在search box 里面。
用trie吧，没搞懂如果type in "xyz"，姓"xyz"和名"xyz"的咋能都reach?

x*w2013-05-21 07:05

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*p2013-05-21 07:05

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 的大作中提到】

j*22013-05-21 07:05

4 楼

明白了，谢谢大牛！！

【在 w********p 的大作中提到】

: 这个要再清楚点。
: 比如一个人的名字是 Steven Paul Jobs
: 当你type "aul" 的时候 Steven Paul Jobs 要不要显示。
: 假设是说,当你type
: S
: St
: Ste
: Stev
: Steve
: P

d*e2013-05-21 07:05

5 楼

如果输入aul时也要显示呢？

【在 w********p 的大作中提到】

: 这个要再清楚点。
: 比如一个人的名字是 Steven Paul Jobs
: 当你type "aul" 的时候 Steven Paul Jobs 要不要显示。
: 假设是说,当你type
: S
: St
: Ste
: Stev
: Steve
: P

j*22013-05-21 07:05

6 楼

［新加一问］：
怎么把priority加到trie的数据结构里
priority #1 : 在你的friend list 里面
priority #2 : 在你的second degree friend list 里面
priority #3 ：当前hot query search like ipad3, iphone5 之类的.

w*p2013-05-21 07:05

7 楼

Trie 的建立或者搜索就要改。
或者Paul, aul, ul l 都塞到trie里。
或者trie的每个节点都要搜，－－这种就不如直接map了。

【在 d**e 的大作中提到】

: 如果输入aul时也要显示呢？

w*p2013-05-21 07:05

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 的大作中提到】

c*a2013-05-21 07:05

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*h2013-05-21 07:05

10 楼

感谢指点！不过有一种情况我不大明白：
可以想见每个用户的priority情况都不一样的（比如说A是B的好友但未必是C的好友）
。那种情况下应该如何处理呢？面对每个用户都建立一个包含所有用户信息的trie感觉
不现实啊
或者说每个用户，因为他的好友数这些都很有限。因此可以在他的好友里面直接先查了
，如果不行的话，再到general的trie里面去查？

memory

【在 w********p 的大作中提到】