The Hard List

Every other list on this site teaches you the patterns. This one stress-tests them. It is hard-only and pattern-complete: 19 patterns, at least four hard problems each, chosen so that finishing a section means you have seen the ways that pattern gets bent in a real interview - not just the textbook form.

This is Uber-flavoured. Uber’s DSA rounds lean on graphs, shortest path, heaps, intervals, and a heavy dose of DP, and they expect runnable code against real test cases. So the DP section is the biggest one here, and the graph sections assume you can write Dijkstra and Kahn’s algorithm from memory without a reference.

Work one pattern at a time. Do not shuffle. The value of a hard set comes from solving five problems that fail in five different ways inside the same pattern - that is what builds the instinct to recognise the trap before you write code. Each section links back to its fundamentals deep dive if you need to reload the base technique first.

Which list should I use?

• 1 week of prep? → Quick-Fire 50
• 4 weeks of prep? → The Blind 75
• 8 weeks of prep? → NeetCode 150
• Already confident on the patterns? → You’re here. The Hard List.

💡 How to use: Give each problem 35 minutes. If you’re stuck, read the editorial, then close it and write the solution from scratch. A problem you read is not a problem you know.

A few problems appear under two patterns - Word Search II is both trie and backtracking, Count of Range Sum is both prefix sum and BIT. That repetition is deliberate: the second time you meet it, solve it with the other pattern’s lens. Repeats are noted in the table.

Two Pointers

Hard two-pointer problems stop being about “left and right walking inward” and start being about what invariant you can maintain in O(1) per step. The trigger is a sorted (or sortable) array plus a target relation, or a problem where the naive answer is O(n²) pair enumeration. At the hard level the pointers often live inside a merge sort, so the “two pointers” are the two halves of a divide-and-conquer, and the invariant is a count you accumulate while merging.

Trapping Rain Water - the invariant is the taller wall

  L ->                                 <- R
  |  leftMax = 2            rightMax = 3  |
  #                                       #
  # . . . . . . . . . . . . . . . . . . . #
  # ~ ~ # ~ ~ ~ # ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ # #
  2 0 1 3 0 1 2 1 ...

  move the pointer on the SHORTER side:
  water at that index = min(leftMax, rightMax) - height[i]

Deep dive: Two Pointers fundamentals →

Sliding Window

The easy version of this pattern is “expand right, shrink left while invalid”. Hard versions break one of the two halves. Either the window is not shrinkable in the obvious direction (the answer needs “exactly K”, which you get as atMost(K) - atMost(K-1)), or the value you want at the window boundary is not a count but a maximum, which needs a monotonic deque inside the window. The trigger is still “contiguous subarray or substring, optimise a length or a count”.

Exactly K distinct = atMost(K) - atMost(K - 1)

  nums = 1 2 1 2 3        K = 2

  atMost(2):  [1 2] [1 2 1] [2 1 2] ...   -> 7 subarrays
  atMost(1):  [1] [2] [1] [2] [3] ...     -> 5 subarrays
  exactly 2 = 7 - 5 = 2 windows too many to shrink directly

Deep dive: Sliding Window fundamentals →

Binary Search (including Search on Answer)

At the hard level binary search is almost never over an array. It is over the answer space: you guess an answer, ask a monotone yes/no question about it, and halve. The trigger is “minimise the maximum” or “maximise the minimum” plus a feasibility check you can write in O(n). The hard part is never the search - it is proving the predicate is monotone and writing feasible(x) without an off-by-one.

Search on answer - the shape you are looking for

  candidate:  1  2  3  4  5  6  7  8  9
  feasible?   N  N  N  N  Y  Y  Y  Y  Y
                          ^
                          first Y = the answer

  lo = min possible, hi = max possible
  while lo < hi:
      mid = lo + (hi - lo) // 2
      if feasible(mid): hi = mid
      else:             lo = mid + 1

Deep dive: Binary Search fundamentals →

Stacks & Queues / Monotonic Stack

A monotonic stack answers “for each element, what is the nearest element to the left or right that is larger or smaller”. Every hard problem here is that question in disguise, or it is a parser - nested expressions where the stack holds the suspended outer context. The trigger for the monotonic version is “previous or next greater or smaller”; for the parser version it is nesting of any kind: brackets, formulas, encoded strings.

