[algorithm] Reservoir Sampling

面試被問到的題目。

題目是假設有一個檔案，不知道多大，你要怎麼做寫一個程式可以印其中任意一行，然後機率要一樣。當然你可以用兩個pass，第一次算行數，第二次印指定一行。但是如果只能允許你做一次呢？

自己的想法：

假設希望每行印出機率都是p，那會走到第二行的機率就是1 - p（第一行沒印出來），印出第二行的機率希望一樣是p，那就是要乘以一個修正常數讓機率變回p，所以就是(1-p) * p / (1 - p) = p，所以第二次產生的亂數跟p/(1-p)比。第三行是前兩行都沒印出來才會到這裡，所以是(1-p)^2 * p / (1-p)^2 = p，跟p/(1-p)^2比。

不過這有幾個問題：

• 印出每行的機率總和不會是1。因為不知道有多少行，所以無法決定p初始值。
• p會越乘越小，會有誤差問題。

coding過程還有被問double 1.4被(int)強制轉型會是1還是2？（是1，floor）。那(int)(-1.4)是-1還是-2？（不知道，結果是-1。看來Java是只取整數部位）Math.random()的output range是什麼？（[0, 1))。另外遇到的Java API記錯的問題。

• BufferedReader沒有hasNext()，判斷有沒有讀完的方法是readLine() != null。
• 兩個常見的取亂數方法是Math.random()和Random rnd = new Random();  rnd.getDouble();

Reservoir Sampling演算法：

後來才知道這種演算法是有名字的，叫做Reservoir Sampling。原本的演算法是針對從N中取K個東西出來，但是事前不知道N或是N很大。用這個演算法的話也不會有我原本那個浮點數越乘越小的問題。然後最後每個元素留在buffer裡的機率都是1/N