Re: [問題] Google Interview Question (4)

看板Prob_Solve (計算數學 Problem Solving)作者 (Achilles)時間11年前 (2013/03/09 17:51), 編輯推噓0(000)
留言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
文章代碼(AID): #1HEmOZ1y (Prob_Solve)
討論串 (同標題文章)
文章代碼(AID): #1HEmOZ1y (Prob_Solve)