Algorithms For Interviews

Adnan Aziz Amit Prakash

How to buy AFI Version Places to Buy Softcover Amazon (ships immediately; eligible for Prime/FSSS) Barnes and Nobles (eligible for free shipping) CreateSpace (ships in 1-2 days) Hardcover Amazon (work in progress) Lulu (5-10 day shipping) Indian Edition Flipkart (Rs. 600, ships in 3-5 day)

Summary

Algorithms For Interviews (AFI) is a book that aims to help engineers interviewing for software development positions as well as their interviewers. AFI consists of 174 solved algorithm design problems. It covers core material, such as searching and sorting; general design principles, such as graph modeling and dynamic programming; advanced topics, such as strings, parallelism and intractability. It also covers system design, problem solving, and interviewing techniques. AFI's authors are practicing algorithmists, with extensive academic and industrial experience. They have collectively published over 100 articles on applied algorithms, applied their skills at Google, Microsoft, IBM, Qualcomm, and a number of smaller software startups, and conducted many job interviews for various computer science jobs.

Example

Let's begin with the picture on the front cover of the book, reproduced on the right. You may have observed that the portrait of Alan Turing is constructed from a number of pictures ("tiles") of great computer scientists and mathematicians. Suppose you were asked in an interview to design a program that takes an image and a collection of s X s-sized tiles and produce a mosaic from the tiles that resembles the image. A good way to begin may be to partition the image into s X s-sized squares, compute the average color of each such image square, and then find the tile that is closest to it in the color space. Here distance in color space can be the Euclidean distance over Red-Green-Blue (RGB) intensities for the color. As you look more carefully at the problem, you might conclude that it would be better to match each tile with an image square that has a similar structure. One way could be to perform a coarse pixelization (2 X 2 or 3 X 3) of each image square and finding the tile that is "closest" to the image square under a distance function defined over all pixel colors (for example, Euclidean Distance over RGB values for each pixel). Depending on how you represent the tiles, you end up with the problem of finding the closest point from a set of points in a k-dimensional space. If there are m tiles and the image is partitioned into n squares, then a brute-force approach would have O(m n) time complexity. You could improve on this by first indexing the tiles using an appropriate search tree. A more detailed discussion on this approach is presented in the book.

If in a 45-60 minute interview, you can work through the above ideas, write some pseudocode for your algorithm, and analyze its complexity, you would have had a fairly successful interview. In particular, you would have demonstrated to your interviewer that you possess several key skills:

• The ability to rigorously formulate and abstract a real-world problem.
• The skills to solve problems and design algorithms.
• The tools to go from an algorithm to a working program.
• The analytical techniques required to determine the computational complexity of your solution.

Authors

Adnan Aziz is a professor at the Department of Electrical and Computer Engineering at The University of Texas at Austin, where he conducts research and teaches classes in applied algorithms. He received his PhD from The University of California at Berkeley; his undergraduate degree is from IIT Kanpur. He has worked at Google, Qualcomm, IBM, and several software startups. When not designing algorithms, he plays with his children, Laila, Imran, and Omar. Amit Prakash is a Member of the Technical Staff at Google, where he works 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. He received his PhD from The University of Texas at Austin; his undergraduate degree is from IIT Kanpur. When he is not improving the quality of ads, he indulges in his passions for puzzles, movies, travel, and adventures with his wife.

Reviews

• sg @ Amazon "Traditional algorithm texts are great for classroom reading, but not as good for a rapid revision of algorithms and problem solving techniques. Also, in a lot of cases, the right solution to a problem lies in some practical approaches which are informed by a good knowledge of algorithm fundamentals and experience in building systems. This book is a really great collection of problems and approaches which can be used by general problem solving enthusiasts, candidates who want to brush up on algorithms and also interviewers to dig into as a question bank."

• A @ Barnes and Nobles "A friend of mine suggested this book a few days before my interview at Microsoft. Dude, it rocks!! Very comprehensive collection of problems and good way of brushing algorithms. I was a bit rusty in problem solving, this book gave me great practice. Interview seems to have gone well, waiting for response."

• f @ Amazon "This book provides an excellent guide to picking problems and solution strategies, for an in-depth examination of fundamental skills necessary for jobs that require extensive computer programming, regardless of the application domain."

• C @ lulu.com "Your book is very promising compared to XXX and other such books in the market. I have interviews at Microsoft, Twitter, Google coming up, waiting to get your book in the mail."

• P @ Google "Read it, then come work for us."

• J @ lulu.com "Very well written, great collection of problems. Done in an entertaining way. Probably the best book out there for problem solving."

Table Of Contents

Thumbnails for table of contents - click images to enlarge, or click here to download in PDF.

Sample pages

Thumbnails for sample pages - click images to enlarge, or click here to download in PDF. You can also see a number of representative problems here.

Bugs

A bug list for the different versions of the book is maintained here. We will pay US$ 0.42 for new technical problems reported. (Please check that the bug is indeed new.) Payment will be in the form of a US check or a Paypal payment. Write to us at the email addresses published in the book. Please specify the version number and date of the book, as given on the bottom of Page (ii). Also tell us if you do not want to be credited with finding the bug - by default we will put a small attribute, e.g., Paul S., August 27, 2010.

Frequently Asked Questions

1. Why are so many algorithms problems asked in interviews?

   This stackoverflow posting gives several reasons. Some of the key insights include:

   • Algorithms and data structures are abstract concepts, which test both a candidate's ability to think through problems then translate/apply them to a problem at hand. (Timo Geusch)
   • Algorithms and data structures are fundamental building blocks of our craft. Languages and technologies change over time, but these basics don't. (Timo Geusch)
   • Programming languages or frameworks can be learned very easily. But it's very hard to develop problem solving ability. (Silent Warrior)
   • Algorithm questions are environment-agnostic and test how smart a person is. (sharptooth)

   (Also note that if you are interviewing for a position, it doesn't matter whether these are good reasons or not - you are going to be asked algorithms questions, and you need to be able to answer them.)

2. Are Kindle and Indian editions available?

   We are working on a Kindle edition; AFI is available in India from Pothi (600 Rupees).

3. What are the pre-requisites?

   Most of AFI requires its readers to have basic familiarity with algorithms taught in a typical undergraduate-level algorithms class. The chapters on meta-algorithms, graphs, and intractability use more advanced machinery and may require additional review.

   Each chapter begins with a review of key concepts. This review is not meant to be comprehensive and if you are not familiar with the material, you should first study the corresponding chapter in an algorithms textbook. There are dozens of such texts and our preference is to master one or two good books rather than superficially sample many. We like Algorithms by Dasgupta, Papadimitriou, and Vazirani because it is succinct and beautifully written; Introduction to Algorithms by Cormen, Leiserson, Rivest, and Stein is more detailed and serves as a good reference.

4. What programming languages are used for the solutions?

   Many of the solutions are at the level of working code. Most solutions are in Java and C++; a few are in Python.

5. How did you prepare the book?

   This book was typeset by the authors using Lesley Lamport's LaTeX document preparation system and Peter Wilson's Memoir class. The cover design was done using Inkscape. MacOSaiX was used to create the front cover image; it approximates Shela Nye's portrait of Alan Turing using a collection of public domain images of famous computer scientists and mathematicians. The graphic on the back cover was created by Nidhi Rohatgi.

6. How should I prepare my resume?

   Resume writing is outside the scope of our book, but we've written up a few pointers here.