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

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

看板Prob_Solve (計算數學 Problem Solving)作者Leon (Achilles)時間11年前 (2013/03/08 15:36)推噓2(2推 0噓 9→)

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

※ 引述《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