因不知道Reservoir Sampling演算法而掛掉面試的我是否要檢討自己？

12-31

我剛美本CS畢業，現正在找工作，投的是PHP軟工職位。
今日碰到了一位語氣溫和的印度裔面試官。他出的第一道題是：在一個長度為n的數組裡隨機抽取 k (&< n) 個元素組成一個新的數組。當然，原數組裡的每一個元素只能選一次。這題的暴力解法很直接了當，把已選元素的位置都記住，下次避開就好了。
他要求只過一遍原數組並只消耗O(1)空間，然後這題我沒做出來。後來我查了一下，發現這是個隨機演算法，叫Reservoir sampling，是Knuth的學生在斯坦福讀計算機博士時想出來的。

我不知道此面試官是想考我知識面廣度，還是想看我是不是比那位Knuth的學生還要聰明。如果是想考我知識廣度，那我顯然是不夠好的。那我應該補充哪些方面的知識才能保證以後碰到這種隨機演算法的題目不至於慌亂呢？
PS: 我不說，你們知道這題要用這個演算法解么？還是你們三十分鐘想得出來這演算法？
PS2: 我個人覺得大家說得都很有道理，我確實怨天尤人了一些。LEETCODE我也只刷了200題，而且別的一些面試信息都沒有用心去找。

零。

答不上這道題並不意味著你面試fail了。你面試fail了並不意味著原因是你沒答上這道題。

一。

對於面試而言，刷題是效率最高的。把對「能力」的考察轉化為對「知識」的考察。本來需要思考的東西變成記憶，用來打動考官。所以如果唯結果論，大量的刷題，熟悉演算法，背盡量多演算法的原理和實現，都是增加自己面試被選中幾率的方式。

二。

對於考官而言，或許他考察你的時候不僅僅是你「是否」知道這個演算法。如果你知道，那可能挺好。如果你不知道，然後靠自己的能力在短短的時間內能接近甚至達到這個演算法，是更有力的表現。換言之，如果你不僅不知道理想演算法，而且在暴力演算法之後沒能再前進一步，那可能才是讓你fail的核心。

三。

對於公司而言，這種考察方法無疑是類「高考」的「非理想但不得不」的方式。很多大公司由於面試的人太多，無法用更全面的方式來考察自己的面試者，而這種考有「標答」的演算法，是最簡單直接有區分度的方式。但是我個人是不喜歡也不認同這種考察方式的。

四。

印度人經常對中國人不友好。

中國人也經常對中國人不友好。

我以前在大公司的時候，面試經常問 Reservoir Sampling 。

通常來說在我這裡能過關的學生，是一個小時內先寫個 atoi 熱身，然後搞定主菜 reservoir sampling，最後聊下 monty hall problem。

所以問這個題目一點毛病都沒有，做不出來的話請首先反思自己的知識體系有沒有不到位的地方。然後想想這題目的思路，想想如果不知道這個演算法自己怎麼才能一步一步把問題解決掉。想想這個題目面試官有沒有 hint，自己和面試官聊的時候有沒有充分的講清楚自己的想法，有沒有做足試探給對方給你 hint 的機會。

在國外找工作的人挺大一的一個毛病就是怨天尤人。一旦掛了反正不是自己的問題，loop 裡面有印度面試官就是自己被黑，有中國面試官就是中國人不幫自己，兩樣都沒有的說人家白左公司搞 AA。

因為這個考題把你刷掉？你想簡單了。

又或者說，能因為這個把你刷掉的公司/單位，你也不用留戀。

找找其他原因吧。

人家只是想刷掉你而已。

如果你是一個顏值爆表、身材火辣、爆乳、單身的妹子，相信即使每題都答錯，對方也會說：明天來上班吧，唉，這麼多題都不會，我會每天好好地指導你的。

對了，為什麼題目標籤里會有【vczh（知乎用戶）】與【曾博】？題主你說出來，我保證不打死你。

