an interview problem - 未名空间MITBBS历史存档

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

Redian新闻

>未名空间

>Programming - 葵花宝典

an interview problem

an interview problem# Programming - 葵花宝典

m*t2007-01-06 08:01

1 楼

write the program for displaying the ten most frequent words in a file such
that your program should be efficient in all complexity measures.
I think hash table with counting will be a natual solution, but not sure if
it is a best fit for this problem.

m*k2007-01-06 08:01

2 楼

hashtable or b+ tree/trie like dictinonary data structure etc only provide
fast search/index, so still need additional data structure on the frequnecy
order statistics. A min-heap is ok. or you can use another b+ tree to store
the frequency as key

such
if

【在 m***t 的大作中提到】

: write the program for displaying the ten most frequent words in a file such
: that your program should be efficient in all complexity measures.
: I think hash table with counting will be a natual solution, but not sure if
: it is a best fit for this problem.

m*t2007-01-06 08:01

3 楼

I guess u mean max heap to store frequency, right?

frequnecy
store

【在 m******k 的大作中提到】

: hashtable or b+ tree/trie like dictinonary data structure etc only provide
: fast search/index, so still need additional data structure on the frequnecy
: order statistics. A min-heap is ok. or you can use another b+ tree to store
: the frequency as key
:
: such
: if

m*k2007-01-06 08:01

4 楼

I mean a min-heap of size 10 store top 10 most frequence words on the fly.
because we need to compare other candidates with the least frequent one of
the top 10 to determine whether do a replcaement. Other operation on the min
-heap includes increase_key if anyone of the current top 10 get hit again.
of course, a max-heap also works, but it seems you need to store the entire
N elements to determine the top 10.

I guess u mean max heap to store frequency, right?
frequnecy
store

【在 m***t 的大作中提到】

: I guess u mean max heap to store frequency, right?
:
: frequnecy
: store

m*t2007-01-06 08:01

5 楼

//blush. That is absolutely right.

min
entire

【在 m******k 的大作中提到】

: I mean a min-heap of size 10 store top 10 most frequence words on the fly.
: because we need to compare other candidates with the least frequent one of
: the top 10 to determine whether do a replcaement. Other operation on the min
: -heap includes increase_key if anyone of the current top 10 get hit again.
: of course, a max-heap also works, but it seems you need to store the entire
: N elements to determine the top 10.
:
: I guess u mean max heap to store frequency, right?
: frequnecy
: store