每個分析師都會遇到的7個面試謎題
轉載聲明
本文為燈塔大數據原創內容，歡迎個人轉載至朋友圈，其他機構轉載請在文章開頭標註：
「轉自：燈塔大數據；微信：DTbigdata」
繼上周發布的譯文《每個分析師都會遇到的7個面試謎題》後，我們又精選了3道有意思的數據謎題，相信聰明的你會喜歡~
現在，想在分析行業里分得一杯羹是非常不容易的事情。約三成的分析公司（特別是頂尖公司）會要求應聘者解決謎題，並藉此評估他們的能力。從中他們能夠觀察出你是否邏輯清晰，思維活躍，且精通數字處理。 如果你能通過獨特視角看待並解決商業難題，那麼你就能從眾多應聘者中脫穎而出。但是這種解決問題的能力不是一朝一夕得來的，需要有計劃地訓練和長期的堅持。 對我來說，解決謎題就像是腦力訓練。我每天都會做，長期下來我覺得效果顯著。為了幫助你也達到這種效果，我和你們分享一些我遇到過的最複雜最費解的問題。這些問題在一些大公司的面試中也出現過，如高盛投資、亞馬遜、谷歌和摩根大通公司等。 解題之前不要偷瞄答案哦！
#8 機智的孩子
一所學校里有19個聰明絕頂的孩子，他們分別是：A、B、C、D、E、F、G、H、I和Sam。早上8:58他們衝進教室大聲談笑，兩分鐘後休息時間就結束了，表情嚴肅的拉比特老師走進了教室。
拉比特老師看到ABCD四個學生臉上有泥。拉比特老師認為他的觀點一定是對的，而且墨守成規，不懂變通。他開始大肆批評起這些孩子。
「都給我閉嘴！」他大聲喊。「都不許說話。你們幾個臉上有泥的，全部給我滾出教室」。這些孩子面面相覷。每個孩子都能看到別人臉上是否有泥，但不能確定自己臉上有沒有。因此，沒有人主動走出教室。
「沒聽到我說的話嗎，臉上有泥的，全部給我滾出教室！」
依然沒有人動。說了5次之後，9點到了，下課鈴響了。拉比特老師生氣的喊道：「你們當中至少還有一個人臉上是有泥的！」
這些孩子咧嘴笑了，因為他們知道這場折磨就要結束了。不久，老師又喊了幾遍「臉上有泥的，全部給我滾出教室！」之後，A、B、C、D走出了教室。
請解釋為什麼A、B、C、D知道是他們的臉上有泥？為什麼這些孩子會笑？每個人都知道他們其中至少有一個人臉上是有泥的。 如果一個孩子在拉比特老師9點鐘怒吼之前還不知道自己臉上是否有泥，但那之後他立刻意識到了。請你給出邏輯解釋。
答案：
拉比特老師第一次怒吼的時候，這些孩子馬上就意識到他們當中至少有一個人臉上有泥。所以，如果只有一個孩子臉上有泥，那麼這個孩子就應該馬上意識到是他自己臉上有泥，然後走出教室。
因為在老師一聲怒吼之後並沒有人離開教室，他們意識到至少有兩個人臉上有泥。如果只有兩個孩子臉上有泥，這兩個人就應該知道（他們會看到其他孩子中只有一個人臉上有泥，然後就能意識到另一個就是自己），然後他們倆就會走出教室。
在老師第二次怒吼之後，依然沒有人走出教室，這就意味著至少有三個孩子臉上有泥，以此類推，到老師第四次怒吼的時候，A、B、C、D就知道是自己臉上有泥並走出教室了。
這個解釋還存在一些疑問。每個人都能看到其他孩子中至少有三個臉上有泥，為什麼他們一定要等到拉比特老師怒吼好幾次才做出反應呢？為什麼這些孩子一定要等到老師怒吼四次呢？
在多主體推理問題中，常識的重要概念就顯現了。每個人都知道至少有三個孩子臉上有泥，但是他們並不清楚其他的孩子是否也知道這一點，所以他們不能一起行動。他們也不知道是否每個人都知道其他人也知道至少有三個孩子臉上有泥（我已暈）。這就是我們需要分析的地方。這需要你有足夠的想像力，快給自己加點想像力，我們再接著看。
A知道BCD臉上有泥，A不知道B是否知道3個人臉上有泥，A知道B知道2個人臉上有泥，但是A不能指望別人根據這一信息做出行動，因為A不知道B是否知道C知道2個人臉上有泥。如果你覺得這是無意義的瞎推理，讓問題變得更複雜，請你考慮一下情況：
A想像出一個空間，其中他自己臉上是沒有泥的，我們稱為空間A。在空間A中，A想像B的空間中A和B臉上都是沒有泥的。我們稱其為空間AB。
A想像出空間A中B想像C想像D認為沒有人臉上有泥。（稱之為空間ABCD），那麼當拉比特老師最開始怒吼的時候，沒有人走出教室可能是因為空間ABCD，其中沒有人臉上有泥所以沒有人需要出去。
所以在拉比特老師怒吼之後，這種狀態就改變了。空間ABCD不復存在，即A不能認為空間A中B想像C想像D認為沒有人臉上有泥。因此現在在空間ABC中，D知道他自己臉上有泥。在空間ABD中，C知道他臉上也有泥。以此類推。
#9囚犯與帽子2
有7個罪犯圍坐一圈。典獄官手裡有7種不同顏色的帽子（每種顏色帽子數量無限）。典獄官在每個罪犯頭上都戴上一頂帽子——他可以將任意顏色帽子戴在任一罪犯頭上。每個罪犯都能看到除了自己之外所有人的帽子顏色。典獄官命令所有人立刻說出自己頭上帽子的顏色。如果有人能正確說出自己頭上帽子的顏色，他就能獲得自由。否則，就會被打入地牢，永不見天日。請你設計一種方案，使得所有罪犯都能被釋放。
答案：
將7種顏色分別編號為0-6。然後我們再做模運算（modulo 7）。
將7個罪犯編號從0-6。罪犯P的編號為N，P猜測分給其他所有罪犯帽子顏色總數為M（modulo 7），那麼，他會按照以下假設推算出自己頭上的帽子顏色 (= (M - sum(其他6個罪犯帽子顏色))%7)。
總有一個罪犯能正確猜出總數來（因為總數介於0-6之間），那麼這個罪犯就能正確猜出他自己頭上帽子的顏色。
如果有解決方案的話，那麼至多1個罪犯會猜對。因為總共有7^7種假設情況。
每一個罪犯的反應都是另外6個罪犯帽子顏色的作用結果。如果你讓這6個人帽子顏色不變，僅僅變化這個人帽子的顏色，你會發現，他猜中自己帽子顏色的概率就是1/7（共有7^6種可能情況），那麼從所有情況中來看，能夠猜對自己帽子顏色的罪犯總數就是7*(7^6)=7^7.
如果每種情況下必須至少有1個罪犯猜測正確，這就意味著每種情況下至多也只有1人猜對。
猜對自己帽子顏色就等於猜出了所有罪犯帽子顏色的總數（modulo 7）。（其他6個人帽子顏色已知）。所以猜一個人帽子顏色就等於猜所有顏色的總數。我們怎樣才能保證至少有一人猜出總數呢?只需要保證每個人猜的總數不相等即可。
#10 種族滅絕
有一天，一個外星人來到地球上。每天，外星人都要做以下四件事其中一件，已知做每件事的概率相等：
(i)自殺
(ii)啥都不做閑著
(iii)把自己撕開變成兩個外星人（他自己就死了）
(iv)把自己撕開變成三個外星人（他自己就死了）
最後地球上的外星人滅絕的概率是多少？
答案：
就是√2 – 1
設外星人徹底滅絕的概率是X
對於n個外星人來說，滅絕的概率就是nX， 因為我們把每個外星人當作獨立個體。現在，如果我們把第二天的外形人數和第一天對比，就能得到：
x = (1 /4) * 1 + (1 /4) * x + (1 /4) * x2 + (1 /4) * x3
x3 + x2 ? 3x + 1 = 0
(x ? 1)(x 2 + 2x ? 1) = 0
得到, x = 1, ?1 ? √ 2, or ? 1 + √ 2
令X不能等於1，最後所有的外星人都死亡。那麼，地球上的外星人數平均乘以0+1+2+3 4 = 1.5每分鐘，那麼原則上外星人就不會滅絕（更加詳細的推理如下）因為X不能為負，因此唯一解就是X = √ 2 ? 1.
X不等於1，因此最大為√ 2?1
nX為一隻細菌在最多n分鐘內滅絕的概率。那麼我們就得到以下關係：
xn + 1 = 1/4 (1 + xn + x2n + x2n)
令對於所有n來說，xn ≤ √ 2 – 1，我們可以用推理得證
顯然x1 = 1 /4 ≤ √ 2 – 1
假設對部分k來說 xk ≤ √ 2 ? 1
xk+1 ≤ 1/4 (1 + xk + x2k + x3k )
≤ 1/4 ( 1 + (√ 2 ? 1) + (√ 2 ? 1)2 + (√ 2 ? 1)3 )
= √ 2 ? 1
這就證明了對所有n來說xn ≤ √ 2 – 1。我們注意到n越大，nX越接近X。運用前面的計數，得到：
x = lim (n ∞) xn ≤ √ 2 ? 1, X不等於1.
英文原文
#8 These kids deserve medals
There are 10 incredibly smart boys at school: A, B, C, D, E, F, G, H, I and Sam. They run into class laughing at 8:58 am, just two minutes before the playtime ends and are stopped by a stern looking teacher: Mr Rabbit.
Mr Rabbit sees that A, B, C and D have mud on their faces. He, being a teacher who thinks that his viewpoint is always correct and acts only to enforce rules rather than thinking about the world that should be, lashes out at the poor kids.
「Silence!」, he shouts. 「Nobody will talk. All of you who have mud on your faces, get out of the class!」. The kids look at each other. Each kid could see whether the other kids had mud on their faces, but could not see his own face. Nobody goes out of the class.
「I said, all of you who have mud on your faces, get out of the class!」
Still nobody leaves. After trying 5 more times, the bell rings at 9 and Mr Rabbit exasperatedly yells: 「I can clearly see that at least one of you kids has mud on his face!」.
The kids grin, knowing that their ordeal will be over soon. Sure enough, after a few more times bawling of 「All of you who have mud on your faces, get out of the class!」, A, B, C and D walk out of the class.
Explain how A, B, C and D knew that they had mud on their faces. What made the kids grin? Everybody knew that there was at least one kid with mud on his face. Support with a logical statement that a kid did not know before Mr Rabbit』s exasperated yell at 9, but that the kid knew right after it.
Answer:
After Mr Rabbit』s first shout, they understood that at least one boy has mud on his face. So, if it was exactly one boy, then the boy would know that he had mud on his face and go out after one shouting.
Since nobody went out after one shouting, they understood that at least two boys have mud on their faces. If it were exactly two boys, those boys would know (they would see only one other』s muddy face and they』d understand their face is muddy too) and go out after the next shouting.
Since nobody went out after the second shouting, it means there are atleast three muddy faces And so on, after the fourth shouting, A, B, C and D would go out of the class.
This explanation does leave some questions open. Everybody knew at least three others had mud on their faces, why did they have to wait for Mr. Rabbit』s shout at the first place? Why did they have to go through the all four shoutings after that as well?
In multi-agent reasoning, an important concept arises of common knowledge. Everybody knows that there are at least three muddy faces but they cannot act together on that information without knowing that everybody else knows that too. And that everybody knows that everybody knows that and so on. This is what we』ll be analyzing. It requires some imagination, so be prepared.
A knows that B, C and D have mud on their faces. A does not know if B knows that three people have mud on their faces. A knows that B knows that two people have mud on their faces. But A can』t expect people to act on that information because A does not know if B knows that C knows that there are two people with mud on their faces. If you think this is all uselessly complicated, consider this:
A can imagine a world in which he does not have mud on his face. (Call this world A) In A』s world, A can imagine B having a world where both A and B do not have mud on their faces. (Call this world AB)
A can imagine a world where B imagines that C imagines that D imagines that nobody has mud on their faces. (Call this world ABCD). So when Mr Rabbit shouted initially, it could have been that nobody was going out because a world ABCD was possible in which nobody should be going out anyway.
So here』s a statement that changes after Mr. Rabbit』s yell. World ABCD is not possible i.e. A cannot imagine a world where B imagines that C imagines that D imagines that nobody has mud on their faces. So now in world ABC, D knows he has mud on his face. And in world ABD, C knows he has mud on his face and so on.
#9 More prisoners and more hats
There are 7 prisoners sitting in a circle. The warden has caps of 7 different colours (an infinite supply of each colour). The warden places a cap on each prisoner』s head – he can chose to place any cap on any other』s head. Each prisoner can see all caps but her/his own. The warden orders everybody to shout out the colour of their respective caps simultaneously. If any one is able to guess her/his colour correctly, he sets them free. Otherwise, he send them in a dungeon to rot and die. Is it possible to devise a scheme to guarantee that nobody dies?
Answer:
Assign to each of the 7 colours a unique number from 0-6. Henceforth, we will only be doing modular arithmetic (modulo 7).
Assign to each of the 7 prisoners a unique number from 0-6. If the number assigned to prisoner P is N, then P always guesses that the sum of the colours assigned to all prisoners is M (modulo 7). Thus, he calculates his own colour under this assumption (= (M - sum(colours of the 6 prisoners he can see))%7).
There will always be a prisoner who guesses the correct sum (as the sum lies in 0-6), and this prisoner therefore correctly guesses his own colour.
If there is a solution, then exactly one prisoner is correct (no more). This is because there are 7^7 scenarios.
Each prisoner』s response is a function of the colours of the other 6, so if you fix their colours and vary his colour, you can see that he will be correct in exactly one-seventh of the cases (=7^6). The sum (across all scenarios) of the number of prisoners who are correct is 7*(7^6)=7^7.
If each scenario is to have at least one person right, this implies that each scenario cannot have more than one person who is right.
Being right about one』s colour is equivalent to being right about the sum of colours of all prisoners (modulo 7). (The colours of the other 6 are known.) So guessing one』s colour is the same as guessing the sum. How do we make sure that at least one person guesses the correct sum? By making sure that everybody guesses a different sum.
#10 All men must die
One day, an alien comes to Earth. Every day, each alien does one of four things, each with equal probability to:
(i) Kill himself
(ii) Do nothing
(iii) Split himself into two aliens (while killing himself)
(iv) split himself into three aliens (while killing himself)
What is the probability that the alien species eventually dies out entirely?
Answer:
The answer is √2 – 1.
Suppose that the probability of aliens eventually dying out is x.
Then for n aliens, the probability of eventually dying out is xn because we consider every alien as a separate colony. Now, if we compare aliens before and after the first day, we get:
x = (1 /4) * 1 + (1 /4) * x + (1 /4) * x2 + (1 /4) * x3
x3 + x2 ? 3x + 1 = 0
(x ? 1)(x 2 + 2x ? 1) = 0
We get, x = 1, ?1 ? √ 2, or ? 1 + √ 2
We claim that x cannot be 1, which would mean that all aliens eventually die out. The number of aliens in the colony is, on average, multiplied by 0+1+2+3 4 = 1.5 every minute, which means in general the aliens do not die out. (A more rigorous line of reasoning is included below.) Because x is not negative, the only valid solution is x = √ 2 ? 1.
To show that x cannot be 1, we show that it is at most √ 2?1.
Let xn be the probability that a colony of one bacteria will die out after at most n minutes. Then, we get the relation:
xn + 1 = 1/4 (1 + xn + x2n + x2n)
We claim that xn ≤ √ 2 ? 1 for all n, which we will prove using induction.
It is clear that x1 = 1 /4 ≤ √ 2 ? 1. Now, assume xk ≤ √ 2 ? 1 for some k. We have:
xk+1 ≤ 1/4 (1 + xk + x2k + x3k )
≤ 1/4 ( 1 + (√ 2 ? 1) + (√ 2 ? 1)2 + (√ 2 ? 1)3 )
= √ 2 ? 1
which completes the proof that xn ≤ √ 2 ? 1 for all n. Now, we note that as n becomes large, xn approaches x. Using formal notation, this is:
x = lim (n ∞) xn ≤ √ 2 ? 1, so x cannot be 1.
翻譯：燈塔大數據
TAG:燈塔大數據 |
※我投了3百份簡歷，只換來2個面試，直到遇見1個AI
※面試時遇到這個問題，你多半都會答錯了
※面試常被問到的9個問題
※面試時，這10個問題千萬不要問面試官！
※怎樣在一年裡拿到三十多個面試
※面試著裝分析 每個季節都會成功
※10個面試問題讓你看透候選人，搞定一切面試！
※2017年新媒體運營面試常見問題！一共10個問題你能回答幾個？
※12 個無法反駁的面試技巧，最後一個才是關鍵！
※為什麼100個面試者，只有1個被錄用了？
※十條笑話：今天去面試，遇到個美女面試官
※大公司一次完美的電話面試，就12個問題，震驚所有HR！
※2017年公務員面試奇葩題目，第三個問題簡直了
※一個30年經驗的日本AV面試官：看過上萬個想拍AV的裸女胴體
※千萬別化這些妝去面試！11個步驟讓面試官蓋上合格章
※17年維密面試結束，秦舒培落榜，入選的這六位東方臉孔個個驚艷
※如何回答面試時最難的20個問題？
※這些面試的套路，你看懂了幾個？
※「當時有一千個女演員素顏面試」