Largest Rectangle in Histogram - pop when the bar shrinks

  heights = 2 1 5 6 2 3
                    _
              _    | |
             | |   | |
             |5|   |6|          when we hit 2 < 6, pop 6:
   _         | |   | |          width = i - stack[-1] - 1
  |2|  _     | |   | |          area  = 6 * 1
  | | |1|    | |   | |
  ---------------------
   0   1      2     3    4   5

  stack holds indices with STRICTLY INCREASING heights

Deep dive: Stacks & Queues fundamentals →

Linked Lists

Hard linked-list problems are pointer-discipline exams. There is rarely a clever insight; there is a lot of state you must keep straight while mutating in place, usually with a dummy head and a “tail of the previous group” pointer. The other half of this pattern is list plus map, where you glue a hash map onto a doubly linked list to get O(1) ordering - which is exactly how caches are built, and why Uber asks it.

flowchart LR
    H["head sentinel"]:::client
    A["node A"]:::service
    B["node B"]:::service
    C["node C"]:::service
    T["tail sentinel"]:::client
    M["hash map key to node"]:::data
    H --> A
    A --> B
    B --> C
    C --> T
    M --> A
    M --> C
    classDef client fill:#4c3a5e,stroke:#818cf8,color:#e2e8f0
    classDef service fill:#1a3a2a,stroke:#4ade80,color:#e2e8f0
    classDef data fill:#3b3520,stroke:#fbbf24,color:#e2e8f0

Deep dive: Linked Lists fundamentals →

Trees & Traversal

Hard tree problems are about what you return up versus what you carry down. Almost all of them are one post-order DFS where each node returns a small tuple to its parent, and a global answer is updated on the way. The trigger phrase is “path”, “subtree”, or “any two nodes” - all three mean “compute something per subtree and combine at the node”. If you find yourself wanting a second traversal, you probably needed a bigger return tuple.

Return up vs carry down

              (10)  <- global best updated here
             /    \
        (2)          (9)
       /   \        /   \
     ...   ...    ...   ...

  dfs(node) returns  -> best downward path through node
  global answer      -> best path that BENDS at node
                        = node.val + max(left, 0) + max(right, 0)

  never return the bent path to the parent - a path bends once

Deep dive: Trees & Traversal fundamentals →

Graphs BFS/DFS

The hard version of graph traversal is rarely about the traversal. It is about defining the graph - what is a node, what is an edge - and about the state you must include in the visited key. If two paths reach the same cell with different remaining budget, the cell alone is not a state. The trigger is any problem about reachability, connectivity, or shortest number of steps on an unweighted structure, including implicit graphs where nodes are strings, board configurations, or bus stops.

flowchart TB
    S["start state"]:::client
    A["neighbour 1"]:::service
    B["neighbour 2"]:::service
    C["neighbour 3"]:::service
    D["goal"]:::data
    S --> A
    S --> B
    A --> C
    B --> C
    C --> D
    classDef client fill:#4c3a5e,stroke:#818cf8,color:#e2e8f0
    classDef service fill:#1a3a2a,stroke:#4ade80,color:#e2e8f0
    classDef data fill:#3b3520,stroke:#fbbf24,color:#e2e8f0

BFS visits states in layers, so the first time you pop the goal you have the fewest steps. DFS commits to one branch and is the right choice when you want all paths, or a value defined recursively over a subtree.

Deep dive: Graphs BFS/DFS fundamentals →

Shortest Path (Dijkstra / Bellman-Ford)

The moment edges carry unequal weights, plain BFS is wrong and you need Dijkstra - a BFS whose queue is a min-heap keyed on total cost so far. Use Bellman-Ford instead when the constraint is on the number of edges (relax exactly k times) or when weights can be negative. The trigger words are “minimum cost”, “minimum effort”, “cheapest”, “earliest time you can”, with non-uniform step costs. A useful variant: when all weights are 0 or 1, a deque replaces the heap and you get 0-1 BFS in O(V+E).

