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 Analysis 35
How Big-O Analysis Works 36
Best, Average, and Worst Cases 37
Optimizations and Big-O Analysis 37
How to Do Big-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 Unfl attening 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
