Re: [問題] Google Interview Question (4)
看板Prob_Solve (計算數學 Problem Solving)作者Leon (Achilles)時間11年前 (2013/03/06 02:08)推噓1(1推 0噓 4→)留言5則, 2人參與討論串4/13 (看更多)
※ 引述《RockLee (Now of all times)》之銘言：
: ※ 引述《Leon (Achilles)》之銘言：
: : Sorry, I can't understand your writing.
: : Also, the link seems to be wrong...
: : Can you describe it, step by step.
: : For example, there are only 3 words, (a,b,c)
: : how are you going to find the window, for the document
: : [b b a c b b b b c b b a] ?
: 雖然 pseudo code 可能比較短,
: 但由於 interview Google 時必需寫 actual code,
: 所以我想還是直接用實際的 Java code 表達我的想法.
: (我假設 window 長度指的是包含的字數, 與每個字的長度無關)
: 以 Leon 大給的例子:
: document: b b a c b b b b c b b a
: index: 0 1 2 3 4 5 6 7 8 9 10 11
: occurence a: 2, 11
: occurence b: 0, 1, 4, 5, 6, 7, 9, 10
: occurence c: 3, 8
: 執行過程及結果會是:
: windowBegin = 0; windowEnd = 3
: windowBegin = 1; windowEnd = 3
: windowBegin = 2; windowEnd = 4
: windowBegin = 3; windowEnd = 11
: windowBegin = 4; windowEnd = 11
: windowBegin = 5; windowEnd = 11
: windowBegin = 6; windowEnd = 11
: windowBegin = 7; windowEnd = 11
: windowBegin = 8; windowEnd = 11
: bestBegin = 1
: bestEnd = 3
: -----------------------------------------------
我的ㄧ些習慣: (大家互相參考一下)
先確定演算法是對的, 作出 complexity,
再用 Pseudo code 寫好
確定結構 ( main program, and possible data structure)
再寫 Code.
我不用 Java, 所以我只是很快的掃過你的 code
再你的 Program 中,
你決定了 window start 之後用 occurance index 去找 window ending ?
依照我的理解, starting point has N possibility,
and you have K different words.
Thus, the computational complexity should be O(N* K),
Not the O(N* lg(K)) you claim before?
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 128.125.20.198
推
03/06 04:41, , 1F
03/06 04:41, 1F
→
03/06 04:42, , 2F
03/06 04:42, 2F
→
03/06 04:43, , 3F
03/06 04:43, 3F
→
03/06 04:44, , 4F
03/06 04:44, 4F
→
03/07 13:38, , 5F
03/07 13:38, 5F
討論串 (同標題文章)
Prob_Solve 近期熱門文章
PTT數位生活區 即時熱門文章
