Re: [問題] Google Interview Question (4)
看板Prob_Solve (計算數學 Problem Solving)作者Leon (Achilles)時間11年前 (2013/03/09 17:51)推噓0(0推 0噓 0→)留言0則, 0人參與討論串12/13 (看更多)
※ 引述《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
討論串 (同標題文章)
本文引述了以下文章的的內容:
完整討論串 (本文為第 12 之 13 篇):
Prob_Solve 近期熱門文章
PTT數位生活區 即時熱門文章