CRACKING

the

CODING INTERVIEW
189 PROGRAMMING QUESTIONS & SOLUTIONS

GAYLE L A A K M A N N MCDOWELL 6TH

Author of Cracking the PM Interview and Cracking the Tech Career
 CRACKING
the

CODING INTERVIEW
G T H EDITION
 A L S O BY GAYLE L A A K M A N N M C D O W E L L

CRACKING THE P M INTERVIEW

H o w TO L A N D A PRODUCT MANAGER JOB IN TECHNOLOGY

CRACKING THE T E C H CAREER

INSIDER ADVICE ON LANDING A JOB AT GOOGLE, MICROSOFT, APPLE, OR A N Y TOP TECH COMPANY
 CRACKING

CODING INTERVIEW
6th Edition
189 Programming Questions and Solutions

GAYLE LAAKMANN MCDOWELL

Founder and CEO, CareerCup.com

CareerCup, LLC
Palo Alto, CA
C R A C K I N G T H E C O D I N G INTERVIEW, SIXTH E D I T I O N

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)®caieercup.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

KnowYour Technical Projects 33

Responding to Behavioral Questions 34

So, tell me aboutyourself. 36

VI. BigO 38

An Analogy 38

Time Complexity 38

Space Complexity 40

Drop the Constants 41

Drop the Non-Dominant Terms 42

VIM Cracking the Coding Interview, 6th Edition

 Introduction

Multi-Part Algorithms: Add vs. Multiply 42

Amortized Time 43

Log N Runtimes 44

Recursive Runtimes 44

Examples and Exercises 45

Vlt. Technical Questions 60

How to Prepare 60

What You Need To Know 60

Walking Through a Problem 62

Optimize & Solve Technique #1: Look for BUD 67

Optimize & Solve Technique #2: DfY (Do It Yourself) 69

Optimizes Solve Technique #3: Simplify and Generalize 71

Optimized Solve Technique #4: Base Case and Build 71

Optimize & Solve Technique #5: Data Structure Brainstorm 72

Best Conceivable Runtime (BCR) 72

Handling Incorrect Answers 76

When You've Heard a Question Before 76

The "Perfect" Language for Interviews 76

What Good Coding Looks Like 77

Don't Give Up! 81

VIII. The Offer and Beyond 82

Handling Offers and Rejection 82

Evaluating the Offer 83

Negotiation 84

On the Job 85

IX. Interview Questions 87

Data Structures 88

Chapter 1 | Arrays and Strings 88

Hash Tables 88

ArrayList & Resizable Arrays 89

StringBuilder 89

Chapter 2 I Linked Lists 92

Creating a Linked List 92

Deleting a Node from a Singly Linked List 93

The "Runner" Technique 93

Recursive Problems 93

CrackingTheCodinglnterview.com 16th Edition VII

Introduction

Chapter 3 j Stacks and Queues 96

Implementing a Stack 96

Implementing a Queue 97
Chapter 4 | Trees and Graphs 100

Types of Trees 100

Binary Tree Traversal 103

Binary Heaps (Min-Heaps and Max-Heaps) 103

Tries (Prefix Trees) 105

Graphs 105

Graph Search 107

Concepts and Algorithms 112

Chapter 5 j Bit Manipulation 112

Bit Manipulation By Hand 112

Bit Facts and Tricks 112

Two's Complement and Negative Numbers 113

Arithmetic vs. Logical Right Shift 113

Common Bit Tasks: Getting and Setting 114

Chapter 6 j Math and Logic Puzzles 117

Prime Numbers 117

Probability 119

Start Talking 121

Develop Rules and Patterns 121

Worst Case Shifting 122

Algorithm Approaches 122

Chapter 7 | Object-Oriented Design 125

How to Approach 125

Design Patterns 126

Chapter 81 Recursion and Dynamic Programming 130

How to Approach 130

Recursive vs. Iterative Solutions 131

Dynamic Programming & Memoization 131

Chapter 9 | System Design and Scalability 137

Handling the Questions 137

Design: Step-By-Step 13S

Algorithms that Scale: Step-By-Step 139

KeyConcepts 140

VIM Cracking the Coding Interview, 6th Edition