好玩的Facebook puzzles
The puzzles which I solved:
最近在找工作，因為我的本行(信號處理)的工作都死光光了
看清了這一點，所以我轉戰軟體工作
(這故事說來話長，之後有時間再解釋)
總之我為了找軟體業的工作，每天都努力的充實我的程式功夫
這幾個禮拜，每天應該都寫快要1000行的程式練功
後來因為申請Facebook的工作，有不少人建議去做他們網站上的程式puzzles
這些puzzles會定義好某種需要的輸入輸出
解puzzle的方法就是寫一個程式滿足這輸入輸出
例如其中的一個puzzle會被輸入一個檔
這個檔裡面有很多個點，每個點是用(x,y)這樣的二維座標定義
要求的輸出是，對於每一個點，都列出離它最近的三個點
而且這個方法要夠快
平方等級( O(n^2), 就是比較慢的 )的算法是不會被接受的
解puzzle的方式，就是你用網站上所支援的語言(我試過C++和Python)
寫成可以編譯/執行的程式，寄去他的email信箱
Facebook有一個機器人程式，會幫你測試你的輸入輸出有沒有正確
如果正確你就會收到一封email，說你的程式通過測試了
然後Facebook還有一個application叫puzzle badge，就是上面那張圖
它會在你的Facebook首頁上顯示說你做對了那幾題
上面那張圖就是我的puzzle badge
我試了做一題之後，就瘋狂地迷上這個東西
對我而言這就好像打電動一樣，就連吃飯睡覺的時候都很想快點跑去寫
好在現在已經全破了(只剩下一題，不過聽說那題沒人做對過)
終於可以回到健康的生活型態了
不過Facebook會不時出現一些新的Puzzles，到時候又可以再上去做
這些題目都包裝的非常有趣，例如有一題就是你是一隻zerg的overlord
你要分配手上的zerg去打人類的基地，人類的兵力和基地的礦已知
要用最佳的方法去分配這些zerg
如果你有玩starcraft，就會覺得超有趣的
但事實上這些題目都是
computer science或是數學裡面非常有代表性的演算法
如果你曾經看過這些算法，你就知道要怎麼辦了
總之這個東西非常好玩，如果你對寫程式有熱情的話
或是想要練練程式和演算法
推薦你去試試
http://www.facebook.com/jobs_puzzles/index.php
哦，對了，我忘了說，如果你想apply他們的工作
做puzzles做的好的話，就會得到interview機會
最近在找工作，因為我的本行(信號處理)的工作都死光光了
看清了這一點，所以我轉戰軟體工作
(這故事說來話長，之後有時間再解釋)
總之我為了找軟體業的工作，每天都努力的充實我的程式功夫
這幾個禮拜，每天應該都寫快要1000行的程式練功
後來因為申請Facebook的工作，有不少人建議去做他們網站上的程式puzzles
這些puzzles會定義好某種需要的輸入輸出
解puzzle的方法就是寫一個程式滿足這輸入輸出
例如其中的一個puzzle會被輸入一個檔
這個檔裡面有很多個點，每個點是用(x,y)這樣的二維座標定義
要求的輸出是，對於每一個點，都列出離它最近的三個點
而且這個方法要夠快
平方等級( O(n^2), 就是比較慢的 )的算法是不會被接受的
解puzzle的方式，就是你用網站上所支援的語言(我試過C++和Python)
寫成可以編譯/執行的程式，寄去他的email信箱
Facebook有一個機器人程式，會幫你測試你的輸入輸出有沒有正確
如果正確你就會收到一封email，說你的程式通過測試了
然後Facebook還有一個application叫puzzle badge，就是上面那張圖
它會在你的Facebook首頁上顯示說你做對了那幾題
上面那張圖就是我的puzzle badge
我試了做一題之後，就瘋狂地迷上這個東西
對我而言這就好像打電動一樣，就連吃飯睡覺的時候都很想快點跑去寫
好在現在已經全破了(只剩下一題，不過聽說那題沒人做對過)
終於可以回到健康的生活型態了
不過Facebook會不時出現一些新的Puzzles，到時候又可以再上去做
這些題目都包裝的非常有趣，例如有一題就是你是一隻zerg的overlord
你要分配手上的zerg去打人類的基地，人類的兵力和基地的礦已知
要用最佳的方法去分配這些zerg
如果你有玩starcraft，就會覺得超有趣的
但事實上這些題目都是
computer science或是數學裡面非常有代表性的演算法
如果你曾經看過這些算法，你就知道要怎麼辦了
總之這個東西非常好玩，如果你對寫程式有熱情的話
或是想要練練程式和演算法
推薦你去試試
http://www.facebook.com/jobs_puzzles/index.php
哦，對了，我忘了說，如果你想apply他們的工作
做puzzles做的好的話，就會得到interview機會
留言
我也想玩~~
可是寄執行檔給過去，他們不怕收到病毒嗎？
因為有個朋友想留言給另一個朋友結果不小心變成更新自己的狀態，所以就被所有人看光光了....原因在於臉書的「塗鴉牆」和「你在想什麼」是長得一模一樣的....請工程師向上建議想個辦法唄~~留言留到被人家看光光還滿冏的... :p
但是我要到六月才會去上班
到時候我再跟他們說
Long time no see. I heard of your great news from Tony so I came up here and say congratulation to you. Congratulation, and welcome to our (programmer's) world. I'd like to recommend one excellent book to you, ``Programming Pearls'' by Jon Bentley. If you have any library in the neighborhood, be sure to get one. The materials would surely make great exercises for you.
By the way, I believe that a simple program based on quicksort/mergesort could solve the problem in O(n log n) time for keeping constant number of nearest neighbors for each node.
Cheers,
cobain
It's really been a long time since I saw you last time. I think it must be more than 10 yrs. How have you been? I hope you're doing well.
And thanks for the suggestion. I will go check out that book. Right now I have a huge collection of books in algorithms, combinatorial optimization, software engineering, user interface and lots of popular languages.
As for this puzzle, I think what you suggest might work (but I solved it using other approach). Try coding it and submit it to the puzzle bot. It's fun!
And that sounds pretty cool. Algorithm and combinatoric optimization totally work for me, too. I'm not much a math guy but it's already an old habit to keep track of any new development in the research field. Good luck and happy hacking!
Oh. I think I will. I am totally into the problem (``all-nearest-neighbor''). I've been sitting here in front of my desk reading articles since I left the comments. And that's completely fantastic. Thanks for the brain teaser, dude.
p.s. It turns out my intuition wasn't quite right. The best algorithm is indeed merge-based and it runs in O(kn + n log n) time, but on the other hand it is way too complicated to be called ``simple''.
One good thing about the Facebook puzzles is that these are all fundamental and important problems. And there are good theories behind the problems. I will start working on the new Thrift problems after my revision of the thesis is done.
It's good that I have finally found a friend who's also doing these puzzles :)
I'm glad that I came up here and talked to you, that gave me an idea this problem can probably be well-studied so that I could use a little bit search on my own. Otherwise, I could still work on it for months without noticing that we could already do this.
Oh, I'm also happy to see you enjoying so much in these stuffs that I love. Already spend too much time of yours. Let's catch up a bit later. If you should make a trip back to Taiwan in the near future, be sure to let me know.
Cheers.