Skip to content

A collection of coding interview problems with my solutions. From various sources including Leet-Code, Interview experiences etc.

Notifications You must be signed in to change notification settings

aroraakshit/coding_prep

Folders and files

NameName
Last commit message
Last commit date

Latest commit

 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

Repository files navigation

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++


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]

About

A collection of coding interview problems with my solutions. From various sources including Leet-Code, Interview experiences etc.

Topics

Resources

Stars

Watchers

Forks

Releases

No releases published

Packages

No packages published