作者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