CRACKING
-tlie -
CODING INTERVIEW
189 PROGRAMMING QlJESTIONS & SOLUTIONS
CRACKING
tfie
CODING INTERVIEW
6TH EDITION
ALSO BY GAYLE LAAKMANN McDoWELL
CRACKING THE PM INTERVIEW
How TO LAND A PRODUCT MANAGER JOB IN TECHNOLOGY
CRACKING THE TECH CAREER
INSIDER ADVICE ON LANDING A JOB AT GOOGLE, MICROSOFT, ApPLE, OR ANY Top TECH COMPANY
CRACKING
the
CODING INTERVIEW
6th Edition
189 Programming Questions and Solutions
GAYLE LAAKMANN MCDOWELL
Founder and CEO, CareerCup.com
CareerCup, LLC
Palo Alto, CA
CRACKING THE CODING INTERVIEW, SIXTH EDITION
Copyright © 2015 by CareerCup.
All rights reserved. No part of this book may be reproduced in any form by any electronic or me
chanical means, including information storage and retrieval systems, without permission in writing
from the author or publisher, except by a reviewer who may quote brief passages in a review.
Published by CareerCup, LLC, Palo Alto, CA. Compiled Feb 10,2016.
For more information, contact support@careercup.com.
978-0-9847828-5-7 (ISBN 13)
For Davis and Tobin,
and all the things that bring us joy in life.
Introduction
Introduction . ........................................................ 2
I.
The Interview Process ...•. • ... ..... .. . . ... ... ..... .............. • ... 4
Why? .... . ... . .... .. . .. . .. .. .. ......... . ..... ... ........... ... .... 4
How Questions are Selected .. ... .......... .. ........ ..... . .. ........ .... . 6
It's All Relative ... ........ . ......... ............ . ...... ...... ....... .. 7
Frequently Asked Questions ........ . .. ......... . .... ... ...... ........... . 7
II. Behind the Scenes . ...................... . ..... .. .. .... ..... . ....... 8
The Microsoft Interview ... .. ........ .... ....... .... ... . ......... .. ...... 9
The Amazon Interview. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
The Google Interview . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
The Apple Interview . . . .................. . .. ...... . .. . .. . ..... ...... . . 11
The Facebook Interview . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
The Palantir Interview . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
III. Special Situations . ..........................• ... ...... .. .......... 15
Experienced Candidates. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. 15
Testers and SDETs . . ................ . . ...... . ... . ................ . . . .. 15
Product (and Program) Management . .. .... . ... .. ....... . ... ........ ....... 16
Dev Lead and Managers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. 17
Startups . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. 18
Acquisitions and Acquihires . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. 19
For Interviewers .. . ............................ . ..................... 21
IV. Before the Interview .......................... .. ................... 26
Getting the Right Experience ..................................... .. ...... 26
Writing a Great Resume. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27
Preparation Map ............ .. . ...................................... 30
V. Behavioral Questions .............................................. 32
Interview Preparation Grid . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32
Know Your Technical Projects. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33
Responding to Behavioral Questions. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34
So, tell me about yourself... . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36
VI. BigO ............ • ........ • ............ ... . .. ..... .... ........ 38
An Analogy. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38
Time Complexity. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38
Space Complexity. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40
Drop the Constants . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41
Drop the Non-Dominant Terms .... ............. .... . . .. .......... . . . ... . . 42
VI
Cracking the Coding Interview, 6th Edition