這確實是一道面試的常見題。在好幾個公司的面經中都反覆出現過這個題。甚至是面實習生的時候。

http://www.careercup.com/question?id=5764338593824768

數據工程師必知演算法：蓄水池抽樣

有可能確實是面試官想黑你吧，儘管我不這樣認為。

面試官會因為誰是個妹子就把誰招進去？不知道很多人持這種看法是侮辱面試官還是侮辱妹子。好吧。。

一個可行的方法就是在面試前多刷刷面經，當然大牛可能會不恥這樣做。但是大牛即使不這樣做也是一把offer。

搞清楚這個問題，move on唄。好公司多得是，又何必在乎一時得失。

我是在公開課裡面學到這個演算法的。。。。Princeton的Alogorithm裡面講到的。

Leetcode只是一個面試輔助工具，不是面試範圍。。。

媽的，學海無涯…我也不知道！

這題是陳題，但是能直接給出正解的絕大多數還是刷過題的。。

正常來講一般一道題做不出來不會導致被刷掉。。放寬心，沒關係，再接再厲。

『我不說，你們知道這題要用這個演算法解么？還是你們三十分鐘想得出來這演算法？』

我們來試一試吧

21:05開始想

---

我們開始知道的只有數組長度和k。。

然後我要O(1)空間。。

考慮我們只能過一遍數組，假設我現在讀到了第i個數。。

O(1)空間。。那麼我肯定不能存前面選了的是哪些對吧。。也就是不能把前面一個選了的替換掉。。

那麼我們每次就要決定這個選或者不選。。

每個數被選的概率是k / n，考慮直接按照k / n的概率選，選滿為止。。？

有完全沒選的情況。。肯定不對。。。

怎麼去掉完全沒選的情況。。假設選了c個，按照(k - c) / (n - i + 1)來選？

其實就是P(A|B)吧。。如果我現在前面選的方案知道了P(B)，那麼窩第i個選的方案就是P(A|B) = (k-c) / (n - i +1)也就是剩下的全排列下前k - c個咯？

所以任何一種情況的概率是k! / n!了？

那就對了？

這是我經常拿來面試的幾道題之一，如果簡歷裡面有號稱做過data mining或者machine learning的人我一般可能問這道。一般我會用1 out of n來做幫助面試者熱身，之後會問m out of n。

一個人從0到1想出這道題可能比較難，但是這種題算是比較常見的類型，所以你做推薦系統的話有很大概率也是會用上的。我個人認為這不是像那種問「茴」字的四種寫法這樣的沒什麼實際意義的題。

很多演算法從無到有都很難（不過傳聞Dijkstra當年發明單源最短路徑演算法貌似也只是一頓飯的時間，不知真假）。但是如果現在先學Dijkstra演算法或者某些常見演算法，挑戰就沒有當年發明者那樣大了。

十年前，我第一次去面試Google，也是倒在這道題目上。

我腦海中第一個想到的答案居然是shuffle之後取前k個(つД`)...

歪個樓。。看上面

暈！十年前被面試這題，稀里糊塗給出了正確答案。今天才知道這是個大家深入研究過的學術問題。

蓄水池抽樣。

常見面試題。

顯然題主沒怎麼刷過題……

很遺憾，雖然沒什麼卵用，但是應屆生找工作還是需要刷題的……

本來看你是亞洲人問你道數學題放水結果你不會概率。。。問動態規劃的印度人才是存心想刷你

可以看看我對這個問題的講解： Java Solution with cases explain

印度面試官黑掉中國求職者又不是什麼大新聞...

是的。

他並不是想讓你30分鐘之內想出reservoir sampling，而是要你聽到這個需求立即說出要用到reservior sampling，然後再實現它。接著如果時間允許的話，會要求你證明為什麼它的隨機性。

多刷題吧。這種題目在面試中不算難題，演算法不算複雜，代碼量也不大。