作者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
1F：→ scwg:Since you claimed that the complexity is O(N), the inner 03/08 16:26
2F：→ scwg:loop must be amortized O(1), that's why I was wondering 03/08 16:27
3F：→ scwg:what kind of data structure are you maintaining through 03/08 16:27
4F：→ scwg:out the loop to keep the lookup o(log K). (Small-o, not 03/08 16:28
5F：→ scwg:big-O.) 03/08 16:28
6F：→ Leon:it's not me to claim O(lg K).. please check my article 03/08 16:44
7F：→ Leon:and, my article do explain how to achieve O(1) in inner 03/08 16:44
8F：→ Leon:loop based on KMP concept.. 03/08 16:44
9F：推 ledia:o(lg K) is different than O(lg K) 03/08 21:11
10F：→ ledia:you did claim o(lg K) 03/08 21:11