Preface xxv

Introduction xxix

Chapter 1: Before the Search 1

Know Yourself 1

Know the Market 3

Basic Market Information 3

What About Outsourcing? 4

Develop Marketable Skills 5

Get Things Done 6

Manage Your Online Profile 7

Summary 8

Chapter 2: the Job Application Process 9

Finding and Contacting Companies 9

Finding Companies 9

Getting Referrals 10

Working with Headhunters 10

Contacting the Company Directly 11

Job Fairs 12

Technology-Driven Sites 12

The Interview Process 12

Screening Interviews 12

On-Site Interviews 13

Dress 14

A Recruiter’s Role 14

Offers and Negotiation 15

Dealing with Recruiter Pressures 15

Negotiating Your Salary 15

Accepting and Rejecting Offers 17

Summary 17

Chapter 3: the Phone Screen 19

Understanding Phone Screens 19

Phone Screens by Software Engineers 19

Phone Screens by Nontechnical People 20

How to Take a Phone Screen 21

Phone Screen Problems 22

Memory Allocation in c 22

Recursion Trade-Offs 22

Mobile Programming 23

FizzBuzz 23

Reversing a String 24

Removing Duplicates 25

Nested Parentheses 26

Summary 27

Chapter 4: Approaches to Programming Problems 29

The Process 29

The Scenario 29

The Problems 30

Which Languages to Use 30

Interactivity Is Key 31

Solving the Problems 32

The Basic Steps 32

When You Get Stuck 34

Analyzing Your Solution 34

Big-O O Analysis 35

How Big-O O Analysis Works 36

Best, Average, and Worst Cases 37

Optimizations and Big-O O Analysis 37

How to Do Big-O O Analysis 38

Which Algorithm Is Better? 38

Memory Footprint Analysis 39

Summary 40

Chapter 5: Linked Lists 41

Why Linked Lists? 41

Kinds of Linked Lists 42

Singly Linked Lists 42

Doubly Linked Lists 44

Circular Linked Lists 44

Basic Linked List Operations 44

Tracking the Head Element 44

Traversing a List 46

Inserting and Deleting Elements 46

Linked List Problems 48

Stack Implementation 48

Maintain Linked List Tail Pointer 54

Bugs in removeHead 60

Mth-to-Last Element of a Linked List 62

List Flattening 65

List Unflattening 68

Null or Cycle 70

Summary 73

Chapter 6: Trees and Graphs 75

Trees 75

Binary Trees 77

Binary Search Trees 78

Heaps 80

Common Searches 80

Breadth-First Search 80

Depth-First Search 81

Traversals 81

Graphs 82

Tree and Graph Problems 83

Height of a Tree 83

Preorder Traversal 84

Preorder Traversal, No Recursion 85

Lowest Common Ancestor 87

Binary Tree to Heap 88

Unbalanced Binary Search Tree 91

Six Degrees of Kevin Bacon 93

Summary 97

Chapter 7: Arrays and Strings 99

Arrays 99

C and C++ 100

Java 101

C# 102

JavaScript 102

Strings 102

C 103

C++ 104

Java 104

C# 105

JavaScript 105

Array and String Problems 105

Find the First Nonrepeated Character 106

Remove Specified Characters 109

Reverse Words 112

Integer/String Conversions 116

From String to Integer 116

From Integer to String 118

UTF-8 String Validation 121

Summary 124

Chapter 8: Recursion 125

Understanding Recursion 125

Recursion Problems 129

Binary Search 129

Permutations of a String 131

Combinations of a String 134

Telephone Words 137

Summary 142

Chapter 9: Sorting 143

Sorting Algorithms 143

Selection Sort 144

Insertion Sort 145

Quicksort 146

Merge Sort 148

Sorting Problems 149

The Best Sorting Algorithm 150

Stable Selection Sort 153

Multi-Key Sort 155

Make a Sort Stable 156

Optimized Quicksort 158

Pancake Sorting 161

Summary 163

Chapter 10: Concurrency 165

Basic Thread Concepts 165

Threads 165

System Threads versus User Threads 166

Monitors and Semaphores 166

Deadlocks 167

A Threading Example 168

Concurrency Problems 170

