Thursday, December 6, 2012

Cracking the coding interview[s] (?)

News come and go, but the hype they create, remains for some time, some times, they ask questions about that on Quora, so again, here's a direct cross-post from Quora

How was Sujeet Gholap able to crack the biggest companies?

Read Sujeet Gholap's experience: Indian Institute of Technology, Madras: What is it like to sit for placements on December 1st?
What was his preparation track? Which areas did he focus upon? How did he learn programming?

My answer:

I guess my answer won't be of much help, I hope it will be interesting though...

How it ideally should have been:
Be an active member of topcoder, keep solving programming problems in other places too if you want like spoj, usaco and careercup(?), interviewstreet(?). Then you will start seeing patterns, and after seeing problems, you would be exclaiming "Oh! That's an N square DP!" "Let's do this by simple BFS with pruning!" "Let's do this much of pre-processing, and then every query will be blazing fast!" That's not what happened with me.

I wish I had taken these things seriously and honed my algorithmic programming skills. Then, I would not have been the one with the guilt "Did I really deserve this or was I just lucky?" "I guess I just happened to be in a premier institute and chanced upon good jobs. I don't think I could have made it to any of these companies on my own."

So, if you are reading my answer for some advice for cracking coding interviews by being a good programmer in general and algorithms programmer in particular, stop. Go read CLRS properly and do problems on one of the above mentioned sites! Even I am going to do that once I get some free time!

Now, if you want to read about the interesting(?) story of how I got lucky and cracked so many interviews, read on!

Slumdog Millionaire:

The main theme here is same as that of Slumdog Millionaire. Just like in the movie, I was lucky that I had discussed/talked about similar questions before, and hence was able to make it through the interviews.

Paying attention in classes:

Yeah! That's how I answered many questions. For example, in one interview, I was asked questions about caches, and wow! I had just finished a course on computer system design (a whole lot of which was just cashes cashes and cashes). Any questions which were not algorithm intensive questions and were more or less straight knowledge based, I could just recall the answer straight from the class when the professor taught that particular topic! There were a few OS questions ranging from "what is an OS?" to "Tell me some page replacement policies and their pros and cons." There were a few networks questions and a few to do with paradigms of programming (functional vs procedural etc)

Taking advantage of the awesomeness in the peer group:

During this semester, there was a time when I used to ask Arijit for a algorithms problem everyday, then while brushing teeth, while taking shower, on lunch table (in case I was dining alone) I would think about how I would solve that problem, if I get it, I would call him up and discuss the answer and ask for more. Why? Remember the first paragraph: "How it ideally should have been"? That's more or less the description of Arijit. A pretty good topcoder, he even has represented India in ACM ICPC this year.

Taking advantage of the sincerity in the peer group:

You know you are not really a sincere and studious person. What do you do? Make friends with sincere and studious people! Much better if it is the other way around (I mean you are already friends, and they happen to be sincere and studious). Enter Madhavi and Vikram. It was never a surprise when I asked Vikram even as early as October end "What's up?" and got a reply "Placement preparations!" I could never just get myself serious enough to sit down, open a book or something and prepare for these interviews. But I have to do it, right? So I made it a point to make him to get me to solve problems along with him. I used to talk to Madhavi about various puzzles etc. When I had barely started preparing for Tower Research interview (it mostly consists of math and logic puzzles), this girl already had a book full of such interview puzzles! Vikram and I just got hold of that book and then on, till we finished the math-logic puzzles part, everyday we would do those puzzles over breakfast in the mess.

Luck might just be on your side!

One year back, I had asked Gunaa about his Facebook interview question. He was asked to design an event of 1/2 probability using a coin with 'p' as the heads probability. Then, I had thought about possible extensions : how about implementing an event of m/n probability using an unbiased coin? Is it possible? How would I do it? Looks like interviewers run out of questions pretty soon... I was asked exactly the same one in Goldman Sachs interview, it is a different story that I had not really thought of the solution, but still, having a problem to work on, which sounds familiar is always comforting.

When she appeared for some off-campus interview for a company, I had asked Madhavi to tell me what questions were asked. One was about building a simple regular expression matcher. Sounded interesting. For the next few days, whenever I had some free time and felt like thinking about some problem, this was it. I even considered possible variations of the problem like "What if we allow more powerful regular expressions?" "Here, even brackets are not allowed. How will I solve the problem if the regex has brackets too? Ideally it should just affect the parsing part, right?" I thought on these lines and had a basic skeleton, a rough sketch of a regexp matcher ready in my head. I had given a thought to questions like "How would I generate an NFSA given a regex? How to combine two NFSAs and arrange them in a series? How to apply a '*' to an NFSA?" Not just that, when everyone was preparing for Natural Language Processing end-of-semester exam, I was coding this thing up! Surprise, surprise! In one of the written tests, the whole test consisted of designing a regex matcher! Wow! I did not have to think anything at all. Everything was fresh in my head, just jotted it down on the paper. In the interview later I learnt that they were so impressed with my answer that they did not want to ask any technical questions. The interview then just consisted of casual chat, some talk about the company and the role I would be playing in it.

Just the day before the interviews, I realized that I am totally blank about how to go about doing the N-queens problem! Pradeep, another friend of mine, patiently explained the solution to me, he made me remember how it fits well within what we had learnt in the AI course. Guess what! Google interview question on almost same lines! BFS state search with pruning!

Early morning on the day of interviews, I was still a bit underconfident. I had almost no time remaining for preparations and I thought that so many things need a revision. It was time to pick and choose, I chose hash tables. I quickly skimmed through the hash table related chapter in CLRS and barely made to the interviews on time. Lucky day again! a total four or so interviews had some questions something to do with hash tables!

Confidence and passion are always a plus:
Although almost all interviews asked me about my projects during internship at both Yahoo! Labs and Facebook, I patiently and passionately explained whatever I could reveal without violating the NDAs I had signed. When it comes to class projects, there were many, but the one which I was most passionate about was a pretty small one. I chose to go with that one still. The enthusiasm and passion with which I explained that project, had visibly impressed most of the interviewers.

2 comments :

  1. "The harder one works, the luckier one gets!" :)

    Reply Delete
  2. Umm... is it just me or is the blogpost title particularly chosen to get more hits/improve page rank?

    Reply Delete

Post a Comment