مصاحبه‌های برنامه‌نویسی: سوالات، تحلیل و راه‌حل‌ها

This book is about coding interview questions from software and Internet companies. It covers five key factors which determine performance of candidates: (1) the basics of programming languages, data structures and algorithms, (2) approaches to writing code with high quality, (3) tips to solve difficult problems, (4) methods to optimize code, (5) soft skills required in interviews. The basics of languages, algorithms and data structures are discussed as well as questions that explore how to write robust solutions after breaking down problems into manageable pieces. It also includes examples to focus on modeling and creative problem solving. Interview questions from the most popular companies in the IT industry are taken as examples to illustrate the five factors above. Besides solutions, it contains detailed analysis, how interviewers evaluate solutions, as well as why they like or dislike them. The author makes clever use of the fact that interviewees will have limited time to program meaningful solutions which in turn, limits the options an interviewer has. So the author covers those bases. Readers will improve their interview performance after reading this book. It will be beneficial for them even after they get offers, because its topics, such as approaches to analyzing difficult problems, writing robust code and optimizing, are all essential for high-performing coders. What you’ll learn Necessary knowledge for coding interviews, including programming languages, algorithms and data structures Tips to write complete and robust code Approaches to simplifying and solving difficult problems, with examples, figures and discussion Methods to optimizing memory and space efficiency Tips to demonstrate communication skills and learning skills during interviews Standards in interviewers’ minds to evaluate candidates’ performance Who this book is for Targeted audiences of this book include students who are interested in programming-related careers, as well as developers with less-than-three-year experience who are looking for more career opportunities. Table of Contents 1. Interview Process 2. Programming Languages 3. Data Structures 4. Algorithms 5. High Quality Code 6. Approaches to Solutions 7. Optimization 8. Skills for Interviews 9. Interview Cases Title Page 2 Copyright Page 3 Contents at a Glance 5 Table of Contents 6 About the Author 11 Acknowledgments 12 Introduction 13 Distinguishing Features 13 Summary of Chapters 14 Downloading the Code 14 CHAPTER 1 Interview Process 15 Types of Interviews 15 Phone Interviews 15 Phone-Screen Interviews 16 On-Site Interviews 17 Phases of Interviews 17 Behavior Interview 18 Project Experience 18 Technical Skills 19 “Why Do You Want to Change Your Current Job?” 20 Technical Interview 21 Basic Programming Knowledge 21 Clean, Complete, and Robust Code 22 Clear Thoughts about Solutions 23 Time and Space Efficiency 24 Soft Skills 25 Q/A Time 25 Summary 26 CHAPTER 2 Programming Languages 27 C 27 Palindrome Numbers 30 Converting a Number into a String 30 Composing a Reversed Number 31 C++ 31 C++ Concepts 32 Analyzing Execution of C++ Code 32 Implementing a Class or Member Function in C++ 33 Assignment Operator 33 Classic, but Only Suitable for Newbie Developers 34 Exception Safety 35 C# 36 Singleton 37 Workable Only in Single-Threading Applications 37 Works with Multiple Threads but Is Inefficient 38 Double-Check around Locking 39 Utilization of Static Constructors 40 Creating an Instance When Necessary 40 Solution Comparison 41 Java 41 Java Keywords 41 Data Containers 43 Thread Scheduler 44 Summary 46 CHAPTER 3 Data Structures 47 Arrays 47 Duplication in an Array 48 Search in a 2-D Matrix 51 Binary Search on a Diagonal 52 Removing a Row or a Column at Each Step 54 String 56 Strings in C/C++ 56 Strings in C# 57 Strings in Java 58 Replace Blanks in a String 59 Replace from Left to Right in O(n2) Time 59 Replace from Right to Left in O(n) Time 60 String Matching 63 Linked Lists 67 Print Lists from Tail to Head 68 Sort Lists 70 Loop in List 73 Trees 77 Next Nodes in Binary Trees 78 Binary Search Tree Verification 80 Verify Value Range of Each Node 80 Increasing In-Order Traversal Sequence 81 Stack and Queue 84 Build a Queue with Two Stacks 84 Build a Stack with Two Queues 86 Summary 88 CHAPTER 4 Algorithms 89 Recursion and Iteration 89 Fibonacci Sequence 90 Recursive and Inefficient 90 Iterative Solution with O(n) Time Complexity 91 More Efficient in O(logn) Time 92 Search and Sort 95 Binary Search in Partially Sorted Arrays 98 Majorities in Arrays 101 Based on the Partition Method 102 Based on the Definition of Majority 103 Comparison 104 Backtracking 104 String Path in Matrix 105 Robot Move 107 Dynamic Programming and Greedy Algorithms 108 Edit Distance 109 Minimal Number of Coins for Change 112 Minimal Times of Presses on Keyboards 113 Bit Operations 115 Number of 1s in Binary 116 Check the Rightmost Bit with Endless Loop 116 Left-Shift Operation on 1 116 Minus One and Then Bitwise AND 117 Numbers Occurring Only Once 119 Based on Arithmetic Calculation 121 Based on Bit Operations 122 Summary 123 CHAPTER 5 High-Quality Code 124 Clearness 124 Completeness 125 Test Cases for Completeness 125 Strategies to Handle Errors 126 Power of Integers 127 Incomplete 127 Complete but Inefficient 128 Complete and Efficient 129 Big Numbers as Strings 130 Underestimating Complexity 130 Simulating Increment on a String 131 Simulating Permutation 133 Delete Nodes from a List 136 Partition Numbers in Arrays 140 Workable but Not Scalable 140 Scalable to Handle Similar Scenarios 141 Move Numbers for O(n) Times 143 Move Numbers for O(k) Times 144 Robustness 145 kth Node from End 145 Reverse a List 148 Substructures in Trees 151 Summary 154 CHAPTER 6 Approaches to Solutions 155 Figures to Visualize Problems 155 Mirror of Binary Trees 155 Print Matrix in Spiral Order 158 Clone Complex Lists 161 Examples to Simplify Problems 164 Stack with Min Function 164 With an Auxiliary Stack 165 Without an Auxiliary Stack 167 Push and Pop Sequence of Stacks 169 Print Binary Trees Level by Level 171 Paths in Binary Trees 177 Divide and Conquer 180 Traversal Sequences and Binary Trees 180 Binary Search Trees and Double-Linked Lists 186 Based on Divide and Conquer 187 Based on Node Rotations 189 Permutation and Combination 191 Based on Divide and Conquer 195 Based on Bit Operations 195 Summary 197 CHAPTER 7 Optimization 198 Time Efficiency 198 Median in a Stream 199 Minimum k Numbers 202 O(nlogk) Time Efficiency 202 O(n) Time Efficiency 204 Comparison between the Two Solutions 205 Intersection of Sorted Arrays 205 With O(m+n) Time 206 With O(nlogm) Time 206 Greatest Sum of Sub-Arrays 207 Analyzing Numbers in the Array One by One 208 Dynamic Programming 209 Digit 1 Appears in Sequence from 1 to n 209 Straightforward but Inefficient 210 Based on Divide and Conquer 210 Concatenate an Array to Get a Minimum Number 212 Space-Time Trade-Off 214 Ugly Numbers 215 Check Every Number One by One 215 Store Found Ugly Numbers into an Array 216 Hash Tables for Characters 218 Reversed Pairs in Array 224 First Intersection Node in Two Lists 227 Summary 229 CHAPTER 8 Skills for Interviews 230 Communication and Learning Skills 230 Communications Skills 230 Learning Skills 231 Knowledge Migration Skill 231 Time of Occurrences in a Sorted Array 232 Application of Binary Tree Traversals 234 Visiting Nodes for Multiple Times 237 Visiting Every Node Only Once 237 Sum in Sequences 238 Reversing Words and Rotating Strings 244 Maximum in a Queue 247 Maximum Value in a Queue 248 Saving the Maximum Value into a Queue 248 Mathematical Modeling Skill 252 Probabilities of Dice Points 252 Last Number in a Circle 254 Simulating a Circle with a Looped List 254 Analyzing the Pattern of Deleted Numbers 255 Minimum Number of Moves to Sort Cards 257 Based on Dynamic Programming Costing O(n2) Time 257 Based on Binary Search Costing O(nlogn) Time 258 Most Profit from Stock 260 Based Divide and Conquer 260 Storing the Minimum Numbers while Scanning 262 Divergent Thinking Skills 262 Calculating 1+2+...+n 263 Based on Constructors 263 Based on Virtual Functions 264 Based on Function Pointers 265 Based on Templates 265 Implementation of +, -, *, and / 266 Final/Sealed Classes in C++ 270 Based on Private Constructors 270 Based on Private Constructors 271 Summary 273 CHAPTER 9 Interview Cases 274 Integer Value from a String 274 The Interviewer’s Comments 278 Lowest Common Parent Node in a Tree 280 The Interviewer's Comments 284 Index 286

