作者Leon (Achilles)
站內Prob_Solve
標題Re: [問題] Google Interview Question (4)
時間Fri Mar 8 15:36:22 2013
※ 引述《Leon (Achilles)》之銘言：
: 嗯, 剛剛想了一下.
: 這個題目, 是 KMP 的變形.
:
: 難的地方在於, 你怎麼想到正確的方向
: (聽起來有點廢話, 哈哈..)
:
: 這裡我採用之前的定義.
:
: For a sentance, we are given the occurance index.
: Take above example, say, only 3 words {a, b, c}.
: The sentance is [b b a c b a].
:
: The the occurance index will be
: a = {3, 6}.
: b = {1, 2, 5}.
: c = {4 }.
:
:
: 在開始之前, 我們先看幾個非常簡單的作法.
:
: 1. Naive: Arbitary choose 2 position from [1, N],
: then check the condition.
:
: 2. Choose one position as the left boundary, then,
: use the max-min of the rest set the decide the right boundary.
:
: For example, if I choose 2 as my left boundary,
: then I need to choose the right boundary by the max of
: d(2,3) and d(2,4) which cover set {a} and set {c}
:
: The result window is [2, 4].
:
: And the complexity should be O(N* K).
:
: 接下來, 就是有趣的地方了.
:
: 3. Follow the previous algorithm, inspired by KMP.
: When we start from 3, actually we don't need to compare all K groups.
:
: Because from previous step, we know [2] covers {b} for sure.
: And [3,4] covers {a,c} for sure.
:
: In this case, we only need to check the condition for set {b} !
: which is d(3,5).
:
: Then the computational complexity is O(N).
: I'll leave the detail for you.
:
:
:
: --
: ※ 發信站: 批踢踢實業坊(ptt.cc)
: ◆ From: 204.140.133.209
: 推 ledia:I'll leave the detail for you XD 03/08 10:19
: → scwg:怎麼用 o(log K) 決定只需要檢查 b 呢 03/08 13:49
Un, I didn't say O(log K).
See below discussion.
: 推 stimim:我不是很確定你的意思，不過 document 可能會有其他的字， 03/08 14:41
: → stimim:所以號碼不一定是連續的 03/08 14:41
: → stimim:因此下一個開始位置不一定是 3 03/08 14:42
My bad, should say more detail.
In approach 2, it iterates with different left boundary.
For example, in the begining, the left boundary is [1].
Then we need to decide the right boundary.
The straight-forward approach will be:
1. Check [1] belongs to which occurance list.
2. Then, find the max - min of the other rest occurance list.
After finishing that, we move to next left boundary position [2],
play a linear scan.
Totally we scan N left positions.
The inner loop takes O(K), the outer loop takes O(N).
So this approach takes O(N* K).
In approach 3, based on KMP concept,
the outer loop still do a sequential scan, but I argue the inner loop
doesn't necessarily need O(K) - we can use previous step info.
Hope it helps.
We should start
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 76.170.73.1
→ scwg:Since you claimed that the complexity is O(N), the inner 03/08 16:26
→ scwg:loop must be amortized O(1), that's why I was wondering 03/08 16:27
→ scwg:what kind of data structure are you maintaining through 03/08 16:27
→ scwg:out the loop to keep the lookup o(log K). (Small-o, not 03/08 16:28
→ scwg:big-O.) 03/08 16:28
→ Leon:it's not me to claim O(lg K).. please check my article 03/08 16:44
→ Leon:and, my article do explain how to achieve O(1) in inner 03/08 16:44
→ Leon:loop based on KMP concept.. 03/08 16:44
推 ledia:o(lg K) is different than O(lg K) 03/08 21:11
→ ledia:you did claim o(lg K) 03/08 21:11