Fourth Edition
Programming Interviews Exposed: Coding Your Way Through the Interview, Fourth Edition
Published by
John Wiley & Sons, Inc.
10475 Crosspoint Boulevard
Indianapolis, IN 46256www.wiley.com
Copyright © 2018 by John Wiley & Sons, Inc., Indianapolis, Indiana
Published by John Wiley & Sons, Inc., Indianapolis, Indiana
Published simultaneously in Canada
ISBN: 978-1-119-41847-4
ISBN: 978-1-119-41849-8 (ebk)
ISBN: 978-1-119-41848-1 (ebk)
No part of this publication may be reproduced, stored in a retrieval system or transmitted in any form or by any means, electronic, mechanical, photocopying, recording, scanning or otherwise, except as permitted under Sections 107 or 108 of the 1976 United States Copyright Act, without either the prior written permission of the Publisher, or authorization through payment of the appropriate per-copy fee to the Copyright Clearance Center, 222 Rosewood Drive, Danvers, MA 01923, (978) 750-8400, fax (978) 646-8600. Requests to the Publisher for permission should be addressed to the Permissions Department, John Wiley & Sons, Inc., 111 River Street, Hoboken, NJ 07030, (201) 748-6011, fax (201) 748-6008, or online at http://www.wiley.com/go/permissions.
Limit of Liability/Disclaimer of Warranty: The publisher and the author make no representations or warranties with respect to the accuracy or completeness of the contents of this work and specifically disclaim all warranties, including without limitation warranties of fitness for a particular purpose. No warranty may be created or extended by sales or promotional materials. The advice and strategies contained herein may not be suitable for every situation. This work is sold with the understanding that the publisher is not engaged in rendering legal, accounting, or other professional services. If professional assistance is required, the services of a competent professional person should be sought. Neither the publisher nor the author shall be liable for damages arising herefrom. The fact that an organization or Web site is referred to in this work as a citation and/or a potential source of further information does not mean that the author or the publisher endorses the information the organization or Web site may provide or recommendations it may make. Further, readers should be aware that Internet Web sites listed in this work may have changed or disappeared between when this work was written and when it is read.
For general information on our other products and services please contact our Customer Care Department within the United States at (877) 762-2974, outside the United States at (317) 572-3993 or fax (317) 572-4002.
Wiley publishes in a variety of print and electronic formats and by print-on-demand. Some material included with standard print versions of this book may not be included in e-books or in print-on-demand. If this book refers to media such as a CD or DVD that is not included in the version you purchased, you may download this material at http://booksupport.wiley.com. For more information about Wiley products, visit www.wiley.com.
Library of Congress Control Number: 2018935416
Trademarks: Wiley, the Wiley logo, Wrox, the Wrox logo, Programmer to Programmer, and related trade dress are trademarks or registered trademarks of John Wiley & Sons, Inc. and/or its affiliates, in the United States and other countries, and may not be used without written permission. All other trademarks are the property of their respective owners. John Wiley & Sons, Inc., is not associated with any product or vendor mentioned in this book.
To Thuy, the love of my life, who understands me, and Calvin, who lights up my days.
—JOHN MONGAN
To Mikey, Alex, Teddy, and Andy.
—NOAH KINDLER
To my parents, Jean-Claude and Marie-Joëlle, who encouraged and supported my love of programming.
—ERIC GIGUÈRE
JOHN MONGAN is a self-taught programmer with professional experience as a consultant for several software and pharmaceutical companies. He has three patents on software testing technologies. He holds an MD and a PhD in bioinformatics from UC San Diego, where he worked on supercomputer simulations of protein dynamics. He is currently Assistant Professor and Vice Chair, Informatics of the Department of Radiology and Biomedical Imaging at UC San Francisco. His research focuses on applications of machine learning to radiological data and computerized clinical decision support.
NOAH KINDLER is VP Technology at the security technology company Avira. He leads software design and development teams across several products with a user base of over 100 million.
ERIC GIGUÈRE started programming in BASIC on a Commodore VIC-20 (a long time ago) and was hooked. He holds BMath and MMath degrees in computer science from the University of Waterloo, has extensive professional programming experience, and is the author of several programming books. He currently works as a staff software engineer at Google.
WAYNE HEYM, PhD, is a Senior Lecturer in the Department of Computer Science and Engineering for The Ohio State University’s College of Engineering. He also collaborates with their Reusable Software Research Group (RSRG). He maintains a strong interest in RSRG’s development discipline and language, Reusable Software Language with Verifiability and Efficiency (RESOLVE). He enjoys introducing beginning programmers to the wonders in the art and science of computer programming. He also likes leading programmers into the rich and satisfying realm of the theoretical foundations of computer science.
DAN HILL is a software engineer and software development manager with over 15 years of experience, working on projects that include web development, user interface design, back-end system architecture, databases, security and cryptography, and mobile app development. He has worked for Silicon Valley startups as well as larger technology companies, and has conducted countless programming interviews. He holds BS and MS degrees in computer science from Stanford University.
WE DEEPLY APPRECIATE the efforts of our colleagues at Wiley and Serendipity23 Editorial Services in bringing this revised fourth edition to fruition. The contributions of our project editor, Adaobi Obi Tulton, whose deft edits, organization, and persistence kept us on track, and the personal attention of our executive editor, Jim Minatel, were especially key, and we thank them for their time, work, and assistance.
The quality of this edition has been greatly improved by the work of our technical editors, Wayne Heym and Dan Hill, both of whom have already made important contributions to prior editions. Their thoughtful comments and meticulous review have eliminated numerous errors and oversights and immeasurably improved the clarity of the book. We thank them for their extensive work. We are also grateful to Andrew Taylor for additional review of the new data science material, and Tom Mongan for assistance with proofreading.
No fourth edition would have been possible without the three that preceded it, and the many people who contributed to them. John is particularly grateful for Michael J. Mongan’s help in facilitating his participation with the third edition. We thank our third edition editor Maureen Spears, who swiftly and surely overcame the unique challenges that arose in preparation of that edition. Additionally, we thank our original editors, Margaret Hendrey and Marjorie Spencer, for their patience and helpfulness. We are also grateful to our original reviewers and advisors, Dan Hill, Elise Lipkowitz, Charity Lu, Rob Maguire, and Tom Mongan. Dan’s contributions in particular were tremendous—the quality of the first edition was vastly improved by his careful and detailed reviews.
This book was written to prepare you for the technical interview process so that you have no problem demonstrating how great a programmer you are. It doesn’t teach you how to program; it shows you how to use the programming skills you have to shine in a programming interview. As you read this book, keep in mind that programming interviews (for the most part) are not factual recall tests, so this book isn’t a cheat sheet of all the facts you need to know for your interview. Instead, it teaches by example the techniques and thought processes you need to succeed. The best way to internalize these is to take time to work through and understand the problems.
Why do software firms use programming interviews? They want to hire great programmers who can work well with others to successfully produce great products. Unfortunately, bitter experience has taught employers that a substantial portion of applicants for programming jobs simply cannot code. You might expect that these applicants could be screened out by careful review of résumés, experience, course work, and degrees, but in practice this often fails. A surprisingly large number of applicants with sparkling résumés and years of apparently relevant industry experience cannot accomplish even the simplest of programming tasks. Many of them have picked up enough terminology that they can appear competent in conversations about programming and technology. Hiring one of these “developers” who can’t code can easily sink a department (or even a small company).
Recognizing that traditional interviews are ineffective in identifying applicants who can’t code, employers took a logical step: ask applicants to do some coding during the interview. Thus the programming interview was born. Programming interviews are extremely effective at separating those who can code from those who can’t, which is why they are a nearly universal part of the technical interview process.
The difficulty with programming interviews is that employers don’t just want to screen out people who can’t code. Employers want to distinguish the best programmers from those who are merely competent. This is a more difficult distinction to make. Typically, interviewers try to measure an applicant’s ability by posing difficult programming challenges and noting how quickly and accurately the applicant solves them.
The problem with this approach is that due to the time restriction inherent to an interview, the skills that can be tested in a programming interview only partially overlap the skills that are relevant to real-world development. By necessity, programming interviews evaluate your ability to solve problems on the spot, with someone watching you, without the benefit of any of the references you would typically have available. There isn’t time to write a lot of code, so problems must have short solutions. Most problems with short solutions would be trivial, so to avoid this many interview problems involve unusual algorithmic tricks, absurd restrictions, or obscure language features. Because these types of problems don’t typically arise in real-world development, an excellent programmer who is unprepared for the peculiarities of the interview experience may appear to be unqualified.
Conversely, many skills essential to development in a professional environment aren’t assessed well (or at all) in programming interviews. These include communicating and working as part of a team; architecture and management of large codebases; time management and discipline to consistently produce reliable code on schedule; and the ability to tackle a large project, identify all the component parts, and carry the project through to completion.
Clearly, programming interviews do not provide a perfect measure of an applicant’s worth as a future employee. But to paraphrase Churchill’s assessment of democracy, it’s the worst form of technical interview except for all the other forms that have been tried. More to the point, programming interviews are the way employers choose who they will hire, so you need to perform well in them regardless of whether they are an ideal form of assessment. This book is devoted to teaching you how to adapt your programming skills to the peculiarities of interview problems and gives you the preparation and practice you need to shine in interviews so that you get the job you want.
Preparation is the key to mastering the programming interview process. The following are some general guidelines on how to effectively use this book to prepare for programming interviews:
Now, let’s get started!
Solving problems that are presented in programming interviews requires a separate skillset from what you need to be a good programmer. Just like anything else, you probably won’t be very good at this when you first start, but you can develop and improve your skills just as we did. This book is the first step in that process; through this book we leverage your programming expertise to rapidly turn you into an expert at programming interviews.
Since the first edition, Programming Interviews Exposed has effectively established a new topic area of programming books, and now a multitude of websites, blogs, and forums provide advice and sample questions. With all that available, why should you invest your time and money in this book?
Our focus continues to be on teaching you the techniques and approaches you need to be successful in programming interviews. We reinforce these by illustrating the thought process that leads to the solution of each of the problems we present, and show you how to move forward when you’re stuck. These skills overlap with general coding skills, but they’re not the same; we’ve seen great coders crash and burn in programming interviews because they haven’t developed their interview skills. Early in our careers we crashed and burned a couple times ourselves, but you can avoid that by beginning your preparation with this book. Once you’ve learned the skills taught in this book you’ll continue to learn by applying them to the problems you find in other books and on the web, but this is the book you want to start with.
One thing that never changes is that to become good at solving programming interview questions, you have to do more than passively read about them: you need to practice them. You’ll get a lot more out of this book if you work out as much of each solution as you can on your own before you read about it.
Although the content of the book has expanded significantly since the first edition and the languages employed have shifted, we’ve stayed true to the goals and approach we set out then, described in the original preface, which follows.
If you’re like us, you don’t usually read prefaces. This one has some useful information in it, though, so we hope you’ll make an exception. If you’re still tempted to skip the preface, here’s what you really need to know: You’ll get as much out of this book as you put into it. If you read this book cover to cover, you’ll learn something, but not nearly as much as you would if you take some time trying to work through the problems on your own before you read the answers.
This book will help prepare you for the interviews you will face when seeking a job in programming, development, technical consulting, or any other field that warrants a programming interview. Programming interviews bear little resemblance to those described in traditional job-hunting and interview books. They consist almost entirely of programming problems, puzzles, and technical questions about computers. This book discusses each of the kinds of problems you are likely to encounter and illustrates how they are best approached using questions from real interviews as examples.
At this point you may be wondering who we are and what gives us the authority to write this book. We’re both recent graduates who’ve been through a lot of interviews in the past few years. We’ve interviewed for jobs ranging from technical consulting with large established companies to writing device drivers for startups. This book is based on the experiences and observations we’ve taken from those interviews—what yielded offers and what didn’t. We believe that this is the best possible basis for a book like this. Rather than give you some HR exec’s idea of how interviewing should be done or a head hunter’s impression of how it might be done, we will tell you what interviews are really like at America’s top software and computer companies and what you need to do to get the job you want.
To that end, we haven’t made up any of the questions in this book. Every last one of them has been lifted from a recent interview. The distributions of problem type and difficulty are similar to what you should expect to encounter in your interviews. We must emphasize that the problems presented in this book are a representative sample of the questions asked in interviews, not a comprehensive compilation. Reading this book straight through and memorizing the answers would completely miss the point. You may be asked some of the questions that appear in this book, but you should not expect that. A large and constantly changing body of questions is asked, and any intelligent interviewer who has seen this book will never again use any of the questions that appear here. On the other hand, interview questions encompass relatively few topic areas and types of questions, and these rarely change. If you work on learning to solve not just the specific problems we present, but the types of problems we present, you’ll be able to handle anything they throw at you in an interview.
We’ve taken a couple of steps to facilitate the objective of improving your problem-solving skills. First, where appropriate, we provide reviews of important topics before we present questions on those topics. Second, instead of merely giving answers to the problems, we illustrate the problem-solving process from beginning to solution. We’ve found that most textbooks and nearly all puzzle books take a different approach to examples: they begin with a problem, go immediately to the answer, and then explain why the answer is correct. In our experience, the result is that the reader may understand the particular answer and why it’s right, but is left with no clue as to how the author came up with that solution or how a similar problem might be solved. We hope that our step-by-step approach to solutions will address this issue, helping you to understand not only the answers but also how you arrive at the answers.
Learning by watching is never as effective as learning by doing. If you want to get the most out of this book, you will have to work out the problems yourself. We suggest the following method:
The more of the solution you work out yourself, the better your understanding will be. In addition, this method closely resembles the actual interview experience, where you will have to solve the problems yourself, but the interviewer will give you hints when you get stuck.
Programming is a difficult and technical art. It would be impossible to teach everything you need to know about computers and programming in one book. Therefore, we’ve had to make some assumptions about who you are. We assume that you have a background in computers equivalent to at least the first year or two of a computer science degree. Specifically, we expect that you are comfortable with programming in C, that you’ve had some experience with object-oriented programming in C++ or perhaps Java, and that you know the fundamentals of computer architecture and computer science theory. These are effectively the minimum requirements for a general development job, so most interviewers will have similar expectations. If you find yourself lacking in any of these areas, you should seriously consider seeking more education before starting your job search and interviews.
It’s also possible that you have a great deal more computer knowledge and experience than what we’ve described as the minimum requirements. If so, you may be particularly interested in some of the more advanced topics included. However, don’t ignore the basic topics and questions, no matter how much experience you have. Interviewers tend to start with the fundamentals regardless of what’s on your résumé.
We have made every effort to ensure that all of the information in this book is correct. All of the code has been compiled and tested. Nevertheless, as you probably know all too well from your own programs, a few bugs and errors are inevitable. As we become aware of such problems, we will post corrections.
We’re confident that you’ll find this book useful in getting the job you want. We hope that you may also find it an entertaining exploration of some clever puzzles in your chosen profession. If you’d like to tell us about your reaction to our book, share your thoughts on any particular problem or topic, or provide a problem from one of your recent interviews, we’d love to hear from you.
Go find a killer job!