flowchart LR
    A["node A dist 0"]:::client
    B["node B dist 2"]:::service
    C["node C dist 5"]:::service
    D["node D dist 6"]:::data
    A -->|"w 2"| B
    A -->|"w 5"| C
    B -->|"w 4"| D
    C -->|"w 1"| D
    classDef client fill:#4c3a5e,stroke:#818cf8,color:#e2e8f0
    classDef service fill:#1a3a2a,stroke:#4ade80,color:#e2e8f0
    classDef data fill:#3b3520,stroke:#fbbf24,color:#e2e8f0

Pop the cheapest unsettled node, relax its edges, and never revisit a settled node. Here D settles at 6 via C, not 6 via B - and you only know that after C settles at 5.

Deep dive: Shortest Path fundamentals →

Topological Sort

Any time the input is “A must come before B”, you are building a DAG and running Kahn’s algorithm: repeatedly remove a node with in-degree zero. If you cannot empty the graph, there is a cycle. Hard versions add a twist - detect ambiguity (more than one valid order), group nodes into super-nodes and sort at two levels, or return the number of rounds rather than the order. The trigger is dependency, prerequisite, ordering constraint, or “build order”.

Kahn's algorithm

  edges: A->B  A->C  B->D  C->D

  in-degree:  A:0  B:1  C:1  D:2
  queue: [A]              output: -
  pop A -> B:0 C:0        output: A
  queue: [B, C]
  pop B -> D:1            output: A B
  pop C -> D:0            output: A B C
  pop D                   output: A B C D

  queue size > 1 at any step  => the order is not unique
  output length < node count  => there is a cycle

Deep dive: Topological Sort fundamentals →

Heaps / Priority Queue

Reach for a heap when you need repeated access to the current extreme of a changing set. Hard problems here are usually one of three shapes: two heaps balanced against each other to track a median or a split point; sort by one dimension and heap on the other, which is how almost every “maximise a ratio or a product” problem is solved; or a heap used as the frontier of a lazy expansion. The trigger is “k-th”, “median”, “top k”, or “at any point, the best available”.

Two heaps keep a median at the boundary

   max-heap (lower half)        min-heap (upper half)
        [ 1  3  5 ]      |         [ 7  9  11 ]
                  ^      |          ^
                  top    |          top

   invariant: size(low) == size(high) or size(low) == size(high) + 1
   median = low.top          if sizes differ
          = avg of both tops if sizes equal

   every insert: push to one, then move one across to rebalance

Deep dive: Heaps fundamentals →

Dynamic Programming - 1D and Sequence

This is the biggest cluster at Uber, so it is split in two. A 1D DP is defined by one index and a small amount of carried state, and the work is entirely in naming the state precisely. If you cannot finish the sentence “dp[i] is the best answer for the prefix ending at i, given that …” then you have not found the state yet. The trigger is “count the ways”, “maximum or minimum over choices”, or an obvious exponential recursion with overlapping subproblems.

State design is the whole problem

  Buy and Sell Stock IV - dp[t][i] = best profit using at most t
                                     transactions through day i

  hold[t]  = max(hold[t],  cash[t-1] - price)   own a share
  cash[t]  = max(cash[t],  hold[t]   + price)   own nothing

  day:      1     2     3     4     5
  price:    3     2     6     5     0
  cash[1]:  0     0     4     4     4
  cash[2]:  0     0     4     4     4

  a wrong state (dp[i] = best profit through day i) cannot
  express "how many transactions have I already spent"

Deep dive: Dynamic Programming fundamentals →

Dynamic Programming - 2D, Grid and Interval

Two indices means one of three sub-shapes. Two-sequence DP compares prefixes of two strings and fills a table row by row (edit distance, matching, subsequence counting). Grid DP walks a matrix, and the hard variants either walk it backwards, walk two paths simultaneously, or need an amortised transition instead of an O(n) inner scan. Interval DP is defined on a range [i..j] and splits on a middle element - the recurrence looks like dp[i][j] = best over k of dp[i][k] + dp[k][j] + cost, and it is the shape most people never get comfortable with.

