標題

Re: [討論] Google面試問題

(25/31篇)看板Soft_Job軟工板作者cyclone350 (老子我最神)推文4則 (3推 0噓 1→)
打在記事本後再貼上的，怕斷線

================================================

我解出來了，若有錯誤請多指教...

不過基本上我認為我得答案是對的 XD


首先，假設有一層樓，"最低的 worst case"  就是 1
若是有兩層樓，"最低的 worst case" 就是 2

我們定義一個 f(x) 代表從 x 層丟下去"最低的 worst case"

我們已知

f(1) = 1
f(2) = 2

而 f(3) 等於多少呢?

我們已知計算"最低的 worst case"的演算法絕對不可能從一層一層丟下去

否則 f(n) 就會是 n。

所以當從中間丟第一顆蛋下去，則接下來會被切成兩個情況

破掉 = > f(1)
沒破掉 => 1

所以 f(3) = min( f(1), 1 ) + 1 = 2

接下來計算 f(4)

若從中間丟下去，可以從第二層丟或是第三層丟，所以會被分成以下情況

若從第二層丟 =>
    沒破 => f(2)
        破     => 1

所以如果我們從第二層丟，所得到的"最低 worst case" = Max(f(2), 1) + 1 = 3

若從第三層丟 =>
    沒破 => f(1)
        破     => 2

所以"最低 worst case" = Max(f(1), 2) + 1 = 3

所以 f(4) = min( Max(1,f(2)), Max(f(1),2) ) + 1
               = 2 + 1 = 3


根據以上情況可以看出幾個公式

1. f(n) >= f(n-1)

2. f(n) = min( x=1..(n-1)  Max(f(x), (n-x-1)) ) + 1

3. f(n) <= n

用公式三可以判端出

Max( f(1), 2 ) = 2
Max( 1, f(2) ) = 不確定

所以 min( Max(1,f(2)), Max(f(1),2) ) = min( Max(1,f(2)), 2 )

我們已知 f(2) <= 2

所以 f(3) 可以簡化成 min(Max(1,f(2)))

另外可以對公式二進行簡化成公式四

4. f(n) = min( x=1..((n-1)/2)  Max( x, f(n-x-1) )  ) + 1

帶入此公式可以算出 { 若 x = f(n-x-1) ，則定義 Max(x, f(n-x-1)) = x ||
f(n-x-1) }

f(3) = min(1) + 1 = 2
f(4) = min(f(2)) + 1 = 3
f(5) = min(f(3), 2) + 1 = 3
f(6) = min(f(4), f(3) || 2) + 1 = 3
f(7) = min(f(5), f(4), 3) + 1 = 4
f(8) = min(f(6), f(5), f(4) || 3) + 1 = 4
f(9) = min(f(7), f(6), f(5) || 3, 4) + 1 = 4
f(10) = min(f(8), f(7), f(6), 4) + 1 = 4

由以上可判斷出每一個 f(n) 有一個值  λ ，若 x < λ ，則 min(x, f(n-x-1)) =
f(n-x-1)
若 x >= λ，則min(x, f(n-x-1)) = x

所以可以推出公式五

5. f(n) = min( f(n-2), f(n-3), ... ,  f(n-λ), λ, (λ+1), (λ+2), ... ) + 1

由公式五可以看出來，min( f(n-2), f(n-3), ... ,  f(n-λ), λ, (λ+1), (λ+2),
... ) =  min(λ, f(n-λ))

藉由之前λ定義可以看出

f(n-λ) > λ-1

因為f(n-λ)是正整數，所以可以推論出 f(n-λ) >= λ


所以 min( f(n-2), f(n-3), ... ,  f(n-λ), λ, (λ+1), (λ+2), ... ) = λ

因此推導出公式六

6. f(n) = λ+1

接下來，因為 f(n) = λ+1，所以 min(f(n), λ+1) = λ+1

有公式五跟公式六可以推導出公式七

7. f(n+f(n)) = f(n) + 1

所以可以推出

f(1+f(1))  = f(2)   = f(1) + 1 = 2
f(2 +f(2)) = f(4)   = f(2) + 1 = 3
f(4 +f(4)) = f(7)   = f(4) + 1 = 4
f(7 +f(7)) = f(11)   = f(7) + 1 = 5
f(11 +f(11)) = f(16) = f(11) + 1 = 6

可看出這是一個遞增公式

f(1) ~ f(20) 分別為
1, 2, 2, 3, 3, 3, 4, 4, 4, 4, 5, 5, 5, 5, 5, 6, 6, 6, 6, 6, 6

雖然知道這是怎麼出來的，但是我公式寫不出來，不知道要用啥符號 @@


所以可以導出， 若"worst case" 若為 t

則樓層最高為 (1+t)t/2 (梯形公式) ，最低為 t(t-1)/2 + 1


所以若100樓所能導出的 "最低 worst case" 為 14

因為 100 介於 91 ~ 105 之間


至於要怎麼丟，寫個 recusive 應該就能跑出來了


感覺繞了一大圈遠路才算出來 @@--
※ 發信站: 批踢踢實業坊(pttweb.tw), 來自: 61.218.64.133
※ 文章網址: https://pttweb.tw/Soft_Job/M.1397811257.A.34C
※ 編輯: cyclone350 (123.193.201.124), 04/18/2014 21:30:43
※ 編輯: cyclone350 (123.193.201.124), 04/18/2014 21:42:15
※ 編輯: cyclone350 (123.193.201.124), 04/18/2014 22:03:46