IntroductionsHello 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 19992004 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. AFIInceptionCollecting 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 problemsGiven 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 HardyRamanujan 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 solutionsWriting 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 metaalgorithm for problem solving. This became the genesis for the Problem Solving chapter. With a little bit of selfindulgence, I'd say this is quite a unique chapter that I haven't seen in any other algorithms book. Adding some funAs 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:
