CRACKING THE
             CODING
             I NTERVIEW
                150 Programming Interview 
                 Questions and Solutions
               GAYLE LAAKMANN
               Founder and CEO, CareerCup.com
                        CareerCup, LLC
                          Seattle, WA
     CRACKING THE CODING INTERVIEW, FOURTH EDITION
     Copyright © 2008 - 2010 by Gayle Laakmann.  All rights reserved.
     Published by CareerCup, LLC, Seattle, WA.  Version 3.21090410302210.
     Visit our website at: www.careercup.com.  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 reviews.
     For more information, contact support@careercup.com.
     Printed in United States of America
            978-1-450-59320-5 9781450593205  (ISBN 13)
                                   
                Behind the Scenes                                                                                                                            7
                    The Microsoft Interview                                                                                                                            8
                    The Amazon Interview                                                                                                                            9
                    The Google 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                                                                                                             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                                                                                                                 53
                    Concepts and Algorithms                                                                                                  56
                    Chapter 5 |  Bit Manipulation                                                                                                                 57
                    Chapter 6 |  Brain Teasers                                                                                                                        59
                     1        Cracking the Coding Interview
                                                                                                                      
                    Chapter 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++                                                                                                                                       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 
                                                                                                                                                                                301
                Mock Interviews                                                                                                                              303
                About the Author                                                                                                                         304
                                                                                                          CareerCup com             2