Busy Waiting 170

Producer/Consumer 172

The Dining Philosophers 175

Summary 179

Chapter 11: Object-oriented Programming 181

Fundamentals 181

Classes and Objects 181

Construction and Destruction 182

Inheritance and Polymorphism 183

Object-Oriented Programming Problems 184

Interfaces and Abstract Classes 184

Virtual Methods 186

Multiple Inheritance 188

Resource Management 189

Summary 191

Chapter 12: Design Patterns 193

What Are Design Patterns? 193

Why Use Design Patterns? 193

Design Patterns in Interviews 194

Common Design Patterns 194

Singleton 195

Builder 195

Iterator 197

Observer 197

Decorator 197

Design Pattern Problems 198

Singleton Implementation 198

Decorator versus Inheritance 201

Efficient Observer Updates 202

Summary 202

Chapter 13: Databases 203

Database Fundamentals 203

Relational Databases 203

SQL 204

NoSQL 208

Object Databases 209

Hybrid Key-Value/Column Databases 209

Database Transactions 210

Distributed Databases 211

Database Problems 212

Simple SQL 212

Company and Employee Database 212

Max, No Aggregates 215

Three-Valued Logic 216

School Schemata 218

Summary 222

Chapter 14: Graphics and Bit Manipulation 223

Graphics 223

Bit Manipulation 224

Binary Two’s Complement Notation 224

Bitwise Operators 225

Optimizing with Shifts 226

Graphics Problems 226

Eighth of a Circle 227

Rectangle Overlap 229

Bit Manipulation Problems 232

Big-Endian or Little-Endian 233

Number of Ones 235

Summary 237

Chapter 15: Data Science, Random Numbers, And Statistics 239

Probability and Statistics 240

Descriptive and Inferential Statistics 241

Confidence Intervals 242

Statistical Tests 242

Artificial Intelligence and Machine Learning 244

Random Number Generators 245

Data Science, Random Number and Statistical Problems 246

Irreproducible Results 247

Study More; Know Less 249

Roll the Dice 251

Calculate Pi 254

Summary 258

Chapter 16: Counting, Measuring, and Ordering Puzzles 259

Tackling Brainteasers 259

Beware of Assumptions 260

Don’t Be Intimidated 261

Beware of Simple Problems 262

Estimation Problems 262

Brainteaser Problems 263

Count Open Lockers 263

Three Switches 265

Bridge Crossing 266

Heavy Marble 269

Number of American Gas Stations 273

Summary 274

Chapter 17: Graphical and Spatial Puzzles 275

Draw It First 275

Graphical and Spatial Problems 276

Boat and Pier 276

Counting Cubes 278

The Fox and the Duck 282

Burning Fuses 283

Escaping the Train 286

Summary 287

Chapter 18: Knowledge-based Questions 289

Preparation 289

Problems 290

C++ versus Java 291

Friend Classes 292

Argument Passing 292

Macros and Inline Functions 294

Inheritance 295

Garbage Collection 296

32-Bit versus 64-Bit Applications 297

Network Performance 298

Web Application Security 298

Cryptography 301

Hash Tables versus Binary Search Trees 301

MapReduce 302

Summary 302

Chapter 19: Nontechnical Questions 303

Why Nontechnical Questions? 303

Questions 304

“What Do You Want to Do?” 304

“What Is Your Favorite Programming Language?” 305

“What Is Your Work Style?” 306

“What Can You Tell Me About Your Experience?” 306

“What Are Your Career Goals?” 306

“Why Are You Looking to Change Jobs?” 306

“What Salary Are You Expecting?” 307

“What Is Your Salary History?” 310

“Why Should We Hire You?” 310

“Why Do You Want to Work for This Company?” 311

“Do You Have Any Questions for Me?” 311

Summary 311

Appendix: Resumes 313

The Technical Resume 313

A Poor Example 313

Sell Yourself 317

Keep It Short 317

List the Right Information 318

Be Clear and Concise 319

Relevant Information Only 320

Use Reverse Chronological Ordering 321

Always Proofread 321

An Improved Example 321

Managers and Senior Developers 323

Tailor the Resume to the Position 329

Sample Resume 329

Index 333