PTT數位生活區 / Prob_Solve (計算數學 Problem Solving)

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

看板Prob_Solve (計算數學 Problem Solving)作者stimim (qqaa)時間11年前 (2013/03/09 17:19)推噓0(0推 0噓 0→)

留言0則, 0人參與討論串11/13 (看更多)

推 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, 第二行是網址，第三行開始則是內文的預覽，那要如何產生一個好的預覽呢？我想這一題的目標：「找出一個最小的 window 來包含所有的關鍵字」可能就是一種方法如果我們每次都是用原本的文件來產生這個 window 的話，（也就是 occurrence lists 要自己產生）那這題至少是 O(|document size| * O(check word)) O(check word) 指的是檢查每個字到底是哪一個關鍵字所要花的時間 document size 以 word 為單位突破這個限制的一種方法就是對文件做一些預處理，(所做的事和 indexing 應該差不多) 我們先對文件中的字產生他們的 occurrence list ，這樣的花費也是 O(|document size| * O(check word)) (假設我們有辦法儲存這些資訊，以供日後使用) 然後，未來有人來搜尋時，我們可以根據事先做好的 occurrence list 來求解在這種情況下，至少不用再花時間做 check word 。以長遠的角度來看，或許可以省下不少時間。另一方面，也因為在有 occurrence list 的狀況下，我們已經可以做到 O(|document size|) 了，所以我會想要試試看能不能做到 O(n) (n = key words 出現的總次數)。而 Leon 在上一篇中所提到的 show_list 我們其實是沒有的，因為我們在事前不知道使用者會搜尋哪一些字，我們只能存每個字各自的 occurrence list ，沒辦法產生 show_list 。如果要把 occurrence list 合並成 show_list ，這應該是沒辦法在 O(n) 的時間內做到，不然 merge sort 就會是 O(n) 了。 -- ※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 36.226.38.104