www.allitebooks.com
Programming Interviews ExposedFourth Edition
PROGRAMMING INTERVIEWS EXPOSED
PREFACE . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . xxv
INTRODUCTION . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . xxix
CHAPTER 5
CHAPTER 6
CHAPTER 3
CHAPTER 2
CHAPTER 1 Before the Search. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1
The Job Application Process . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
The Phone Screen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
CHAPTER 4 Approaches to Programming Problems . . . . . . . . . . . . . . . . . . . . . . 29
Linked Lists . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41
Trees and Graphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 75
CHAPTER 7 Arrays and Strings . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 99
Recursion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 125
Sorting . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 143
CHAPTER 10 Concurrency . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 165
CHAPTER 11 Object-Oriented Programming . . . . . . . . . . . . . . . . . . . . . . . . . . . . 181
CHAPTER 12 Design Patterns . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 193
CHAPTER 13 Databases . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 203
CHAPTER 14 Graphics and Bit Manipulation . . . . . . . . . . . . . . . . . . . . . . . . . . . . 223
CHAPTER 15 Data Science, Random Numbers, and Statistics . . . . . . . . . . . . . . . 239
CHAPTER 16 Counting, Measuring, and Ordering Puzzles . . . . . . . . . . . . . . . . . 259
CHAPTER 17 Graphical and Spatial Puzzles . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 275
CHAPTER 18 Knowledge-Based Questions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 289
CHAPTER 19 Nontechnical Questions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 303
Résumés . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 313
CHAPTER 8
CHAPTER 9
APPENDIX
INDEX . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 333
www.allitebooks.com
Programming Interviews ExposedCODING YOUR WAY THROUGH THE INTERVIEWFourth EditionJohn MonganNoah KindlerEric Giguère
www.allitebooks.com
Programming Interviews Exposed: Coding Your Way Through the Interview, Fourth EditionPublished by John Wiley & Sons, Inc. 10475 Crosspoint Boulevard Indianapolis, IN 46256 www.wiley.comCopyright © 2018 by John Wiley & Sons, Inc., Indianapolis, IndianaPublished by John Wiley & Sons, Inc., Indianapolis, IndianaPublished simultaneously in CanadaISBN: 978-1-119-41847-4ISBN: 978-1-119-41849-8 (ebk)ISBN: 978-1-119-41848-1 (ebk)Manufactured in the United States of America10 9 8 7 6 5 4 3 2 1No 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 pro-motional 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 pub-lisher 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: 2018935416Trademarks: Wiley, the Wiley logo, Wrox, the Wrox logo, Programmer to Programmer, and related trade dress are trade-marks 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.
www.allitebooks.com
To Thuy, the love of my life, who understands me, and Calvin, who lights up my days.—John MonganTo Mikey, Alex, Teddy, and Andy.—Noah KindlerTo my parents, Jean-Claude and Marie-Joëlle, who encouraged and supported my love of programming.—Eric Giguère
www.allitebooks.com
ABOUT THE AUTHORSJOHN 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 tech-nologies. 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.
www.allitebooks.com
ABOUT THE TECHNICAL EDITORSWAYNE 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 program-ming. He also likes leading programmers into the rich and satisfying realm of the theoretical foun-dations of computer science.DAN HILL is a software engineer and software development manager with over 15 years of experi-ence, 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 pro-gramming interviews. He holds BS and MS degrees in computer science from Stanford University.
www.allitebooks.com
PROJECT EDITORAdaobi Obi Tulton TECHNICAL EDITORSWayne Heym and Dan HillPRODUCTION EDITORBarath Kumar RajasekaranCOPY EDITORKimberly A. CoferPRODUCTION MANAGERKatie WisorMANAGER OF CONTENT ENABLEMENT AND OPERATIONSPete GaughanMARKETING MANAGERChristie HilbrichBUSINESS MANAGERAmy KniesEXECUTIVE EDITORJim MinatelPROJECT COORDINATOR, COVERBrent SavagePROOFREADERNancy BellINDEXEREstalita M. SlivoskeyCOVER DESIGNERWileyCOVER IMAGE© Paul Bradbury/Getty ImagesCREDITS