濰坊IT培訓
美國上市IT培訓機構

0536-8222119

熱門課程

一道有趣的IT面試題

  • 時間:2016-11-30
  • 發布:濰坊達內
  • 來源:濰坊達內

現在很多大型IT企業在面試時都喜歡問一些智力相關的題目,雖然智力面試題在面試筆試中占的比例不大,但很多時候,面試環節中智力題往往會成為我們拿offer的最大攔路虎。因為有些面試官認為通過智力題可以考查你的思維能力、抽象問題的能力。

下面是一道很經典的智力型面試題,也是濰坊達內小編一朋友在BAT面試中親身見識過的一道題。各位來體驗一下,看看自己的大腦是不是好使。

題目

有一棟樓共100層,一個雞蛋從第N層及以上的樓層落下來會摔破, 在第N層以下的樓層落下不會摔破。給你2個雞蛋,設計方案找出N,并且保證在最壞情況下, 最小化雞蛋下落的次數。(假設每次摔落時,如果沒有摔碎,則不會給雞蛋帶來損耗)

在參考下面的解答之前,請你先仔細思考10分鐘??茨憬o出的方案最小下落次數是多少。如果題目總分10分,看看自己能得幾分。

解答1:得0分的答案

用二分法。

這基本可以說就是沒有通過大腦得出來的答案,而且還貌似很牛掰的樣子,并常常帶著一個lgn的復雜度。如果你接著問怎么個二分法,他就答不上來了。

這個答案不是我杜撰出來的,而是我拿這個題目問過身邊的一些人,其中有幾個人真的隨口就把二分法給說出來了。每當我聽到二分法時,當我沒問。

解答2:得5分的答案

如果我們動一下腦子仔細思考這個問題,我們會得到一個相對不錯的答案。參加BAT面試那位朋友就給出了下面的這種方案,并自認為是一種很完美的答案。但面試官給出的回答是:我還是不滿意。

據說,他這種思路的靈感來自于數學中的求極值問題。

已知兩個自然數的和為25,求這兩個數的平方和的最大、最小值。

解:設一個自然數為x 另一個自然數為25-x

x2+(25-x)2

=2x2-50x+625

=2(x2-25x+312.5)

=2[(x-12.5)2-156.25+312.5]

=2[(x-12.5)2+156.25]

所以可得:

當x取12.5時 有最小值2×156.25=312.5 (當x==y==12.5時取得極小值)

當x取25時 有最大值2×(12.52+156.5)=625

因此,很容易得到啟發(當然,這只是一種直覺,并沒有什么理論依據。)。100層樓,平均分成10分,每份剛好10層。

那么我們的做法如下:

將100層樓分成10分,每一份就是10層樓。首先,將雞蛋從第10層樓開始扔。那么結果有兩種可能:

情況1:如果碎了,說明臨界樓層在1到10之間,但現在只剩下一個雞蛋了,只能從層一直到第10層。

情況2:如果沒有碎,接下來從第20層扔雞蛋。

該方法的思路是,用一個雞蛋來試探,找到臨界樓層的大致范圍[1~10]、[11-20]….[91-100]。然后用另一個雞蛋在大致范圍內找出精確樓層。該方法的最壞次數是:18次。(自己去算,如果你算出來是17次,那就17次唄:))

解答3:得10分的答案

這是真正有理有據的解答。具體如下所述:

我們先假設最壞情況下,雞蛋下落次數為x,即我們為了找出N,一共用雞蛋做了x次的實驗。 那么,我們應該在哪層樓往下扔雞蛋呢?先讓我們假設是在第y層樓扔的雞蛋, 如果雞蛋在次扔就碎了,我們就只剩下一個雞蛋,要用它準確地找出N, 只能從層向上,一層一層的往上測試,直到它摔壞為止,答案就出來了。 由于個雞蛋在第y層就摔破了, 所以最壞的情況是第二個雞蛋要把第1到第y-1層的樓都測試一遍,最后得出結果, 噢,原來雞蛋在第y-1層才能摔破(或是在第y-1層仍沒摔破,答案就是第y層。) 這樣一來測試次數是1+(y-1)=x,即次測試要在第x層。OK, 那如果測試雞蛋沒摔破呢,那N肯定要比x大,要繼續往上找,需要在哪一層扔呢? 我們可以模仿前面的操作,如果雞蛋在第二次測試中摔破了, 那么第二個雞蛋的測試次數就只剩下x-2次了(雞蛋已經用了2次)。 這樣一來,第二次扔雞蛋的樓層和扔雞蛋的樓層之間就隔著x-2層。 我們再回過頭來看一看,扔雞蛋的樓層在第x層,第1層到第x層間共x層; 第1次扔雞蛋的樓層到第2次扔雞蛋的樓層間共有x-1層(包含第2次扔雞蛋的那一層), 同理繼續往下,我們可以得出,第2次扔雞蛋的樓層到第3次扔雞蛋的樓層間共有x-2層, ……最后把這些互不包含的區間數加起來,應該大于等于總共的樓層數量100,即

x + (x-1) + (x-2) + ... + 1 >= 100

(x+1)*x/2 >= 100

得出答案是14。

即我先用第1個雞蛋在以下序列表示的樓層數不斷地向上測試,直到它摔破。 再用第2個雞蛋從上一個沒摔破的序列數的下一層開始,向上測試, 即可保證在最壞情況下也只需要測試14次,就能用2個雞蛋找出從哪一層開始, 往下扔雞蛋,雞蛋就會摔破。

14, 27, 39, 50, 60, 69, 77, 84, 90, 95, 99, 100

比如,我第1個雞蛋是在第77層摔破的,那么我第2個雞蛋就從第70層開始,向上測試, 第二個雞蛋最多只需要測試7次(70,71,72,73,74,75,76),加上第1個雞蛋測試的 7次(14,27,39,50,60,69,77),最壞情況只需要測試14次即可得出答案。

這個問題還有一個泛化的版本,即d層樓,e個雞蛋,然后設計方案找出N, 使最壞情況下測試的次數最少。維基上給出了DP的解法,感興趣的話也可以看看。

更多資訊掃請描下方二維碼!

濰坊達內

上一篇:PHP初級開發者常見的5種疑問
下一篇:沒有下一篇了

馬上預約七天免費體驗課

姓名:

電話:

選擇城市和中心
江西省

貴州省

廣西省

海南省

達內教育

有位老師想和您聊一聊

再正经的男生谈恋爱也会污