谷歌演算法面試題

❶ 3道有意思的邏輯思維面試題

從小到大做了無數道智力題，工作之後接觸到程序員邏輯思維面試題，也曾經饒有興致的研究過。這些智力題，表面上是考智力水平，實際上是考察邏輯思維能力，而從更一般的意義而言，是在考察解決問題的能力。

一個人學習、研究、工作，其實無時無刻不是在訓練或使用解決問題的能力。解決問題的能力，在我看來，有很多方面，其中很重要的一方面就是邏輯思維能力。很多人對於邏輯思維的理解是存在誤區的，總以為邏輯思維只是理科生和工程師用的東西，與文科生甚至普通人沒有什麼關系。而實際上， 邏輯思維所涉及的范圍遠遠不止以數學為基礎的理工科，而是一種涵蓋各種學科、各種工作的通識能力 。

比如說，大學學文科專業的羅振宇，幾年前開了一個節目叫「羅輯思維」，強調用邏輯思維來理解世界，節目的內容涉及社會、歷史、經濟、人文、理工等各方面，俘獲了幾百萬乃至上千萬的粉絲。後來羅打造得到APP成為最知名的知識付費應用，就是以羅輯思維這個品牌欄目為底子做的。

最近看了一些大的科技公司（比如谷歌、微軟等）等招聘員工的面試題，很有意思，在這里與大家分享，並共同探討。

這是微軟非常知名的一道面試題，曾經難倒無數學霸才子：不是說好的考程序題或者智力題嗎，怎麼來了一個社會基礎建設問題？

為什麼是圓的？方的不行嗎？圓的究竟優勢在哪裡？

這就是在考察面試者的邏輯思維了。其實認真思考之後，不難得出「標准答案」：

如果面試者能夠這樣回答，說明他的邏輯思維不錯，或者至少生活經驗比較豐富。

那麼這是唯一的正確答案嗎？沒有這么簡單。我從一些優秀者的回答中，還發現了其它也很有道理的答案：

如果面試者能夠在所謂「標准答案」的基礎上，多給出幾個原因，那麼說明不僅邏輯思維很好，工程思維也非常棒，善於運用生活中的知識。這道題基本上給考官的印象應該是滿分了。

但是，關於這道題的討論並非到此為止。 下水道井蓋一定是圓的嗎？有沒有可能是方的或者其它形狀的？

傳說有一位面試者，在被問到該問題的時候，堅持說也可以用方的井蓋，並給出了合理的理由，最終成功說服了考官。下面是傳說的面試過程：

這位面試者不僅邏輯思維和工程經驗豐富，說服人的能力也非常強，讓考官覺得他是不可多得的人才，被推薦到更需要綜合技能的銷售部門工作。

其實，像這樣的邏輯思維面試題並沒有所謂的標准答案，考官的真實目的是 考察面試者的邏輯思維能力 ，更一般的講，是 解決問題的能力 。下水道蓋也可以是方的，只要你能給出合理的理由，自圓其說。

這是Google的一道面試題：

有一棟100層高的大樓，給你兩個完全相同的玻璃球。假設從某一層開始，丟下玻璃球會摔碎。那麼怎麼利用手中的兩個球，用什麼最優策略知道這個臨界的層是第幾層？

最笨的辦法誰都能想到：

可是這個辦法，最壞的情況下要試99次，平均意義上要試49次。而且只用了一個球，另一個球沒利用上。顯然不是最優的策略。

計算機專業的學生很容易想到更高級的辦法——二分法。具體是：

用這種方法，需要log100，也就是大約7次，能夠找到答案。

面試者如果能這樣回答，說明對計算機專業基本演算法是有了解的。但是，仔細想想，這個方法對嗎？

這個方法顯然是有毛病的。比如說我舉一個反例，第10層是臨界層的情況。按照二分法來執行，第一次試驗第50層將摔碎，第二次試驗第25層又將摔碎，此時兩個玻璃球都摔碎了，將沒有辦法繼續進行試驗！

注意最多有兩個球，也就是最多可以摔碎兩次。盡管上述二分法不可行，我們是否可以借鑒其思路，先大致確定一個小的范圍，然後逐個試驗呢？根據這樣的思路，可以提出下面的方法：

