问一道面试设计题 - 未名空间MITBBS历史存档

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

Redian新闻

>未名空间

>JobHunting - 待字闺中

问一道面试设计题

问一道面试设计题# JobHunting - 待字闺中

e*32015-10-10 07:10

1 楼

题目就是类似电话里通讯录的搜索功能. 输入一个人人名的前几个字母,会弹出一堆有
相同前几个字母的人.但是这些人要根据被拨打次数的多少从高到低进行排序.面试官貌
似不是想要trie的做法,而且用trie的话因为要排序那这个搜索时间也应该很长. 求大
牛解答

l*s2015-10-10 07:10

2 楼

TrieNode上加个call times field,然后用搜索结果放到SortedSet里就可以
，创建TrieNode时指定一个排序的方法，按照call times排即可。时间复杂度O(nlgn)
，n是Trie搜索的结果长度。

e*32015-10-10 07:10

3 楼

不懂.
比如你输入a, 那你要搜索a下面所有trienode,然后再把搜索结果进行排序吧?
"创建TrieNode时指定一个排序的方法，按照call times排即可"
这是什么意思

【在 l******s 的大作中提到】

: TrieNode上加个call times field,然后用搜索结果放到SortedSet里就可以
: ，创建TrieNode时指定一个排序的方法，按照call times排即可。时间复杂度O(nlgn)
: ，n是Trie搜索的结果长度。

e*22015-10-10 07:10

4 楼

https://en.wikipedia.org/wiki/Treap

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

:
: 不懂.
: 比如你输入a, 那你要搜索a下面所有trienode,然后再把搜索结果进行排序吧?
: "创建TrieNode时指定一个排序的方法，按照call times排即可"
: 这是什么意思

e*32015-10-10 07:10

5 楼

这个treap如何应用到这道题上?
比如:
名字 call times
abc 50
abcd 100
abd 200
怎么通过call times在trie中进行排序?

l*s2015-10-10 07:10

6 楼

有笔误，应该是创建SortedSet时指定一个排序方法。比如下面：
SortedSet ss = new SortedSet(Comparer.Create((
a, b) => a.CallTimes == b.CallTimes ? a.PhoneName.CompareTo(b.PhoneName) : b.
CallTimes.CompareTo(a.CallTimes)));
我用的是C#，Java也有类似的创建自定义的排序的Compare的方法。

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

: 这个treap如何应用到这道题上?
: 比如:
: 名字 call times
: abc 50
: abcd 100
: abd 200
: 怎么通过call times在trie中进行排序?