TRT
Sign in

// practice

Practice

Problems and design prompts with explanations that connect the idea to how software runs — then try the exercise yourself.

  1. dsaDesign a skip listImplement search, add and erase on a skip list with probabilistic heights, handle duplicates correctly, and measure how close average searches stay to log2 n.
  2. dsaDesign a bounded blocking queueBuild a thread-safe queue with a fixed capacity: enqueue blocks when full, dequeue blocks when empty, and no call busy-waits.
  3. dsaRange sum query: immutableAnswer many range-sum queries on a fixed array in O(1) each with a prefix-sum array.
  4. dsaRunning sum of an arrayReturn the running totals of an array, and see why recomputing each total from scratch is quadratic.
  5. dsaCapacity to ship packages within D daysFind the smallest ship capacity that delivers packages in order within D days, by binary searching capacities with a greedy check.
  6. dsaPow(x, n)Compute x to the power n with O(log n) multiplications by halving the exponent, including negative exponents.
  7. dsaSearch a 2D matrix IISearch a matrix whose rows and columns are sorted independently, in O(m + n), with a staircase walk from the top-right corner.
  8. dsaMissing numberAn array holds every number from 0 to n except one. Find it four ways and compare their time and space.
  9. dsaUTF-8 validationGiven a list of byte values, decide whether they form valid UTF-8, using the leading bits of each byte.
  10. dsaMy calendar IAccept a booking only if it overlaps no existing one, by checking its neighbors in an ordered map.
  11. dsaRange moduleTrack a set of half-open ranges under additions, removals and coverage queries, keeping disjoint intervals sorted.
  12. dsaStock price fluctuationHandle out-of-order and corrected price updates while reporting the latest, highest and lowest prices, with a hash map plus an ordered structure.
  13. dsaFibonacci numberCompute the nth Fibonacci number recursively, measure the calls, then fix it with memoization and with a loop.
  14. dsaShortest common supersequenceBuild the shortest string containing both inputs as subsequences by walking back through an LCS table.
  15. dsaAccounts mergeMerge user accounts that share any email address, by unioning emails and grouping them by root.
  16. dsaFind critical and pseudo-critical edges in a minimum spanning treeClassify each edge as in every minimum spanning tree, in some, or in none, by rerunning Kruskal with the edge removed or forced in.
  17. dsaFind eventual safe statesFind the vertices of a directed graph from which every path ends at a terminal vertex, using three-color DFS.
  18. dsaFind if path exists in graphBuild adjacency lists from an edge list and decide whether two vertices are connected with BFS or DFS.
  19. dsaFind the city with the smallest number of neighbors at a threshold distanceCompute all-pairs distances with Floyd-Warshall, then count each city's neighbors within a distance limit.
  20. dsaNumber of provincesCount the groups of cities connected directly or indirectly, given an adjacency matrix, with union-find.
  21. dsaPath with minimum effortFind the route across a height grid whose largest single climb is as small as possible, with Dijkstra on bottleneck costs.
  22. dsaSatisfiability of equality equationsDecide whether a set of equalities and inequalities between variables can all hold, by unioning the equalities first.
  23. dsaSliding puzzleSolve a 2 × 3 sliding-tile puzzle in the fewest moves by searching the graph of board states, with BFS or A*.
  24. dsaContains duplicate IIIFind two values close in position and in value, with a ceiling query on an ordered window.
  25. dsaRandom pick with blacklistPick uniformly from 0 to n − 1 excluding a blacklist, with one random call per pick, by remapping blacklisted values through a hash map.
  26. dsaSubarray sum equals KCount the subarrays whose sum is exactly k, even with negative numbers, using prefix sums and a hash map.
  27. dsaKth largest element in a streamReport the kth largest value after each insertion into a stream, with a min-heap that never holds more than k values.
  28. dsaMinimum cost to connect sticksJoin sticks into one, paying the sum of the two lengths each time, at minimum total cost, by always joining the two shortest.
  29. dsaSliding window medianReport the median of every window of size k, with an ordered multiset or two heaps with lazy deletion.
  30. dsaMinimum number of arrows to burst balloonsShoot the fewest arrows to burst every horizontal balloon, shooting at the earliest end each time.
  31. dsaDesign linked listImplement a linked list with get, add at head, add at tail, add at index and delete at index, handling every edge case.
  32. dsaInsertion sort listSort a singly linked list with insertion sort, splicing each node into a growing sorted list behind a dummy head.
  33. dsaLinked list random nodePick a uniformly random node from a linked list in one pass with O(1) extra memory, using reservoir sampling.
  34. dsaMerge k sorted listsMerge k sorted linked lists into one, in O(N log k), with a min-heap of the current list heads.
  35. dsaSort listSort a linked list in O(n log n) time with merge sort, splitting at the middle with fast and slow pointers and merging by rewiring nodes.
  36. dsaCount primesCount the primes below n, first by testing each number and then with the sieve of Eratosthenes, and compare how the two grow.
  37. dsaShuffle an arrayReturn uniformly random permutations of an array with the Fisher-Yates shuffle, and restore the original on demand.
  38. dsaShortest path in binary matrixFind the shortest clear path from the top-left to the bottom-right of a grid, moving in eight directions, with BFS.
  39. dsaLargest numberArrange numbers so their concatenation is as large as possible, using a custom comparator that defines a valid total order.
  40. dsaMaximum gapFind the largest difference between consecutive values in sorted order, in linear time, without a comparison sort.
  41. dsaSort an arraySort an array of integers in O(n log n) without the built-in sort: implement merge sort, then quick sort with a random pivot, and compare.
  42. dsaSort array by increasing frequencySort values by how often they occur, breaking ties by value in decreasing order, with a composite sort key.
  43. dsaDecode stringExpand an encoded string such as 3[a2[c]] into accaccacc, first recursively and then with an explicit stack.
  44. dsaDesign a stack with increment operationSupport push, pop and adding a value to the bottom k elements, all in O(1), by recording increments lazily and passing them down on pop.
  45. dsaDesign circular queueImplement a fixed-size queue on a ring buffer, with every operation in O(1) and correct full and empty checks.
  46. dsaImplement queue using stacksBuild a FIFO queue from two LIFO stacks, and show that each operation is O(1) amortized.
  47. dsaOnline stock spanReport, for each new price, how many consecutive days up to today had a price at most today's, with a monotonic stack that is O(1) amortized per call.
  48. dsaEncode and decode a list of stringsPack a list of arbitrary strings into a single contiguous byte buffer with length prefixes and decode it back without delimiter collisions.
  49. dsaFind the first occurrence in a stringReturn the first index where a pattern occurs in a text, with Rabin-Karp or KMP in linear time.
  50. dsaRepeated DNA sequencesFind every 10-letter sequence that occurs more than once in a DNA string, by hashing a rolling window.
  51. dsaShortest palindromeAdd the fewest characters to the front of a string to make it a palindrome, by finding its longest palindromic prefix with the prefix function.
  52. dsaBalance a binary search treeTurn any binary search tree into a balanced one with the same keys, by flattening it in order and rebuilding.
  53. dsaBinary tree inorder traversalReturn the inorder traversal of a binary tree, first recursively and then iteratively with an explicit stack.
  54. dsaBinary tree maximum path sumFind the path with the largest sum of values anywhere in the tree, returning the best downward branch and recording the best turning path.
  55. dsaConvert sorted array to binary search treeBuild a height-balanced binary search tree from sorted values by making the middle value the root, recursively.
  56. dsaDelete node in a BSTDelete a key from a binary search tree, handling nodes with zero, one and two children.
  57. dsaFlatten nested list iteratorIterate over the integers of an arbitrarily nested list lazily, keeping your place with an explicit stack instead of recursion.
  58. dsaInsert into a binary search treeInsert a value into a binary search tree by searching for its empty spot and attaching a new leaf.
  59. dsaLongest duplicate substringFind the longest substring that occurs at least twice, with a suffix array and LCP array, or binary search over rolling hashes.
  60. dsaMinimum depth of binary treeFind the depth of the shallowest leaf, stopping a level-order traversal at the first leaf it meets.
  61. dsaRepeated substring patternDecide whether a string is a shorter block repeated several times, using its smallest period from the prefix function.
  62. dsaMove zeroesMove every 0 in an array to the end while keeping the other elements in order, in place and in one pass.
  63. dsaDesign a hash mapBuild put, get and remove for a hash map from scratch, without using your language's built-in hash table.
  64. dsaContains duplicateReturn true if any value appears at least twice in an array of integers, and false if every value is distinct.
  65. dsaGroup anagramsGroup the words in a list that are anagrams of each other, using a key that every anagram of a word shares.
  66. dsaTwo sumReturn the indices of the two numbers in an array that add up to a target value.
  67. system designDesign a Rate LimiterImplement a token bucket or fixed-window counter that allows bursts but enforces a steady request rate across many service instances.
  68. dsaBest Time to Buy and Sell StockChoose one buy day and a later sell day to maximize positive profit; return zero if no profitable trade exists.
  69. dsaMajority elementFind the value that fills more than half of an array, and compare a hash map, sorting, a random guess and the Boyer-Moore vote.
  70. dsaProduct of array except selfReturn, for each index, the product of all other elements, with prefix and suffix products and no division.
  71. dsaCombination sum IIFind every unique combination that sums to a target when each candidate may be used once and the input contains duplicates.
  72. dsaCombination sumFind every combination of candidates, each usable any number of times, that adds up to a target, pruning once the sum is too large.
  73. dsaGenerate parenthesesGenerate every well-formed string of n pairs of parentheses, never building an invalid prefix.
  74. dsaN-queensPlace n queens on an n × n board so that no two attack each other, and return every solution, pruning by column and diagonal.
  75. dsaPalindrome partitioningSplit a string into pieces that are all palindromes, in every possible way.
  76. dsaPermutationsReturn every ordering of an array of distinct integers, tracking which elements are already used.
  77. dsaSubsetsReturn every subset of a set of distinct integers, using backtracking with a start index.
  78. dsaBinary searchFind a target in a sorted array in O(log n), with a half-open range and an invariant that makes every boundary obvious.
  79. dsaFind the duplicate numberAn array of n + 1 numbers from 1 to n contains one repeated value. Find it without modifying the array and with O(1) extra space, by treating the array as a linked list with a cycle.
  80. dsaFind first and last position of element in sorted arrayReturn the first and last index of a target in a sorted array with duplicates, using lower and upper bounds.
  81. dsaFind minimum in rotated sorted arrayFind the smallest element of a rotated sorted array in O(log n) by comparing the middle with the right end.
  82. dsaKoko eating bananasFind the slowest eating speed that finishes all piles within h hours, by binary searching over speeds with a feasibility check.
  83. dsaMedian of two sorted arraysFind the median of two sorted arrays in O(log min(m, n)) by binary searching for the cut that splits all elements in half.
  84. dsaSearch a 2D matrixSearch a matrix whose rows continue each other in sorted order, as one flat sorted array of m × n elements.
  85. dsaSearch insert positionReturn the index of a target in a sorted array, or where it would be inserted: the lower bound.
  86. dsaSearch in rotated sorted arrayFind a target in a sorted array that has been rotated, in O(log n), by identifying the sorted half at each step.
  87. dsaCounting bitsFor every integer from 0 to n, return how many 1 bits it has, in a single pass.
  88. dsaNumber of 1 bitsCount how many bits are set in the binary form of a 32-bit unsigned integer.
  89. dsaSingle numberEvery value in an array appears twice except one. Find it in linear time and constant extra memory.
  90. dsaDesign add and search wordsStore words in a trie and search patterns in which a dot matches any letter, branching only where the pattern has a dot.
  91. dsaLRU cacheBuild a fixed-capacity cache with O(1) get and put that evicts the least recently used key, using a hash map and a doubly linked list.
  92. dsaTime based key-value storeStore values with timestamps and answer 'value as of time t' queries with an upper-bound search per key.
  93. dsaBurst balloonsMaximize the coins from bursting balloons with an interval DP over which balloon in each range bursts last.
  94. dsaClimbing stairsCount the ways to climb n stairs one or two steps at a time, first with memoized recursion and then with two variables.
  95. dsaCoin changeFind the fewest coins that make an amount, with unlimited copies of each coin, using an unbounded knapsack table.
  96. dsaCombination sum IVCount the ordered sequences of numbers that sum to a target, and see how the loop order decides whether orderings are counted.
  97. dsaDecode waysCount the ways to decode a digit string into letters, adding the counts for one-digit and two-digit last letters.
  98. dsaDistinct subsequencesCount how many times t appears as a subsequence of s with a two-string counting DP.
  99. dsaEdit distanceFind the fewest insertions, deletions and replacements to turn one word into another, with a table over prefixes, then in two rows.
  100. dsaHouse robber IIRob houses arranged in a circle by solving the straight-line problem twice, once without the first house and once without the last.
  101. dsaHouse robberMaximize the loot from houses on a street without robbing two neighbors, with a take-or-skip recurrence.
  102. dsaLongest common subsequenceFind the length of the longest subsequence shared by two strings with a table over their prefixes.
  103. dsaLongest increasing subsequenceFind the length of the longest strictly increasing subsequence, in O(n²) with DP and in O(n log n) with patience tails.
  104. dsaLongest palindromic subsequenceFind the longest subsequence of a string that reads the same backward, with an interval DP on the string's two ends.
  105. dsaMaximum subarrayFind the largest sum of a contiguous subarray in O(n) with Kadane's best-ending-here recurrence.
  106. dsaMin cost climbing stairsFind the cheapest way to the top of a staircase where each step has a cost, filling a table from the bottom up.
  107. dsaPartition equal subset sumDecide whether an array can be split into two equal-sum halves, as a subset-sum table with a downward loop.
  108. dsaRegular expression matchingMatch a string against a pattern with . and * using a table over string and pattern prefixes.
  109. dsaTarget sumCount the ways to assign + and − signs to reach a target, by transforming it into counting subsets with a given sum.
  110. dsaUnique paths IICount right-and-down paths through a grid with obstacles, setting blocked cells to zero.
  111. dsaUnique pathsCount the paths from the top-left to the bottom-right of a grid moving only right or down, with a grid DP.
  112. dsaWord breakDecide whether a string can be split into dictionary words with a DP over prefixes.
  113. dsaCheapest flights within K stopsFind the cheapest route with at most k stops by running k + 1 Bellman-Ford rounds over a copy of the previous round.
  114. dsaClone graphDeep-copy a connected undirected graph, mapping each original vertex to its copy so that cycles are copied once.
  115. dsaCourse schedule IIReturn an order in which all courses can be taken, or an empty list if the prerequisites form a cycle.
  116. dsaCourse scheduleDecide whether all courses can be finished given their prerequisites, by checking the prerequisite graph for a cycle.
  117. dsaMax area of islandFind the largest island in a grid by having each flood fill return the number of cells it marked.
  118. dsaMin cost to connect all pointsConnect every point at the lowest total Manhattan distance, with the O(n²) array version of Prim's algorithm.
  119. dsaNetwork delay timeFind how long a signal takes to reach every node of a weighted directed network, with Dijkstra from the source.
  120. dsaNumber of connected components in an undirected graphCount the connected components of a graph by starting a search from every vertex not yet visited.
  121. dsaNumber of islandsCount the islands in a grid of land and water, flooding each one with DFS or BFS the first time you step on it.
  122. dsaPacific Atlantic water flowFind the cells whose water can reach both oceans by searching uphill from each ocean's border and intersecting the results.
  123. dsaReconstruct itineraryUse every flight ticket exactly once, starting from JFK and preferring alphabetical order, with a DFS that adds airports after their tickets run out.
  124. dsaRedundant connectionFind the edge that closes the only cycle in a graph that was a tree plus one extra edge, with union-find.
  125. dsaRotting orangesFind how many minutes it takes rot to spread from every rotten orange to all fresh ones, with a multi-source BFS.
  126. dsaSurrounded regionsCapture regions of O cells that don't touch the border, by first marking every O reachable from the border.
  127. dsaSwim in rising waterFind the earliest time you can swim across a grid as water rises, by minimizing the highest cell on the path with Dijkstra.
  128. dsaWord ladderFind the length of the shortest chain of one-letter changes from one word to another through a dictionary, with BFS over an implicit graph.
  129. dsaWord search IIFind every dictionary word that can be traced through adjacent grid cells, with one depth-first search guided by a trie of all the words.
  130. dsaWord searchDecide whether a word can be traced through adjacent cells of a letter grid, marking cells as used and unmarking them on the way back.
  131. dsaGas stationFind the starting station for a circular route in one pass, using the total balance and the running tank.
  132. dsaJump gameDecide whether the last index is reachable by tracking the farthest index reachable so far.
  133. dsaMerge triplets to form target tripletDecide whether element-wise maximums of some triplets can equal a target, by merging only the triplets that never exceed it.
  134. dsaHand of straightsSplit a hand into groups of consecutive cards by always starting a group at the smallest remaining card.
  135. dsaInsert delete getrandom O(1)Design a set that inserts, removes and returns a uniformly random element, each in O(1) on average.
  136. dsaLongest consecutive sequenceFind the length of the longest run of consecutive integers in an unsorted array in O(n), using a hash set and starting only at the beginning of each run.
  137. dsaValid SudokuCheck whether a partly filled 9 × 9 Sudoku board breaks any rule, using the box-number formula.
  138. dsaFind median from data streamMaintain the median of a growing stream with a max-heap for the lower half and a min-heap for the upper half.
  139. dsaK closest points to originReturn the k points nearest the origin with a max-heap of size k keyed by squared distance.
  140. dsaFind k pairs with smallest sumsGenerate the k pairs with the smallest sums from two sorted arrays, treating each row of pairs as a sorted stream to merge.
  141. dsaKth largest element in an arrayFind the kth largest value in an unsorted array with a size-k heap or with quickselect, without fully sorting it.
  142. dsaLast stone weightRepeatedly smash the two heaviest stones together, using a max-heap to find them in O(log n).
  143. dsaSingle-threaded CPUSimulate a CPU that always runs the shortest available task, with a heap of tasks that have arrived.
  144. dsaSliding Window MaximumReturn the maximum value for every contiguous window of width k.
  145. dsaTask schedulerFind the minimum time to run tasks when equal tasks need n idle intervals between them, by always running the most frequent remaining task.
  146. dsaTop k frequent elementsReturn the k most frequent values, by counting with a hash map and keeping a size-k heap of counts.
  147. dsaInsert intervalInsert a new interval into a sorted, non-overlapping list, merging where needed, in O(n).
  148. dsaMerge intervalsMerge all overlapping intervals after sorting them by start, in one pass.
  149. dsaMinimum interval to include each queryFor each query point, find the length of the shortest interval containing it, by sweeping sorted queries and keeping a heap of active intervals.
  150. dsaNon-overlapping intervalsFind the fewest intervals to remove so the rest don't overlap, by keeping as many as possible with the earliest-end rule.
  151. dsaAdd two numbersAdd two numbers stored as linked lists of digits in reverse order, building the result list with a dummy head and a carry.
  152. dsaCopy list with random pointerDeep-copy a linked list whose nodes also have a random pointer to any node, so that the copy's pointers lead only to copy nodes.
  153. dsaDesign browser historyImplement a browser's visit, back and forward with two stacks, or with an array and a cursor.
  154. dsaLinked list cycleDecide whether a linked list loops back on itself, in O(n) time and O(1) memory, with fast and slow pointers.
  155. dsaMerge two sorted listsSplice the nodes of two sorted linked lists into one sorted list, using a dummy head and a tail pointer.
  156. dsaRemove nth node from end of listRemove the node n positions from the end of a linked list in one pass, using two pointers a fixed gap apart.
  157. dsaReorder listRearrange L0 → L1 → … → Ln into L0 → Ln → L1 → Ln−1 → … in place, by finding the middle, reversing the second half and merging.
  158. dsaReverse linked listReverse a singly linked list in place by turning every next pointer around, iteratively and then recursively.
  159. dsaLongest increasing path in a matrixFind the longest strictly increasing path between neighboring cells of a grid with a memoized depth-first search.
  160. dsaRotate imageRotate an n × n matrix by 90 degrees clockwise, in place, using index arithmetic.
  161. dsaSet matrix zeroesZero every row and column that contains a 0, first with O(m + n) extra memory and then with O(1).
  162. dsaSpiral matrixReturn the elements of an m × n matrix in clockwise spiral order, keeping four boundaries straight.
  163. dsaCar fleetCount how many groups of cars arrive at a destination, by sorting by position and stacking arrival times.
  164. dsaDaily temperaturesFor each day, count the days until a warmer one, in a single pass with a monotonic stack.
  165. dsaEvaluate reverse Polish notationEvaluate an arithmetic expression written in postfix order with a single stack of operands.
  166. dsaLargest rectangle in histogramFind the largest rectangle under a histogram in O(n), using an increasing stack to find each bar's previous and next smaller bars.
  167. dsaLongest valid parenthesesFind the length of the longest well-formed run of parentheses, using a stack of indexes instead of characters.
  168. dsaMin stackDesign a stack that also returns its minimum element in O(1), even after pops, by storing the running minimum with each item.
  169. dsaValid parenthesesDecide whether a string of (), [] and curly brackets is balanced, with each closer matching the most recent unclosed opener.
  170. dsaLetter combinations of a phone numberReturn every string a sequence of phone digits could spell, one letter per digit.
  171. dsaLongest Repeating Character ReplacementFind the longest substring that can be made uniform by replacing at most k characters.
  172. dsaLongest Substring Without Repeating CharactersFind the maximum length of a contiguous substring containing no repeated characters.
  173. dsaMinimum Window SubstringFind the shortest substring of s containing every required character in t with at least its required multiplicity.
  174. dsaPartition labelsSplit a string into as many pieces as possible so each letter appears in only one piece, using each letter's last position.
  175. dsaPermutation in StringDetermine whether any contiguous window in the second string is a permutation of the first string.
  176. dsaReverse words in a stringReverse the order of the words in a string, collapsing extra spaces, with two-pointer reversals.
  177. dsaValid anagramDecide whether two strings are anagrams by counting letters instead of sorting, in O(n) time.
  178. dsaValid palindromeDecide whether a string reads the same forward and backward after ignoring case and non-alphanumeric characters, in O(1) extra space.
  179. dsaBalanced binary treeDecide whether every node's subtrees differ in height by at most one, in a single O(n) pass.
  180. dsaBinary tree level order traversalReturn a tree's values level by level, using a queue and the length of the queue at the start of each level.
  181. dsaBinary tree right side viewReturn the values visible from the right side of a tree: the last node of each level.
  182. dsaConstruct binary tree from preorder and inorder traversalRebuild a binary tree from its preorder and inorder traversals, using the root from preorder to split the inorder list.
  183. dsaDiameter of binary treeFind the longest path between any two nodes by returning heights and recording the best path through each node.
  184. dsaCount good nodes in binary treeCount nodes that are at least as large as every node on the path from the root, passing the running maximum down.
  185. dsaInvert binary treeMirror a binary tree by swapping every node's left and right children.
  186. dsaKth smallest element in a BSTFind the kth smallest key in a binary search tree with an inorder traversal that stops early.
  187. dsaLowest common ancestor of a binary search treeFind the lowest node that has both p and q as descendants, by walking down from the root until the two keys split.
  188. dsaMaximum depth of binary treeReturn the number of nodes on the longest root-to-leaf path, recursively and with a level-order traversal.
  189. dsaSame treeDecide whether two binary trees have the same shape and the same values, by recursing on both at once.
  190. dsaSubtree of another treeDecide whether one tree appears as a subtree of another, by running a same-tree check from every node.
  191. dsaValidate binary search treeDecide whether a binary tree is a valid binary search tree by passing down the range each subtree must lie in.
  192. dsaImplement a trieBuild a prefix tree with insert, exact search and prefix search, each in time proportional to the word's length.
  193. dsaContainer with most waterFind two lines that hold the most water, moving the pointer at the shorter line inward each step.
  194. dsaMerge sorted arrayMerge a sorted array into another sorted array that has empty space at its end, in place, by filling from the back.
  195. dsaSort colorsSort an array of 0s, 1s and 2s in one pass and in place, with a three-way (Dutch national flag) partition.
  196. dsa3SumFind every unique triple that sums to zero by fixing one value and running a two-pointer scan on the rest.
  197. dsaTrapping rain waterCompute the water trapped between bars after rain, with two pointers and running maximums from each side.
  198. dsaTwo sum II: input array is sortedFind two numbers in a sorted array that add up to a target, in O(n) time and O(1) space, with converging pointers.
  199. system designDesign a Short-Link ServiceDesign short-link creation and redirection from traffic assumptions through identifier generation, storage, cache, and abuse controls.
  200. system designImplement a Time-Based Logger Rate LimiterTrack the last accepted timestamp for each message and reason about state growth, ordering, and concurrent requests.