這種方法最壞的情況出現在臨界層為100時，將需要試驗10+10=20次；最好的情況出現在臨界層為2時，只需要試驗2次。而平均意義上大約需要試驗10次。怎麼樣，是不是有效的利用了兩個球呢？

按照吳軍老師的說法，這種解題方法其實體現了 一種典型的工程思維：粗調和精調 。其中第一個球用於粗調，確定一個大致的范圍；第二個球用於精調，在大致的范圍內確定精確的值。

其實，粗調和精調的工程思維在生活和工程中都很常見：

從這幾個例子，我們可以對粗調和精調的優點及注意事項進行簡單的總結：

了解了粗調和精調的概念之後，我們回過頭來，再次考察這道玻璃球題目。如果有3個玻璃球呢，是否有更好的方法？

當然是有的，標準的答案是採取三步試驗：

細心的讀者會發現，這三步試驗分別把答案的可能范圍縮小了4、4、5倍，最終確定了答案。

為什麼是這幾個數呢？而且，回過頭來想想，為什麼兩個小球的情況下，兩步試驗縮小的范圍分別是10、10呢？

這幾個數的選擇，當然絕非巧合。實際上，2個和3個玻璃球的情況下，縮小倍數分別是按照根號下100（也就是10）、3次根號下100（大約是5）來選擇的。 推廣到n個玻璃球的情況下，每步試驗的范圍縮小倍數應該是n次根號下100。 具體證明，我們在這里不做討論。

這絕不僅僅是一個小小的邏輯題， 考官想考察的是面試者的邏輯思維，包括工程思想、分析能力以及舉一反三的歸納概括能力 。知道標准答案不算什麼，吃透這道題並弄清背後的深刻原理，才是本事。

這道題相對前兩道來說要簡單一些。據說Google過去面試產品經理的時候會問到這個問題。什麼數據都不給，直接就這么問。

有些中國面試者可能不樂意了：你又不告訴我高爾夫球多大，也不告訴我這個房間的尺寸，什麼數據都沒有，我怎麼算啊？

但是這個題沒錯，考官考察的就是不給數據你怎麼計算！要不然小學生都能算出來了。

有些人一看沒給數據，可能就會胡猜：一間普通辦公室，又不是很大，高爾夫球直徑大概幾厘米，直觀感覺應該能裝幾千個或者幾萬個吧？

然而答案恰恰違反我們的直覺：至少能裝幾十萬個，甚至能裝上百萬個。

我們來算算：

一個房間竟然能裝這么多高爾夫球？是不是大的出乎我們的意料呢？

有人可能會懷疑，這道題如此簡單，小學生都能做，侮辱人智商嗎？然而這道題實際考察的，是我們解決問題的方式。Google對產品經理的要求是：

有的面試者在沒給數據的情況下可能會根據直覺亂猜，這是做事的大忌，因為很多東西其實是反直覺的，亂猜可能導致完全錯誤的結論，這是很危險的。最准確的做法是拿工具量一下會議室的長寬高以及高爾夫球的直徑，然後進行計算。不過，在沒有準確數據的情況下，合理的估算也是可行的，甚至也是必要的，估算能夠幫助我們大致知道答案的范圍，這在很多情況下已經足夠支持決策！

❷ 如何解讀微軟、谷歌和蘋果公司的智力面試問題

有棟建築物高100層。若從第N層或更高的樓層扔下來，雞蛋就會破掉。若從第N層以下的樓層扔下來則不會破掉。給你2個雞蛋，請找出N，並要求最差情況下扔雞蛋的次數為最少。

我們發現，無論怎麼扔雞蛋1（Egg 1），雞蛋2（Egg 2）都必須在「破掉那一層」和下一個不會破掉的最高樓層之間，逐層扔下樓（從最低的到最高的）。例如，若雞蛋1從5層和10層樓扔下沒破掉，但從15層扔下時破掉了，那麼，在最差情況下，雞蛋2必須嘗試從11、12、13和14層扔下樓。

具體做法

首先，讓我們試著從10層開始扔雞蛋，然後是20層，等等。

q 如果雞蛋1第一次扔下樓（10層）就破掉了，那麼，最多需要扔10次。

q 如果雞蛋1最後一次扔下樓（100層）才破掉，那麼，最多要扔19次（10、20、…、90、100層，然後是91到99層）。

這么做也挺不錯，但我們只考慮了絕對最差情況。我們應該進行「負載均衡」，讓這兩種情況下扔雞蛋的次數更均勻。