Interval DP - iterate by LENGTH, split on the LAST balloon to pop

  dp[i][j] = max points from the OPEN interval (i, j)

  for len in 2 .. n:
      for i in 0 .. n - len:
          j = i + len
          for k in i+1 .. j-1:
              dp[i][j] = max(dp[i][j],
                             dp[i][k] + nums[i]*nums[k]*nums[j] + dp[k][j])

  the reversal that makes it work: k is the LAST balloon popped,
  so its neighbours are still i and j

Deep dive: Dynamic Programming fundamentals →

Backtracking

Backtracking is DFS over a decision tree with undo. The template is fixed - choose, recurse, un-choose - so all the difficulty lives in pruning and in avoiding duplicate branches. Two rules cover most of it: sort first so you can skip equal siblings, and prune the moment a partial candidate cannot possibly extend to a solution. The trigger is “all permutations”, “all combinations”, “all partitions”, or a constraint-satisfaction puzzle.

choose - recurse - un-choose

  place(row):
      if row == n: record solution; return
      for col in 0 .. n-1:
          if cols[col] or diag1[row+col] or diag2[row-col+n]:
              continue                          <- prune
          cols[col] = diag1[row+col] = diag2[row-col+n] = 1
          place(row + 1)
          cols[col] = diag1[row+col] = diag2[row-col+n] = 0

  the three boolean arrays turn an O(n) conflict check into O(1)

Deep dive: Backtracking fundamentals →

Tries

A trie turns a set of strings into a tree of shared prefixes, which makes prefix queries O(length) instead of O(dictionary). Use one whenever the same string set is queried repeatedly, when you need “does any word start with”, or - the less obvious case - when you are searching bits rather than characters, which makes a binary trie the tool for maximum-XOR problems. The other high-value use is pruning: a trie lets a grid DFS abort the instant no word can continue.

flowchart TB
    R["root"]:::client
    C["c"]:::service
    A["a"]:::service
    T["t end of word cat"]:::data
    R2["r"]:::service
    T2["t end of word cart"]:::data
    R --> C
    C --> A
    A --> T
    A --> R2
    R2 --> T2
    classDef client fill:#4c3a5e,stroke:#818cf8,color:#e2e8f0
    classDef service fill:#1a3a2a,stroke:#4ade80,color:#e2e8f0
    classDef data fill:#3b3520,stroke:#fbbf24,color:#e2e8f0

Deep dive: Tries fundamentals →

Union-Find

Union-find answers “are these two things in the same group” under a stream of merges, in effectively O(1) with path compression and union by size. Use it when merges only ever add connectivity - it cannot handle deletions. The trigger is connected components, “count groups”, cycle detection in an undirected graph, or anything processed in sorted edge order, which is why it competes with Dijkstra on threshold problems. The non-obvious skill is choosing what the elements are: sometimes they are rows and columns, or emails, not the objects in the problem statement.

Union by size plus path compression

  find(x): if parent[x] != x: parent[x] = find(parent[x])   <- compress
           return parent[x]

  union(a, b):
      ra, rb = find(a), find(b)
      if ra == rb: return False        <- already connected = a cycle
      if size[ra] < size[rb]: swap
      parent[rb] = ra; size[ra] += size[rb]
      return True

  before compression        after find(3)
    0 <- 1 <- 2 <- 3          0 <- 1
                              0 <- 2
                              0 <- 3

Deep dive: Union Find fundamentals →

Intervals / Greedy

Interval problems reduce to a sort plus a sweep, and the only real decision is what to sort by. Sort by start when you are merging or inserting. Sort by end when you are keeping a maximum non-overlapping set. Split each interval into a +1 start event and a -1 end event when you need the maximum concurrency at any moment. Greedy more generally needs an exchange argument: show that taking the locally best choice never makes the global answer worse. If you cannot argue that, it is a DP.

Sweep line - maximum concurrent intervals

  intervals: [0,30] [5,10] [15,20]

  events:  0:+1   5:+1   10:-1   15:+1   20:-1   30:-1
  running:   1      2      1       2       1       0
                    ^                      
                    peak = 2 rooms needed

  sort starts and ends independently, then walk both

Deep dive: Greedy fundamentals →

Design / Data-Structure

