S Sold to Jiaduo He using Selz (#8RLEKRCN) Edition 1 LEETCODE 50 COMMON INTERVIEW QUESTIONS Clean Code Handbook LEETCODE Clean Code Handbook  2014 LeetCode [email protected] 1 CHAPTER 0: FOREWORD ....................................................................................................................... 4 CHAPTER 1: ARRAY/STRING ............................................................................................................... 5 1. TWO SUM .................................................................................................................................................. 5 2. TWO SUM II – INPUT ARRAY IS SORTED ................................................................................................. 6 3. TWO SUM III – DATA STRUCTURE DESIGN ............................................................................................. 8 4. VALID PALINDROME .............................................................................................................................. 10 5. IMPLEMENT STRSTR() ........................................................................................................................... 11 6. REVERSE WORDS IN A STRING ............................................................................................................. 12 7. REVERSE WORDS IN A STRING II .......................................................................................................... 13 8. STRING TO INTEGER (ATOI) ................................................................................................................. 14 9. VALID NUMBER ...................................................................................................................................... 16 10. LONGEST SUBSTRING WITHOUT REPEATING CHARACTERS ........................................................... 19 11. LONGEST SUBSTRING WITH AT MOST TWO DISTINCT CHARACTERS ............................................ 21 12. MISSING RANGES ................................................................................................................................. 23 13. LONGEST PALINDROMIC SUBSTRING ................................................................................................. 24 14. ONE EDIT DISTANCE ........................................................................................................................... 27 15. READ N CHARACTERS GIVEN READ4 ................................................................................................ 29 16. READ N CHARACTERS GIVEN READ4 – CALL MULTIPLE TIMES ...................................................... 30 CHAPTER 2: MATH ............................................................................................................................... 32 17. REVERSE INTEGER .............................................................................................................................. 32 18. PLUS ONE ............................................................................................................................................. 34 19. PALINDROME NUMBER ....................................................................................................................... 35 CHAPTER 3: LINKED LIST .................................................................................................................. 37 20. MERGE TWO SORTED LISTS ............................................................................................................... 37 21. ADD TWO NUMBERS ........................................................................................................................... 38 22. SWAP NODES IN PAIRS ....................................................................................................................... 39 23. MERGE K SORTED LINKED LISTS ....................................................................................................... 40 24. COPY LIST WITH RANDOM POINTER ................................................................................................. 43 CHAPTER 4: BINARY TREE ................................................................................................................ 46 25. VALIDATE BINARY SEARCH TREE ...................................................................................................... 46 26. MAXIMUM DEPTH OF BINARY TREE ................................................................................................. 49 27. MINIMUM DEPTH OF BINARY TREE .................................................................................................. 50 28. BALANCED BINARY TREE ................................................................................................................... 52 29. CONVERT SORTED ARRAY TO BALANCED BINARY SEARCH TREE .................................................. 54 30. CONVERT SORTED LIST TO BALANCED BINARY SEARCH TREE ....................................................... 56 31. BINARY TREE MAXIMUM PATH SUM ................................................................................................. 58 32. BINARY TREE UPSIDE DOWN ............................................................................................................. 60 CHAPTER 5: BIT MANIPULATION ................................................................................................... 62 33. SINGLE NUMBER .................................................................................................................................. 62 34. SINGLE NUMBER II .............................................................................................................................. 64 CHAPTER 6: MISC .................................................................................................................................. 66 2 35. SPIRAL MATRIX ................................................................................................................................... 66 36. INTEGER TO ROMAN ........................................................................................................................... 68 37. ROMAN TO INTEGER ........................................................................................................................... 70 38. CLONE GRAPH ...................................................................................................................................... 72 CHAPTER 7: STACK .............................................................................................................................. 74 39. MIN STACK .......................................................................................................................................... 74 40. EVALUATE REVERSE POLISH NOTATION .......................................................................................... 76 41. VALID PARENTHESES .......................................................................................................................... 80 CHAPTER 8: DYNAMIC PROGRAMMING ........................................................................................ 81 42. CLIMBING STAIRS ................................................................................................................................ 81 43. UNIQUE PATHS .................................................................................................................................... 83 44. UNIQUE PATHS II ................................................................................................................................ 86 45. MAXIMUM SUM SUBARRAY ................................................................................................................ 87 46. MAXIMUM PRODUCT SUBARRAY ....................................................................................................... 89 47. COINS IN A LINE ................................................................................................................................... 90 CHAPTER 9: BINARY SEARCH ........................................................................................................... 95 48. SEARCH INSERT POSITION ................................................................................................................. 95 49. FIND MINIMUM IN SORTED ROTATED ARRAY .................................................................................. 97 50. FIND MINIMUM IN ROTATED SORTED ARRAY II – WITH DUPLICATES ........................................... 99 3 Chapter 0: Foreword Hi, fellow LeetCoders: First, I would like to express thank you for buying this eBook: “Clean Code Handbook: 50 Common Interview Questions”. As the title suggested, this is the definitive guide to write clean and concise code for interview questions. You will learn how to write clean code. Then, you will ace the coding interviews. This eBook is written to serve as the perfect companion for LeetCode Online Judge (OJ). Each problem has a “Code it now” link that redirects to the OJ problem statement page. You can write the code and submit it to the OJ system, which you will get immediate feedback on whether your solution is correct. If the “Code it now” link says “Coming soon”, it means the problem will be added very soon in the future, so stay tuned. On the top right side of each problem are the Difficulty and Frequency ratings. There are three levels of difficulty: Easy, Medium, and Hard. Easy problems are problems that are easy to come up with ideas and the implementation should be pretty straightforward. Most interview questions fall into this level of difficulty. On the other end, there are hard problems. Hard problems are usually algorithmic in nature and require more thoughts beforehand. There could be some coding questions that fall into Hard, but that is rare. There are three frequency rating: Low, Medium, and High. The frequency of a problem being asked in a real interview is based on data collected from the user survey: “Have you met this question in a real interview?” This should give you an idea of what kind of questions is currently being asked in real interviews. Each question may contain a section called “Example Questions Candidate Might Ask”. These are examples of good questions to ask your interviewer. Asking clarifying questions is important and is a good chance to demonstrate your thought process. Each question is accompanied with as many approaches as possible. Each approach begins with a runtime and space complexity summary so you can quickly compare between different approaches. The analysis of the runtime and space complexity is usually provided along with the solution. Analyzing complexity is frequently being asked in a technical interview, so you should definitely prepare for it. You learn best when you solve a problem by yourself. If you get stuck, there are usually hints in the book to help you. If you are still stuck, read the analysis and try to write the code yourself in the Online Judge Even though you might think a problem is easy, writing code that is concise and clean is not as easy as most people think. For example, if you are writing more than 30 lines of code during a coding interview, your code is probably not concise enough. Most code in this eBook fall between 20 — 30 lines of code. 1337c0d3r 4 Chapter 1: Array/String 1. Two Sum Code it now: https://oj.leetcode.com/problems/two-sum/ Difficulty: Easy, Frequency: High Question: Given an array of integers, find two numbers such that they add up to a specific target number. The function twoSum should return indices of the two numbers such that they add up to the target, where index1 must be less than index2. Please note that your returned answers (both index1 and index2) are not zero-based. You may assume that each input would have exactly one solution. Solution: O(n2) runtime, O(1) space – Brute force: The brute force approach is simple. Loop through each element x and find if there is another value that equals to target – x. As finding another value requires looping through the rest of array, its runtime complexity is O(n2). O(n) runtime, O(n) space – Hash table: We could reduce the runtime complexity of looking up a value to O(1) using a hash map that maps a value to its index. public int[] twoSum(int[] numbers, int target) { Map<Integer, Integer> map = new HashMap<>(); for (int i = 0; i < numbers.length; i++) { int x = numbers[i]; if (map.containsKey(target - x)) { return new int[] { map.get(target - x) + 1, i + 1 }; } map.put(x, i); } throw new IllegalArgumentException("No two sum solution"); } Follow up: What if the given input is already sorted in ascending order? See Question [2. Two Sum II – Input array is sorted]. 5 2. Two Sum II – Input array is sorted Code it now: Coming soon! Difficulty: Medium, Frequency: N/A Question: Similar to Question [1. Two Sum], except that the input array is already sorted in ascending order. Solution: Of course we could still apply the [Hash table] approach, but it costs us O(n) extra space, plus it does not make use of the fact that the input is already sorted. O(n log n) runtime, O(1) space – Binary search: For each element x, we could look up if target – x exists in O(log n) time by applying binary search over the sorted array. Total runtime complexity is O(n log n). public int[] twoSum(int[] numbers, int target) { // Assume input is already sorted. for (int i = 0; i < numbers.length; i++) { int j = bsearch(numbers, target - numbers[i], i + 1); if (j != -1) { return new int[] { i + 1, j + 1 }; } } throw new IllegalArgumentException("No two sum solution"); } private int bsearch(int[] A, int key, int start) { int L = start, R = A.length - 1; while (L < R) { int M = (L + R) / 2; if (A[M] < key) { L = M + 1; } else { R = M; } } return (L == R && A[L] == key) ? L : -1; } O(n) runtime, O(1) space – Two pointers: Let’s assume we have two indices pointing to the ith and jth elements, A and A i j respectively. The sum of A and A could only fall into one of these three possibilities: i j i. A + A > target. Increasing i isn’t going to help us, as it makes the sum even i j bigger. Therefore we should decrement j. ii. A + A < target. Decreasing j isn’t going to help us, as it makes the sum even i j smaller. Therefore we should increment i. iii. A + A == target. We have found the answer. i j 6 public int[] twoSum(int[] numbers, int target) { // Assume input is already sorted. int i = 0, j = numbers.length - 1; while (i < j) { int sum = numbers[i] + numbers[j]; if (sum < target) { i++; } else if (sum > target) { j--; } else { return new int[] { i + 1, j + 1 }; } } throw new IllegalArgumentException("No two sum solution"); } 7 3. Two Sum III – Data structure design Code it now: Coming soon! Difficulty: Easy, Frequency: N/A Question: Design and implement a TwoSum class. It should support the following operations: add and find. add(input) – Add the number input to an internal data structure. find(value) – Find if there exists any pair of numbers which sum is equal to the value. For example, add(1); add(3); add(5); find(4)  true; find(7)  false Solution: add – O(n) runtime, find – O(1) runtime, O(n2) space – Store pair sums in hash table: We could store all possible pair sums into a hash table. The extra space needed is in the order of O(n2). You would also need an extra O(n) space to store the list of added numbers. Each add operation essentially go through the list and form new pair sums that go into the hash table. The find operation involves a single hash table lookup in O(1) runtime. This method is useful if the number of find operations far exceeds the number of add operations. add – O(log n) runtime, find – O(n) runtime, O(n) space – Binary search + Two pointers: Maintain a sorted array of numbers. Each add operation would need O(log n) time to insert it at the correct position using a modified binary search (See Question [48. Search Insert Position]). For find operation we could then apply the [Two pointers] approach in O(n) runtime. add – O(1) runtime, find – O(n) runtime, O(n) space – Store input in hash table: A simpler approach is to store each input into a hash table. To find if a pair sum exists, just iterate through the hash table in O(n) runtime. Make sure you are able to handle duplicates correctly. 8 public class TwoSum { private Map<Integer, Integer> table = new HashMap<>(); public void add(int input) { int count = table.containsKey(input) ? table.get(input) : 0; table.put(input, count + 1); } public boolean find(int val) { for (Map.Entry<Integer, Integer> entry : table.entrySet()) { int num = entry.getKey(); int y = val - num; if (y == num) { // For duplicates, ensure there are at least two individual numbers. if (entry.getValue() >= 2) return true; } else if (table.containsKey(y)) { return true; } } return false; } } 9