作者Leon (Achilles)
站内Prob_Solve
标题Re: [问题] Google Interview Question (4)
时间Sat Mar 9 17:51:29 2013
※ 引述《stimim (qqaa)》之铭言：
: 推 scwg:我 (ledia 应该也是) 自动采用 2. 的解释, 因为 inverse 03/09 03:21
: → scwg:list 可以 offline 建好, 之後这个演算法可以重复多次 03/09 03:22
: 我的想法和 scwg 一样，
: 因为原本的题目其实没有说明的很清楚，以下是我自己脑补的部份：
: 这个演算法想要做什麽？有一个猜测是，我觉得他的功能很像是搜寻时的预览功能，
: 比如说我们用 google search "harry potter spell" 这三个关键字，
: 我所找到的第一笔结果长这样：
: Harry Potter Spell List
: www.pojo.com/harrypotter/spelist.shtml - Cached
: Harry Potter Spell List. Here I think I got all the spells, charms,
: enchantments, curses, jinxes and all the other incantations. If there's
: any missing, e-mail us on the ...
: 另一个比较後面的结果长这样：
: HPL: Encyclopedia of Spells - The Harry Potter Lexicon
: www.hp-lexicon.org/magic/spells/spells.html - Cached
: Dec 27, 2000 –Descriptions of spells and various magical effects in the
: Harry Potter universe.
: 第一行是网页的 title, 第二行是网址，第三行开始则是内文的预览，
: 那要如何产生一个好的预览呢？
我觉得你的例子举得很好, I am really convinced by the application.
: 我们只能存每个字各自的 occurrence list ，
: 没办法产生 show_list 。
: 如果要把 occurrence list 合并成 show_list ，
: 这应该是没办法在 O(n) 的时间内做到，不然 merge sort 就会是 O(n) 了。
Yes, if you only have the occurance list, and want to
generate the show_list.
It will be equivlent to sort K "sorted" list.
Then, the complexity to generate the show_list will be O(N log K)..
我认为我们的讨论, 似乎已经超出原本面试题的范围了,
嗯, 也许应该写篇文章投到.. 数学传播之类的?
--
※ 发信站: 批踢踢实业坊(ptt.cc)
◆ From: 142.136.126.103