我們的目標是設計一種扔雞蛋的方法，使得扔雞蛋1時，不論是在第一次還是最後一次扔下樓才破掉，次數越穩定越好。

(1) 完美負載均衡的方法應該是，扔雞蛋1的次數加上扔雞蛋2的次數，不論什麼時候都一樣，不管雞蛋1是從哪層樓扔下時破掉的。
(2) 若有這種扔法，每次雞蛋1多扔一次，雞蛋2就可以少扔一次。
(3) 因此，每丟一次雞蛋1，就應該減少雞蛋2可能需要扔下樓的次數。例如，如果雞蛋1先從20層往下扔，然後從30層扔下樓，此時雞蛋2可能就要扔9次。若雞蛋1再扔一次，我們必須讓雞蛋2扔下樓的次數降為8次。也就是說，我們必須讓雞蛋1從39層扔下樓。
(4) 由此可知，雞蛋1必須從X層開始往下扔，然後再往上增加X-1層……直至到達100層。
(5) 求解方程式X + (X-1) + (X-2) + … + 1 = 100，得到X (X + 1) / 2 = 100 → X = 14。
我們先從14層開始，然後是27層，接著是39層，依此類推，最差情況下雞蛋要扔14次。

正如解決其他許多最大化/最小化的問題一樣，這類問題的關鍵在於「平衡最差情況」。

❸ 15個變態的谷歌面試問題的答案

