Re: [問題] Google Interview Question (4)
※ 引述《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
→
03/08 16:26, , 1F
03/08 16:26, 1F
→
03/08 16:27, , 2F
03/08 16:27, 2F
→
03/08 16:27, , 3F
03/08 16:27, 3F
→
03/08 16:28, , 4F
03/08 16:28, 4F
→
03/08 16:28, , 5F
03/08 16:28, 5F
→
03/08 16:44, , 6F
03/08 16:44, 6F
→
03/08 16:44, , 7F
03/08 16:44, 7F
→
03/08 16:44, , 8F
03/08 16:44, 8F
推
03/08 21:11, , 9F
03/08 21:11, 9F
→
03/08 21:11, , 10F
03/08 21:11, 10F
推
03/08 22:19, , 11F
03/08 22:19, 11F
討論串 (同標題文章)
本文引述了以下文章的的內容：
完整討論串 (本文為第 8 之 13 篇)：