Amit Prakash


Amit Prakash 

Introductions

Hello and welcome to my Blog! I am one of the authors of the book, " Algorithms for Interviews" (AFI). I have worked in the software Industry since 1998 (except 1999-2004 when I was in grad school) at various positions in Synopsis, Microsoft, and now Google. Currently I work primarily on machine learning problems that arise in the context of online advertising. Prior to that he worked at Microsoft in the web search team. I earned my PhD from the University of Texas at Austin where I worked on designing algorithms for high speed routers. My undergraduate degree is from Indian Institute of Technology, Kanpur.

AFI

Inception

Collecting fun puzzles and interview problems has been a hobby of mine for a long time. The idea of writing this book came to me somewhere around Fall 2008. As soon as the idea presented itself, I decided to write a book that presents the material taught in an undergraduate level algorithms course in the form of fun problems and puzzles. I teamed up with my former PhD advisor, Adnan Aziz who was also working for Google at the time. We realized that constraining all the problems to something that could be used in a software job interview would make this book immensely valuable to anyone preparing for such an interview. From time to time, I have recommended friends and acquaintances for software jobs and almost always the very next question I get after they land up with an interview is how to prepare for the interview. Recommending that they brush up a standard textbook such as CLR seems counterproductive given the time constraints. On the other hand, books like "Programming Interviews Exposed" do a great job of brushing up the basics but do not cover algorithms in much depth. Hence we decided to fill the void by writing our own book.

The problems

Given that this was mostly an evenings and weekends project for us, it took us nearly a year to collect around 150 or so problems that we wanted to present in this book. This was also the most fun part of writing this book. We recollected our favorite problems that we had accumulated over time. We invented a number of new problems. Some of the problems were created to illustrate an interesting technique in a real world setting. Some of the problems were based on experiences in building software systems. One problem that I particularly remember from this creative process is the Hardy-Ramanujan Problem where I wanted to somehow relate the 1729 story to an algorithms problem. After some thinking, I realized that the problem of finding whether a given number is the sum of two perfect cubes nicely maps to search in a Young's tableau , which has been quite commonly used as an interview question.

The solutions

Writing solutions took us another year. During this process, we realized that some of the problems that we had thought were easy enough to be an interview problem were not that easy and had to be dropped. As we solved some of these problems ourselves for the first time, new ideas came up and we created even more problems. Writing solutions for the Probability and the Dynamic Programming chapters was the most fun. While intuition played a big role in solving the problems, we also tried to capture our meta-algorithm for problem solving. This became the genesis for the Problem Solving chapter. With a little bit of self-indulgence, I'd say this is quite a unique chapter that I haven't seen in any other algorithms book.

Adding some fun

As much as I love algorithms and problem solving, I'd have hated it if we ended up with a book that just talks about one problem after the other without any fun element in between. We looked for interesting anecdotal stories about discovery of interesting algorithms. Surprisingly there are very few fun anecdotal stories about origins of algorithms. I love the one about Huffman discovering Huffman code as a class project. But there are not many such stories that we could find (if you know of any such stories that you could share, please do write to me at amit@algorithmsforinterviews.com). Another way in which we tried to make the book interesting is find quotes from some of the most original works in the field to start off the chapters.

At some point I had seen this XKCD cartoon about the traveling salesman problem:

This seemed like a perfect match for the Intractability chapter and Randall very generously gave us the permission to use it in the book. We could have found more XKCD cartoons for other chapters but that seemed like overusing Randall's generosity. At this time I teamed with my wife to create our own cartoons. After much brainstorming came the first idea for our cartoon:

  sorting cartoon
Fairly pleased with this result, both me and my wife ended up spending the next couple of weeks completely obsessed with the idea of coming up with new cartoons and had a great time doing it. I think the best one that we produced is:


[The Science of Interviewing]


















ą
Amit Prakash,
Sep 20, 2010, 10:33 PM
ą
Amit Prakash,
Sep 20, 2010, 11:29 PM
Comments