目次

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 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: RÉSUMÉS 313 The Technical Résumé 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 Résumé to the Position 329 Sample Résumé 329 INDEX 333