coding_prep

A collection of coding interview problems with my solutions. From various sources including Leet-Code, Interview experiences etc. List of questions at the end of this readme file. #100DaysOfCode

---

Other Resources:

1. TopCoder Blog - GitHub Repositories With Competitive Programming Libraries [link]
2. Problem Solving with Algorithms and Data Structures using Python [link]
3. RosettaCode [link]
4. Problem Solving with Algorithms and Data Structures using C++ [link]
5. Algs4cs Princeton [link]
6. Union Find - HackerEarth [link]
7. Teach Yourself CS [link]
8. LeetCode Patterns [link]

---

Common Patterns

Arrays/Lists/Strings:

• Two pointers (left/right, slow/fast)
• Ordered Dictionaries in Python (LRU Cache, LFU Cache)
• Zero Sum Clique Reduction (Optimal Account Balancing, Minimum Cash Flow)
• Merge Intervals, Insert Interval (based on Sorting)
• Largest Number (Custom Comparator operator, Python's map function)
• Implement strStr() (Two pointers, Rabin Karp: Rolling Hash)
• Game of Life

Trie / Prefix Search

• Add and Search Word

Stacks & Queues:

• Design Snake Game (Queues)
• Remove K Digits (Stacks and Greedy algorithm)
• Simplify Path (Stacks)
• Decode String
• Moving Average from Data Stream (Queue)

Backtracking:

• Letter Combinations of a Phone Number
• Word Search
• Add and Search Word - Data structure design
• Permutations II
• Palindrome Partitioning
• Restore IP Addresses

Dynamic Programming

• Bomb Enemy
• Coin Change

Greedy Approach

• Wiggle Subsequence
• Remove K Digits

Ad Hoc:

• Fraction to Recurring Decimal
• Integer to English Word
• Spiral Matrix (yield keyword, generator perspective)

Graphs/Trees:

• DFS (Iterative and Recursive) / O(V+E)
  • Clone Graph (recursive)
  • Coin Change
  • Detect Cycle in a directed graph / Course Schedule
  • Distribute Coins in a Binary Tree
  • Pacific Atlantic Water Flow
  • Robot Room Cleaner
• BFS (Iterative and Recursive)
  • Surrounded Regions
  • Word Ladder (Bi-directional BFS)
  • Optimal Account Balancing
  • Clone Graph (iterative)
  • Binary Tree Level Order Traversal
  • Populating Next Right Pointers in Each Node
• Inorder Traversal (Iterative and Recursive)
• Preorder Traversal (Iterative and Recursive)
• Postorder Traversal (Iterative and Recursive)
• Kosaraju's Algorithm for Strongly Connected Components
• Union-Find Algorithm for Cycle Detection in Undirected Graphs
• Cycle detection in directed graphs using Colors / DFS stack
• Bridges in a graph
• Prim's Algorithm, Kruskal Algorithm: Minimum spanning tree
• Dijkstra's Algorithm - Shortest path from origin to every other node in graph / Greedy / O(ELogV) / only non-negative weights
• Bellman Ford Algorithm - Shortest path from origin to every other node in graph / DP / O(VE)
• Topological Sort for a directed graph
  • Alien Dictionary
• Floyd Warshall Algorithm - All pairs shortest path
• Kirchhoff’s Theorem - Calculating number of Spanning trees Of a Graph

Python

• List Comprehensions (Bomb Enemy, Permutations II)
• zip(*(grid)) generator for transpose (Bomb Enemy, Alien Dictionary)
• Iterators / Ordered Dict (LRU Cache)
• Generator objects
• xor (^) (Adding Two Numbers, Fraction Recurring Decimal, Single Number_2)
• heapq package (Employee Free Time, Kth Largest Element)
• bisect package - helps with binary search (Reverse Pairs, Three Sum, Longest Increasing Subsequence, Find First and Last Position of Element in Sorted Array)
• reverse a list a[::-1]
• zip function (Compare Version Numbers)
• @lru_cache in functools (Minimum cost for tickets)

C++

• Shortforms [link]

---

List of Questions

1. LeetCode (Medium) - Design Tic Tac Toe [link]
2. LeetCode (Medium) - Longest substring without repeating characters [link]
3. Codility (Hard) - Tree Trip [link]
4. LeetCode (Medium) - Add Two Numbers [link]
5. LeetCode (Hard) - Median of Two Sorted Arrays [link]
6. LeetCode (Medium) - Three Sum [link]
7. LeetCode(Medium) - Set Matrix Zeroes [link]
8. LeetCode (Medium) - Group Anagrams [link]
9. LeetCode (Medium) - Longest Palindromic Substring [link] (Manacher's Algorithm)
10. LeetCode (Medium) - Increasing Triplet Subsequence [link]
11. LeetCode (Medium) - Missing Ranges [link]
12. LeetCode (Easy) - Reverse LinkedList [link]
13. LeetCode (Hard) - Reverse LinkedList in k groups [link]
14. LeetCode (Easy) - Sqrt [link]
15. LeetCode (Easy) - Rectangle Overlap [link]
16. LeetCode (Hard) - Interleaving String [link]
17. LeetCode (Medium) - Merge Intervals [link]
18. LeetCode (Medium) - Generate Parentheses [link]
19. LeetCode (Hard) - LRU Cache [link]
20. LeetCode (Medium) - Search in Rotated Sorted Array [link]
21. LeetCode (Medium) - Rotate Image [link]
22. LeetCode (Easy) - Maximum Subarray [link]
23. LeetCode (Easy) - Two Sum [link]
24. LeetCode (Medium) - Kth Largest Element in an Array [link]
25. LeetCode (Medium) - UTF-8 Validation [link]
26. LeetCode (Easy) - Count Primes [link]
27. LeetCode (Easy) - Climbing Stairs [link]
28. LeetCode (Hard) - Maximal Rectangle [link]
29. LeetCode (Medium) - Product of Array Except Self [link]
30. LeetCode (Easy) - Sum of Two Numbers [link]
31. LeetCode (Medium) - Validate Binary Search Tree [link]
32. LeetCode (Easy) - Add Strings [link]
33. LeetCode (Hard) - Trapping Rain Water [link]
34. LeetCode (Medium) - Number of Islands [link]
35. LeetCode (Medium) - Reverse Words in a String [link]
36. LeetCode (Medium) - Binary Tree Zigzag Level Order Traversal [link]
37. LeetCode (Medium) - WordBreak [link]
38. LeetCode (Hard) - WordBreak II [link]
39. LeetCode (Hard) - Concatenated Words [link]
40. LeetCode (Medium) - Partition Equal Subset Sum [link]
41. LeetCode (Medium) - Partition to K Equal Sum Subset [link] #TODO
42. LeetCode (Easy) - Reverse Bits [link]
43. LeetCode (Medium) - Subsets [link]
44. LeetCode (Easy) - Single Number [link]
45. LeetCode (Medium) - Single Number II [link]
46. LeetCode (Easy) - Move Zeroes [link]
47. LeetCode (Easy) - Add Binary Numbers [link]
48. LeetCode (Easy) - Intersection of Two Arrays II [link]
49. LeetCode (Easy) - Valid Palindrome [link]
50. LeetCode (Easy) - Valid Palindrome II [link]
51. LeetCode (Medium) - ZigZag Conversion [link]
52. LeetCode (Easy) - Palindrome Number [link]
53. LeetCode (Hard) - Regular Expression Matching [link]
54. LeetCode (Medium) - Container with Most Water [link]
55. LeetCode (Easy) - Roman to Integer [link]
56. LeetCode (Easy) - Longest Common Prefix [link]
57. LeetCode (Medium) - Interval List Intersections [link]
58. LeetCode (Easy) - Squares of a Sorted Array [link]
59. LeetCode (Easy) - K Closest points to the origin [link]
60. LeetCode (Medium) - Shortest Bridge [link]
61. LeetCode (Medium) - Random Pick with Weight [link]
62. LeetCode (Hard) - Consecutive Numbers Sum [link]
63. LeetCode (Hard) - Bus Routes [link]
64. LeetCode (Hard) - Reaching Points [link]
65. LeetCode (Easy) - Construct Quad Tree [link]
66. LeetCode (Hard) - Serialize and Deserialize N-ary Tree [link]
67. LeetCode (Hard) - Employee Free Time [link]
68. LeetCode (Hard) - Cherry Pickup [link]
69. LeetCode (Medium) - Max Area of Island [link]
70. LeetCode (Hard) - 24 Game [link]
71. LeetCode (Medium) - Find K Closest Elements [link]
72. LeetCode (Medium) - Print Binary Tree [link]
73. LeetCode (Medium) - Exclusive Time of Functions [link]
74. LeetCode (Medium) - Task Scheduler [link]
75. LeetCode (Medium) - 01 Matrix [link]
76. LeetCode (Hard) - Expression Add Operators [link]
77. LeetCode (Medium) - The Maze [link]
78. LeetCode (Medium) - Validate IP Addreess [link]
79. LeetCode (Medium) - Sort Characters By Frequency [link]
80. LeetCode (Easy) - Path Sum III [link]
81. LeetCode (Medium) - Reconstruct Itineraries [link]
82. LeetCode (Medium) - Flatten a Multilevel Doubly Linked List [link] (DFS)
83. LeetCode (Hard) - Reverse Pairs [link] (Fenwick Trees / BIT Trees)
84. LeetCode (Hard) - Optimal Account Balancing [link] (Settling Debts Paper/ 3-partition problem - Optimal, Greedy, Clique Reduction/BFS, Fastest)
85. LeetCode (Hard) - LFU Cache [link] (OrderedDict used as a queue)
86. LeetCode (Hard) - Basic Calculator III [link] (See discussion_basic_Calculator.pdf, python3 iter)
87. LeetCode (Easy) - Logger Rate Limiter [link]
88. LeetCode (Medium) - Encode and Decode TinyURL [link]
89. LeetCode (Hard) - Number of Islands II [link]
90. LeetCode (Easy) - Shortest Word Distance [link]
91. LeetCode (Easy) - Intersection of Two Arrays [link]
92. LeetCode (Medium) - Decode Ways [link]
93. LeetCode (Hard) - Longest Consecutive Sequence [link] (UnionFind, Ad-hoc)
94. LeetCode (Medium) - Remove Nth Node From End Of List [link] (Two Pointers)
95. LeetCode (Hard) - Integer to English Words [link] (Divide and Conquer)
96. LeetCode (Medium) - Fraction to Recurring Decimal [link]
97. LeetCode (Medium) - Surrounded Regions [link] (BFS)
98. LeetCode (Medium) - Word Ladder [link] (Bi-Directional BFS)
99. LeetCode (Medium) - Spiral Matrix [link]
100. LeetCode (Medium) - Clone Graph [link]
101. LeetCode (Medium) - Design Snake Game [link]
102. LeetCode (Medium) - Multiply Strings [link]
103. LeetCode (Easy) - Linked List Cycle [link]
104. LeetCode (Easy) - Excel Sheet Column Number [link]
105. LeetCode (Medium) - Letter Combinations of a Phone Number [link] (Backtracking)
106. LeetCode (Hard) - Insert Interval [link]
107. LeetCode (Easy) - Jewels and Stones [link]
108. LeetCode (Medium) - Friend Circles [link] (Union-Find)
109. LeetCode (Medium) - Add and Search Word - Data structure design [link] (Trie)
110. LeetCode (Medium) - Bomb Enemy [link] (Dynamic Programming)
111. LeetCode (Medium) - Coin Change [link] (Dynamic Programming, DFS)
112. LeetCode (Medium) - Longest Increasing Subsequence [link] (Dynamic Programming, Binary Search)
113. LeetCode (Medium) - Wiggle Subsequence [link] (Greedy Algorithm)
114. LeetCode (Medium) - Course Schedule [link] (Detect cycle in a directed graph)
115. LeetCode (Medium) - Course Schedule II [link] (Topological Sort, Cycle Detection in 114.)
116. LeetCode (Medium) - Word Search [link] (Backtracking)
117. LeetCode (Medium) - Permutations II [link] (Backtracking)
118. LeetCode (Medium) - Palindrome Partitioning [link] (Backtracking)
119. LeetCode (Medium) - Compare Version Numbers [link] (String Manipulation)
120. LeetCode (Medium) - Largest Number [link] (Sorting, String/Arrays, custom comparator op)
121. LeetCode (Medium) - Nth Highest Salary [link] (SQL)
122. LeetCode (Medium) - Remove K Digits [link] (Greedy Algorithm, Stacks, Monotonically Increasing Sequence)
123. LeetCode (Medium) - Pow(x,n) [link] (Divide and Conquer-ish)
124. LeetCode (Medium) - Simplify Path [link] (Stacks)
125. LeetCode (Easy) - Implement strStr() [link] (String, Rabin Karp Algorithm)
126. LeetCode (Medium) - Distribute Coins in Binary Tree [link] (Depth First Search)
127. LeetCode (Medium) - Decode String [link] (String/Stacks)
128. LeetCode (Medium) - Game Of Life [link] (Matrix/Game/Array)
129. LeetCode (Hard) - Word Ladder II [link] (BFS, all shortest paths between two nodes in undirected graph)
130. LeetCode (Hard) - Max Points on a Line [link] (Array iteration, defining a line, duplicates resolution, checking collinearity)
131. LeetCode (Medium) - Copy List with Random Pointer [link] (Similar to Clone Graph problem)
132. LeetCode (Medium) - Next Greater Element III [link]
133. LeetCode (Medium) - Reorder List [link] (Suturing a LinkedList, Stack)
134. LeetCode (Medium) - Restore IP Addresses [link] (Backtracking)
135. LeetCode (Hard) - Sliding Window Maximum [link] (Dynamic Programming)
136. LeetCode (Medium) - Partition List [link] (LinkedList)
137. LeetCode (Medium) - Pacific Atlantic Water Flow [link] (DFS, Similar to Longest Increasing Path in a Matrix)
138. LeetCode (Hard) - Longest Increasing Path in a Matrix [link] (DFS, DP/memoization)
139. LeetCode (Easy) - Sum of Root To Leaf Binary Numbers [link] (DFS, Bit Manipulation)
140. LeetCode (Medium) - Next Greater Node In Linked List [link] (Stack, Arrays)
141. LeetCode (Hard) - Subarrays with K Different Integers [link] (Sliding Window)
142. LeetCode (Easy) - Pairs of Songs With Total Durations Divisible by 60 [link] (Hash Table)
143. LeetCode (Easy) - Find the Town Judge [link] (Sets)
144. LeetCode (Easy) - Rotting Oranges [link] (BFS)
145. LeetCode (Easy) - Cousins in Binary Tree [link] (BFS)
146. LeetCode (Medium) - Vertical Order Traversal of a Binary Tree [link] (BFS, interesting use of lambda/defaultdict and reported order)
147. LeetCode (Medium) - Minimum Cost For Tickets [link] (Dynamic Programming)
148. LeetCode (Hard) - Unique Paths III [link] (DFS, Dynamic Programming/Bit Manipulation)
149. LeetCode (Medium) - Longest Turbulent Subarray [link] (Arrays)
150. LeetCode (Medium) - Prison Cells After N Days [link] (Bit Manipulation)
151. LeetCode (Medium) - Inorder Successor of BST [link] (Inorder Traversal, BST, Stack)
152. LeetCode (Medium) - Find First and Last Position of Element in Sorted Array [link] (Python's bisect package, Binary Search)
153. LeetCode (Medium) - Minesweeper [link] (recursive DFS)
154. LeetCode (Easy) - Count and Say [link] (Recursion)
155. LeetCode (Easy) - Delete node in a linked list [link] (Trick on LL/ copy the next element to current and delete the next one)
156. LeetCode (Easy) - Merge two sorted lists [link] (Recursion)
157. LeetCode (Easy) - Palindrome Linked List [link] (O(1) space and O(n) time)
158. LeetCode (Easy) - High Five [link] (Heap)
159. LeetCode (Medium) - Max Increase to Keep City Skyline [link] (Smart Iteration)
160. LeetCode (Hard) - Robot Room Cleaner [link] (Depth First Search)
161. LeetCode (Medium) - Rotate List [link] (Linked List)
162. LeetCode (Hard) - Number of Atoms [link] (Hash Table)
163. LeetCode (Medium) - Reverse Words in a String II [link] (in-place transformation)
164. LeetCode (Easy) - Valid Parentheses [link] (Stack)
165. LeetCode (Medium) - Add Two Numbers II [link] (Stack, reverse linked list)
166. LeetCode (Hard) - Merge k Sorted Lists [link] (Accumulate in list and sort instead of recursion)
167. LeetCode (Easy) - Intersection of Two Linked Lists [link] (Stack, Two pointers)
168. LeetCode (Medium) - Binary Tree Inorder Traversal [link] (Iterative/recursive inorder)
169. LeetCode (Medium) - Binary Tree Level Order Traversal [link] (BFS)
170. LeetCode (Medium) - Populating Next Right Pointers in Each Node [link] (BFS, perfect binary tree constraint)
171. LeetCode (Medium) - Populating Next Right Pointers in Each Node II [link] (BFS)
172. LeetCode (Easy) - Lowest Common Ancestor of a Binary Search Tree [link] (Recursion)
173. LeetCode (Medium) - Lowest Common Ancestor of a Binary Tree [link] (Iterative post order traversal using stack)
174. LeetCode (Medium) - Construct Binary Tree from Preorder and Inorder Traversal [link] (Recursion)
175. LeetCode (Hard) - Alien Dictionary [link] (Topological Sort for directed graph)
176. LeetCode (Medium) - Grumpy Bookstore Owner [link]