十二題可是初三上學期的物理題啊,關於天平的!
答案是:把八個硬幣其中3個放左盤,在選另外3個放右盤,其餘兩個先不管,如果兩個盤一樣重,則重的硬幣在剩下的兩個硬幣中,在稱這兩個硬幣,ok.若其中一個盤較重,就把這個盤的三個硬幣,其中一個放左盤,另一個放右盤再測,如果相等,則重的是剩下的1個硬幣,如果天平不平衡,則重的硬幣在較重的盤上.
第五題則是關於數學幾何圖形,大概是初二初三接觸過的,要知道井蓋在路上,肯定是有東西在井蓋的邊緣托住他,井蓋才不會掉下去,而這個邊緣是很小的.那麼井蓋是圓的話,半徑相等,如果井蓋因某種原因而打側放的話由於直徑比邊緣要長,不至於令井蓋掉下去.如果井蓋是矩形的話,一打側他就會掉下去了,因為矩形由兩個直角三角形組成,而直角三角形的斜邊較長.如果照這樣說等邊三角形也應該可以啊,一些不規則圖形也可以,可能也有美觀這一因素在吧,又或者是井蓋作者先想到圓井蓋,後來全世界都圓井蓋了,就沒人在意去計較為什麼不用等邊三角形井蓋了...由於所學知識有限,當時我問老師為什麼不能用等邊三角形,老師沒答我.不能給你證明,抱歉.
第七題,首先思考一下,每一秒分針時針都在轉動,那麼在重合的時候的下一秒,時針分針會不會再重合一次?想深一層,我覺得應從圓的度數方面考慮,通過計算得知,分針每走一小格(一分鍾),走了6度,而時針走了0.5度.那麼,假如現在是十二點,時針分針都指在了"12"上,這時重合了一次,但每走一秒,分針都有微妙的轉動,而時針也是,那麼一秒分針轉動了6/60=0.1度,時針轉動了0.5/60=0.008333度,即是說,在重合時的下一秒,分針就已經超越了時針,所以一小時只重合一次!(個人認為,本人僅是初三學生,這可能不是正確答案).我覺得,一天24小時,自然是24次.
第十一題屬於推理題目,我不知道(呵呵),不過在網上有類似這道題的:海盜分金幣,有五個海盜,一號首先開始分金幣,如果他的分配方法得不到半數的同意就處死並讓下一位去分,這題已有詳細答案(很久前就看過了),答案是:逆向思維。
假設每一個海盜都是絕頂聰明而理性，他們都能夠進行嚴密的邏輯推理，並能很理智的判斷自身的得失，即能夠在保住性命的前提下得到最多的金幣。同時還假設每一輪表決後的結果都能順利得到執行，那麼抽到1號的海盜應該提出怎樣的分配方案才能使自己既不被扔進海里，又可以得到更多的金幣呢？
此題公認的標准答案是：1號海盜分給3號1枚金幣，4號或5號2枚金幣，自己則獨得97枚金幣，即分配方案為（97，0，1，2，0）或（97，0，1，0，2）。現來看如下各人的理性分析：
首先從5號海盜開始，因為他是最安全的，沒有被扔下大海的風險，因此他的策略也最為簡單，即最好前面的人全都死光光，那麼他就可以獨得這100枚金幣了。
接下來看4號，他的生存機會完全取決於前面還有人存活著，因為如果1號到3號的海盜全都餵了鯊魚，那麼在只剩4號與5號的情況下，不管4號提出怎樣的分配方案，5號一定都會投反對票來讓4號去喂鯊魚，以獨吞全部的金幣。哪怕4號為了保命而討好5號，提出（0，100）這樣的方案讓5號獨占金幣，但是5號還有可能覺得留著4號有危險，而投票反對以讓其喂鯊魚。因此理性的4號是不應該冒這樣的風險，把存活的希望寄託在5號的隨機選擇上的，他惟有支持3號才能絕對保證自身的性命。
再來看3號，他經過上述的邏輯推理之後，就會提出（100，0，0）這樣的分配方案，因為他知道4號哪怕一無所獲，也還是會無條件的支持他而投贊成票的，那麼再加上自己的1票就可以使他穩獲這100金幣了。
但是，2號也經過推理得知了3號的分配方案，那麼他就會提出（98，0，1，1）的方案。因為這個方案相對於3號的分配方案，4號和5號至少可以獲得1枚金幣，理性的4號和5號自然會覺得此方案對他們來說更有利而支持2號，不希望2號出局而由3號來進行分配。這樣，2號就可以屁顛屁顛的拿走98枚金幣了。
不幸的是，1號海盜更不是省油的燈，經過一番推理之後也洞悉了2號的分配方案。他將採取的策略是放棄2號，而給3號1枚金幣，同時給4號或5號2枚金幣，即提出（97，0，1，2，0）或（97，0，1，0，2）的分配方案。由於1號的分配方案對於3號與4號或5號來說，相比2號的方案可以獲得更多的利益，那麼他們將會投票支持1號，再加上1號自身的1票，97枚金幣就可輕松落入1號的腰包了 .但是google的這道題無明確條件,只說如果得不到同意就死,沒其他的了,如果船員不管三七二十一全讓你死,那你怎麼辦?或許這題不應用邏輯分析,而是從社會現實角度,例如巴結好熟人之類的呵呵~~
第十題好像在某本書上看過,不過沒有寫答案,我是這樣想的,既然要讓他不知道號碼,就不能夠在紙上寫,那麼就只能夠用手機確認了:讓鮑伯撥打我的手機號碼.
第十五題,我想出的答案有很多,這種腦筋急轉彎式的題在大家眼中有無數答案,但出題人只看他手中的正確答案,所以我把我最雷的一個給你參考吧:如果只有硬幣這么小,從平面看攪拌器一般成接近四邊形五邊形的形狀,攪拌刀片轉動時是圓,嗎么就直接站在攪拌刀片切不到你的死角位置不就ok了?
第三題,生物學解釋,生男生女比例1比1,因為概率問題只是大概估算,並無准確答案,考方只想看你的解題思路罷了,我是這樣解的:既然是一比1,那麼就是要麼先生男,要麼先生女,由於是大概估算,那麼看作每生兩次就有一男一女(現實是不可能),即是:先生男的話就不再生,如果生女的話就會在生一個男,把他認作只有這兩種情況,且概率都是一比一,就是說兩男一女,所以比例就是二比一.
第八題,我不會,不過網上有網友的見解:對於一個軟體工程師來說，是要盡量避免在軟體中「死牛肉」出現。它不但對軟體本身沒有好處，還會給整個軟體帶來破壞。死牛肉不但不能吃還會引來許多倉蠅之類的害蟲。
其他題大多屬於主觀題,沒絕對答案,出題人只想看你的思路.不過我已經把能說的都給你說了,只看答案沒有用關鍵是分析,希望我用了1小時的長篇大論對你有幫助

參考資料： 網路大神,老師的諄諄教導

❹ android 面試，演算法題。

final int size = data.length;
for(int i = 0; i< size; i++){
if(data[i] == 0xffffffff)
data[i] = 0x80ffffff;
}

不知道你是不是這個意思。