Facebook Engineering Puzzles

A colleague of mine pointed me to the facebook engineering puzzles page yesterday. And I tried to give a shot to first one (the liar-liar puzzle). It took a good number of my hours today but it was fun.

And, I succeeded in first submission itself :). Here is the mail from facebook that I received:

from Facebook PuzzleBot
to g.himanshu@gmail.com
date Sat, Sep 11, 2010 at 4:45 PM
subject liarliar evaluation results
mailed-by facebook.com


Dear submitter,

Thank you for your submission of a puzzle solution to Facebook! After running your solution to liarliar (received on September 11, 2010, 12:37 am), I have determined it to be correct. Your solution ran for 2508.850 ms on its longest test case. If you have not already, try installing the official Facebook Puzzles application from http://apps.facebook.com/facebookpuzzles/ and publish a story about your solution! To publish, just go to http://apps.facebook.com/facebookpuzzles/mypuzzles.php and click on the publish link.

If you are applying for a position within Facebook, the puzzle difficulty solved will be taken into account with regards to how much time you had available to solve it (remember that Hors D'oeuvres are only tests for your benefit). I have taken the liberty of alerting our recruiting team about your success. Best of luck!

Sincerely,
-The puzzle robot

sorry, but no open sourced code this time for obvious reason. :P

[Update#1] I got the 2nd one(breathalyzer) accepted also. It took multiple submissions though :( and hence more time.

[Update(May 02 - 2011)] After a long time, yesterday I worked on Gattaca puzzle and nailed it. Regarding the timing, bot says, it took 4132.647 ms on the longest test case. My first solution was O(2^n) as I thought this was NP-hard problem which got rejected. I then followed the discussions on it and realized that this was *not* NP-hard and managed to work out the code that runs in O(n^2) in the worst case.

[Update(May 08 - 2011)] dancebattle is finished too. My first submission was accepted but longest test case time was 1108.22 ms. Then I optimized it a little bit, resubmitted and then bot says, it took 263.009 ms on it's longest test case :).

[Update(May 09 - 2011)] smallworld is done. Note that trivial O(n^2) solution does not succeed. Bot says, my solution took 9928.117 ms on its longest test case.

[Update(May 16 - 2011)] Today I received acceptance email for my solution to fridgemadness (Refrigerator Madness). Hardest part in this puzzle is to really understand the problem :). Regarding the timing, puzzle bot says, it took 362.562 ms on its longest test case.

Habits that make you a better programmer in the long run

I read a thread on hacker news on "what habits made you a better programmer?". Here are some of the things(in no particular order) that resonated with me personally.

• Learning new things. Every year or so try to learn a new major skill like functional languages, AI, Compilers, OS etc.
• Think first, write later.
• Read great code written by great people and read your own code also.
• Surround yourself with real smart people.
• Spend an extra hour or so after you're *done* with something to give it finishing touches, do the edge cases.
• Work on what is exciting to you, then switch when the excitement wears off and switch back again when excitement for it comes back. Though, it needs some level of discipline to come back.
• Have discipline to go 100%, keep the notes and write blog.
• Learning to love new languages that make you think differently.
• Learn one editor really well.
• Write small utility project/programs for the tool/technology you're curious about rather than waiting for THE master project.
• Find someone to pair program with who is a great programmer.
• Persistence and Patience are a virtue.
• Keeping healthy body and mind is very important. Practice yoga or something regularly.
• Socialize, be part of hack/code fests and such forums and groups.

Performance Tuning

I'm scribbling here my recent(and ongoing) experience with performance tuning a java web application. Like any other article on optimization, I'll start with the quote, "Premature optimization is the root of all evil.". My take is that don't *optimize* prematurely, but do not make it an excuse for *not measuring* the performance of your system. It is good to know how your system performs at all times.

Anyway, here is the common way(was reinforced after attending a talk on performance tuning in devcamp-2010) that everyone knows about but I'm just putting here anyway...

1. Pick conservative hardware and install your application on it.

2. Create a large sample(but realistic) dataset. It might be good to just take a dump from production and load your system with it.

3. Put your system to extreme load. In general the load will be very general doing all the functions on your system. But, in the special case where you're just exploring one feature's performance/GC-activity then put the load on that feature only. Use any of the load generation tools... Apache Bench(non-gui) and Apache Jmeter(gui as well as non-gui modes) are two free ones.

4. Measure, Measure and Measure.
This gets tricky, I've tried to use hprof for memory dumps, Runtime.freeMemory and Runtime.maxMemory methods for memory consumption analysis but ended up using a profiler(a commertial one that is standard in our org) and it really helps.

5. Make your change if any and then measure again and keep repeating.

6. Automate, as much possible, the whole process for faster feedback loops.

So far we've found following major boosters..

1. Putting indexes, we always were very careful while putting indexes as they become overhead for write/update heavy tables, but later found there are many tables where indexes are helping alot more than we imagined.

2. We noticed that alot of garbage was generated and most of it was char[] data resulting from a lot of Strings. And finally figured out that the culprit was heavy amount of logs *printed*. However, Note that log statements in the code are not that expensive but printing them is. So, for prod/perf environment set print log level to ERROR and be very careful while putting log statements in app(I mean being judicious about what level you print the log in.. DEBUG/INFO/WARN/ERROR/FATAL), anything in log.error should really be an error.

3. Guarding log.debug statements with log.isDebugEnabled.

4. Caching with LRU(policy may very well depend on particular use case)

[Update:] We realized that our background jobs are very memory/cpu hungry, so we created a separate job node to run just the background jobs. It is improving the performance of serving synchronous client requests tremendously. However, we are still working on to make background jobs more efficient in terms of memory/cpu usage.

[Update:10-12-10] We realized that we usually used bind variables in sql/hql queries when wrote them by hand but when generated dynamically, we forgot(its easy) to use bind variables. Also, we never used bind variables wherever we had IN clauses. Since we all know that it is more efficient to use bind variables to reduce parsing times in db(they get more cache hits on already parsed sqls), So we are paying this technical debt and correcting all of this now. While we're doing it, it seems it would have been a simpler exercise if all the hql and sql statements were written in one place then it would have been easier to go through all of them as right now they are all scattered in different places in the big project code-base

[Update:14-12-10] We are resorting to use bulk manipulation queries and they are giving significant improvements. To take an extreme example, it is much efficient to directly execute query, "UPDATE TABLE t SET c = 'blah'", than iterating over every data object, updating it and saving it(unfortunately, ORMs give us the habit of thinking always in terms of objects and we forget to use these simple optimizations).
Also, I find the contents on this stackoverflow thread very informative and It seems I've also made some of the mistakes mentioned there :).

[Update:10-03-11] Never leave memory requirements of an operation unbounded. If your memory requirement increases in proportion to some dataset size and you believe that dataset size is upper bounded then place some mechanism so that if the dataset size goes beyond your assumption then somehow you get the notification. In my experience, usually my assumptions were either wrong or with time the load grew and assumption became wrong.. so it is much better if you plan your code so that dataset size is also bounded by design rather than by belief :). For example if you're fetching a list of records from database, probably there will be good enough reasons to use pagination parameters.

