FOURTH CRACKING THE EDITION C O D I N G Gayle Laakmann

1 Gayle LAAKMANNC A R E E R C U P. CO MCRACKING THE coding INTERVIEWNow in the 4th EDITION , CRACKING the coding Interview gives you the interview prepara-tion you need to get the top software developer jobs This book provides: 150 Programming Interview Questions and Solutions From binary trees to binary search, this list of 150 questions includes the most common and most useful questions in data structures, algorithms, and knowledge based questions Five Proven Approaches to Solving Tough Algorithm QuestionsUsing these fi ve approaches to solving algorithm questions, you can conquer tough interview questions and impress your interviewer Ten Mistakes Candidates Make -- And How to Avoid ThemDon t lose your dream job by making these common mistakes Learn what many candidates do wrong, and how to avoid these issues Steps to Prepare for Behavioral and Technical QuestionsStop meandering through an endless set of questions, while missing some of the most important preparation techniques Follow these steps to more thoroughly prepare in less time Interview War Stories.

2 A View from the Interviewer s SideHumorous but instructive stories from our interviewers show you how some can-didates really fl opped on the most important question - and how you can avoid doing the same Gayle Laakmann founded CareerCup com in 2005 to provide technical interview coaching for software engineers As a Software Engineer at Microsoft, Apple and Google, she interviewed over one hundred and twenty applicants in three countries She holds Bachelor s and Master s degrees in Computer Science from the University of Penn-sylvania G AY L E L A A K M A N NFounder and CEO, programming interview questions and solutions Plus: Five proven approaches to solving tough algorithm questions Ten mistakes candidates make -- and how to avoid them Steps to prepare for behavioral and technical questions Interviewer war stories: a view from the interviewer s sideFOURTHEDITIONCRACKING THEC O D I N GI N T E R V I E WCRACKING THECODINGINTERVIEWCRACKING THEC O D I N GI N T E R V I E W150 Programming Interview Questions and SolutionsG AY L E L A A K M A N NFounder and CEO, , LLCS eattle, WACRACKING THE coding INTERVIEW, FOURTH EDITIONC opyright 2008 - 2010 by Gayle Laakmann .

3 All rights by CareerCup, LLC, Seattle, WA. Version our website at: No part of this book may be used or repro-duced in any manner without written permission except in the case of brief quota-tions in critical articles or more information, contact in United States of America978-1-450-59320-5 9781450593205 (ISBN 13) CRACKING the coding Interview1 Table of ContentsForeword 4 Introduction 5 Behind the Scenes 7 The Microsoft Interview 8 The Amazon Interview 9 The Google

4 Interview 10 The Apple Interview 11 The Yahoo Interview 12 Interview War Stories 13 Before the Interview 20 Resume advice 21 Behavioral Preparation 23 Technical Preparation 25 The Interview and Beyond 28 Handling Behavioral Questions 29 Handling Technical Questions

5 31 Five Algorithm Approaches 34 The Offer and Beyond 37 Top Ten Mistakes Candidates Make 39 Frequently Asked Questions 41 Interview Questions 44 Data Structures 46 Chapter 1 | Arrays and Strings 47 Chapter 2 | Linked Lists 49 Chapter 3 | Stacks and Queues 51 Chapter 4 | Trees and Graphs

6 53 Concepts and Algorithms 56 Chapter 5 | Bit Manipulation 57 Chapter 6 | Brain Teasers 592 CareerCup comTable of ContentsChapter 7 | Object Oriented Design 61 Chapter 8 | Recursion 63 Chapter 9 | Sorting and Searching 65 Chapter 10 | Mathematical 67 Chapter 11 | Testing 69 Chapter 12 | System Design and Memory Limits 71 Knowledge Based 74 Chapter 13 | C++

7 75 Chapter 14 | Java 77 Chapter 15 | Databases 79 Chapter 16 | Low Level 81 Chapter 17 | Networking 83 Chapter 18 | Threads and Locks 85 Additional Review Problems 88 Chapter 19 | Moderate 89 Chapter 20 | Hard 91 Solutions 94 Index

8 301 Mock Interviews 303 About the Author 3044 CareerCup comForewordDear Readers,Welcome to the 4th EDITION of CRACKING the coding Interview This volume updates the 3rd EDITION with new content and refreshed information Be sure to check out our website, www careercup com, to connect with other candidates and to discover new resources For those of you new to technical interviews, the process can seem overwhelming Inter-viewers throw questions at you, expect you to whip up brilliant algorithms on the spot, and then ask you to write beautiful code on a whiteboard Luckily, everyone else is in the same boat, and you re already working hard to prepare Good job!

9 As you get ready for your interviews, consider these suggestions: Write Code on Paper: Most interviewers won t give you a computer and will instead expect you to write code on a whiteboard or on paper To simulate this environment, try answering interview problems by writing code on paper first, and then typing them into a computer as-is Whiteboard / paper coding is a special skill, which can be mastered with constant practice Know Your Resume: While technical skills are extremely important, that s no reason to neglect your own resume Make sure to prepare yourself to give a quick summary of any project or job you were involved with, and to discuss the hardest and most interesting problems you encountered along the day Don t Memorize Solutions: While this book offers a representative sample of interview questions, there are still thousands of interview questions out there Memorizing solu-tions is not a great use of your time Rather, use this book to explore approaches to problems, to learn new concepts, and to practice your skills Talk Out Loud: Interviewers want to understand how you think and approach prob-lems, so talk out loud while you re solving problems Let the interviewer see how you re tackling the problem, and they just might guide you as well And remember -- interviews are hard!

10 In my years of interviewing at Google, I saw some interviewers ask easy questions while others ask harder questions But you know what? Getting the easy questions doesn t make it any easier to get the offer Receiving an offer is not about solving questions flawlessly (very few candidates do!), but rather, it is about answering questions bett