These problems give you an API and a complexity target, and expect you to compose two structures so that each operation hits its bound. Hash map plus doubly linked list gives O(1) ordering. Hash map plus array gives O(1) random access with removal. Two heaps give a median. The interview signal here is not cleverness but interface discipline: decide your invariants before writing a line, then keep every operation honouring them. Uber weights this heavily because it sits between DSA and LLD.

Hash map plus array - O(1) insert, remove, getRandom

  vals  = [ a  b  c  d ]        idx = { a:0, b:1, c:2, d:3 }

  remove(b):
     swap b with the LAST element        vals = [ a  d  c  b ]
     update idx[d] = 1                   idx  = { a:0, d:1, c:2 }
     pop the tail                        vals = [ a  d  c ]

  the swap-with-last trick is what makes removal O(1)

Deep dive: DSA Fundamentals →

Bit Manipulation

Bit problems reward a small vocabulary used fluently: n & (n-1) clears the lowest set bit, n & -n isolates it, XOR cancels pairs, and a bitmask is a subset. Hard versions ask you to count bits per position across all numbers (which handles “every element appears three times”), to build an answer greedily from the high bit down, or to use a mask as a DP state. The trigger is a constant-space requirement on a counting problem, or an explicit ban on arithmetic operators.

Every number appears three times except one

  position:      2  1  0
  nums = 2       0  1  0
         2       0  1  0
         3       0  1  1
         2       0  1  0

  count of set bits per position:   0  4  1
  take each count mod 3:            0  1  1   -> 3

  the O(1)-space version keeps two masks, ones and twos,
  which together form a mod-3 counter per bit

Deep dive: Bit Manipulation fundamentals →

Prefix Sum / Index-as-Hash

Prefix sums turn any range-sum query into a subtraction, and combining them with a hash map turns “count subarrays with property P” into a single pass: for each prefix, ask how many earlier prefixes make the current one valid. Index-as-hash is the twin trick - when values are bounded by the array length, the array is your hash table, and you can encode presence by sign or by placement to hit O(1) space. The trigger for the first is subarray sum or count; for the second, “O(1) extra space” on a problem about values in 1..n.

Count subarrays with sum k, in one pass

  nums = 1 2 3        k = 3

  prefix:  0   1   3   6
  seen:   {0:1}
  at 1: need 1-3 = -2  -> 0    seen = {0:1, 1:1}
  at 3: need 3-3 =  0  -> 1    seen = {0:1, 1:1, 3:1}
  at 6: need 6-3 =  3  -> 1    total = 2

  seeding seen with {0: 1} is what makes prefixes
  starting at index 0 count

Deep dive: DSA Fundamentals →

Advanced Structures (Segment Tree / Fenwick BIT / Ordered Set)

Rarely asked at Uber - included for completeness, and because the pattern is worth recognising even if you never implement it under time pressure. Reach for a Fenwick tree or segment tree when you need both point updates and range queries in logarithmic time; a prefix-sum array gives you O(1) queries but O(n) updates, and a plain array gives the reverse. The other common use is counting inversions or order statistics on the fly, which usually needs coordinate compression first because values are large and sparse. Every problem below also has a merge-sort or heap solution - know that one first, and treat the BIT as the second answer you offer.

Fenwick tree - each index covers a power-of-two block

  index:  1    2    3    4    5    6    7    8
  covers: 1   1-2   3   1-4   5   5-6   7   1-8

  update(i): while i <= n:  tree[i] += v;  i += i & -i
  query(i):  while i > 0 :  s += tree[i];  i -= i & -i

  range [l, r] = query(r) - query(l - 1)
  both operations touch at most log n nodes

Deep dive: DSA Fundamentals →

How to know you’re done

For each pattern, you should be able to do three things without looking anything up: state the trigger that makes you reach for it, write the core template from memory, and name the one variant that breaks the template and what you do instead. If a section fails that test, the fix is not more problems from that section - it is re-solving the two hardest ones you already did, from a blank file.

For the all-difficulty lists, see Quick-Fire 50, The Blind 75, and NeetCode 150. For pattern fundamentals, read DSA Fundamentals. For company-specific sets, start with Uber Interview Prep.