Plan - Introduction to Probability

I'm working through, Introduction to Probability. Yesterday, at devcamp, I met Ravi and as always he was curious about my progress with the book. So, here it comes, the plan to finish this book :).

1. Ch-1, Sample Space and Probability -- Done
2. Ex* + Ch-2, Discrete Random Variables -- Done
3. Ex + Ch-3, General Random Variables -- Done [on Sep 05' 10]
4. Ex + Ch-4, Further Topics on Random Variables -- Done [on Sep 16' 10]

Problem-Set#1 - Done [on Sep 26' 10]
Problem-Set#2 - Done [on Sep 27' 10]
Problem-Set#3 - Done [on Sep 28' 10]
Problem-Set#4 - Done [on Sep 29' 10]
Problem-Set#5 - Done [on Oct 04' 10]
Problem-Set#6 - Done [on Oct 04' 10]

5. Ex + Ch-5, The Bernoulli and Poisson Processes - Done [on Oct 09' 10]
6. Ex + Ch-6, Markov Chains - Done [on Oct 16' 10]
7. Ex + Ch-7, Limit Theorems - Done [on Oct 23' 10]

Problem-Set#7 - Done [on Nov 2' 10]
Problem-Set#8 - Done [on Nov 2' 10]
Problem-Set#9 - Done [on Nov 2' 10]
Problem-Set#10 - Done [on Nov 23' 10]
Problem-Set#11 - Done [on Nov 23' 10]
Problem-Set#12 - Done [on Nov 23' 10]

Ex* - working through few end of chapter exercises of the previous chapter done.
Problem-Set* - This book is used as text book in probability course in MIT. I intend to work through all the problem-sets that were given as assignments in this course.

I have intentionally not put any dates above as they never work out for me(my schedule is not completely in my control). That said, I believe each chapter should take a week or so. I will keep on updating this post with dates whenever I get done with a chapter or a problem set.

While working through it, I'm trying to follow advices given here. I really wish to follow the advice of , make the idea your own, and looking for people working through this book.

@devcamp - 2010

This is the first devcamp I attended. Once I got to thoughtworks, I was promptly attended, felt welcomed and shown the hall where the action was about to begin. It was a big hall filled with many (supposedly)geeky people with laptops. There was a board in the front, mentioning 3 tracks, to be run in parallel, with stickies mentioning the topics to be presented.

All the presenters came to introduce themselves and to introduce their sessions. On another board some topics were listed for QnA and I found it interesting that people were voluntarily chosen from the audience to answer the questions for various topics.

And then, the sessions began... and throughout the day, things went on and on and on. Among many good things, there were some things I especially noted...

- Audience were demanding and asking questions, looking for the explanations.
- Presenters had running code to show.
- A very informal environment was created due to lack of space in the rooms, no one had any problems sitting on the floor.

And, did I say I got a devcamp tshirt also :).

All in all, It was a good experience. Thanks to all the people who were behind the event, it ran pretty smooth.

ignoring emacs auto buffers in (next/previous)-buffer

I am about 2 yr old emacs user now. I've been doing basic stuff with emacs for long and now trying to transition into emacs power user after getting inspiration from screencasts like this one. More such vids can be found at emacs wiki.

Anyway, The traditional commands for going to next and previous buffers in emacs are "C-x <left/right arrow>". I read a pro tip somewhere that whenever you use next/prev buffer commands, you almost never want to go to one of emacs auto buffers such as *scratch*, *Messages* etc and that unnecessarily slows you down. It sounded so true to me and I got the itch to write elisp for it that ignores those buffers and here it is(I'm sure it could be done better, but then I'm a noob :) )

(defun emacs-buffer-p (name)
  (string-match-p "\\*.*\\*" name))

(defun next-non-emacs-buffer (&optional original)
  "Similar to next-buffer, but ignores emacs buffer such as *scratch*, *messages* etc."
  (interactive)
  (let ((tmp-orig (or original (buffer-name))))
    (next-buffer)
    (if (and
         (not (eq (buffer-name) tmp-orig))
         (emacs-buffer-p (buffer-name)))
        (next-non-emacs-buffer tmp-orig))))

(defun previous-non-emacs-buffer (&optional original)
  "Similar to previous-buffer, but ignores emacs buffer such as *scratch*, *messages* etc."
  (interactive)
  (let ((tmp-orig (or original (buffer-name))))
    (previous-buffer)
    (if (and
         (not (eq (buffer-name) tmp-orig))
         (emacs-buffer-p (buffer-name)))
        (previous-non-emacs-buffer tmp-orig))))

and re-mapped "C-b", "M-b"(I never used their default keybindings anyway) to them

(global-set-key (kbd "C-b") 'next-non-emacs-buffer)
(global-set-key (kbd "M-b") 'previous-non-emacs-buffer)

Now if, occasionally, I want to goto emacs auto buffers then I can still use "C-x <left/right arrow>".

how to prove it - a retrospection

I just finished working through velleman's how to prove it. All of my notes and solution to exercises can be found here. After reading it, here is what I think.

What I expected before I started reading it?
I expected to learn how mathematicians *think* when they encounter a conjecture. And, hoped that this would make it easy for me to read/understand any proof based books like cormen et al.

What I found?
Essential logic theory, A *solid* understanding of the abstract *structures* used in proofs and how these structures come from logic. You learn set, relations and functions for free as side effects :)

It helped a lot to have some understanding of (propositional)logic and quantifiers before I started reading this book. After working through this book when you will look at any proof, you will first understand the abstract structure behind the proof(in fact you'll just get it without even thinking about it) and then understand the specific details of the particular proof.

In short, I'm glad I read it. Thanks to Ravi for pointing me to it.