This book is about coding interview question of software and Internet companies. It covers five key factors which determine performance of candidates: (1) the basics of programming languages, data structures and algorithms, (2) approaches to writing code with high quality, (3) tips to solve difficult problems, (4) methods to optimize code, (5) soft skills required in interviews. The basics of languages, algorithms and data structures are discussed as well as questions that explore how to write robust solutions after breaking down problems into manageable pieces.It also includes examples to focus on modeling and creative problem solving.

Interview questions from the most popular companies in the IT industry are taken as examples to illustrate the five factors above. Besides solutions, it contains detailed analysis, how interviewers evaluate solutions, as well as why they like or dislike them.

Readers will improve their interview performance after reading this book. It will be beneficial for them even after they get offers, because its topics, such as approaches to analyzing difficult problems, writing robust code and optimizing, are all essential for high-performing coders.

What you’ll learn

• Necessary knowledge for coding interviews, including programming languages, algorithms and data structures
• Tips to write complete and robust code
• Approaches to simplifying and solving difficult problems, with examples, figures and discussion
• Methods to optimizing memory and space efficiency
• Tips to demonstrate communication skills and learning skills during interviews
• Standards in interviewers’ minds to evaluate candidates’ performance

Who this book is for

Targeted audiences of this book include students who are interested in programming-related careers, as well as developers with less-than-three-year experience who are looking for more career opportunities.

Table of Contents1. Interview Process

2. Programming Languages

3. Data Structures

4. Algorithms

5. High Quality Code

6. Approaches to Solutions

7. Optimization

8. Skills for Interviews

9. Interview Cases

This book is about coding interview question of software and Internet companies. It covers five key factors which determine performance of candidates: (1) the basics of programming languages, data structures and algorithms, (2) approaches to writing code with high quality, (3) tips to solve difficult problems, (4) methods to optimize code, (5) soft skills required in interviews. The basics of languages, algorithms and data structures are discussed as well as questions that explore how to write robust solutions after breaking down problems into manageable pieces. It also includes examples to focus on modeling and creative problem solving. Interview questions from the most popular companies in the IT industry are taken as examples to illustrate the five factors above. Besides solutions, it contains detailed analysis, how interviewers evaluate solutions, as well as why they like or dislike them. Readers will improve their interview performance after reading this book. It will be beneficial for them even after they get offers, because its topics, such as approaches to analyzing difficult problems, writing robust code and optimizing, are all essential for high-performing coders