Ankit Kashyap

patterns-tbd

Patterns TBD

These are candidate low-level problem types to promote into Patterns after solving enough examples.

Source signal used for this pass:

Legend: MS Microsoft, GOOG Google, AMZN Amazon, META Facebook/Meta, AAPL Apple.

Pattern Count by Category

CategoryCount
1-D Dynamic Programming2
2-D Dynamic Programming1
Advanced Graphs1
Arrays & Hashing7
Backtracking1
Binary Search2
Bit Manipulation0
Graphs6
Greedy0
Heap / Priority Queue3
Intervals2
Linked List2
Math & Geometry1
Sliding Window3
Stack2
Trees5
Tries1
Two Pointers1
Total40

Table of Contents

1-D Dynamic Programming

2-D Dynamic Programming

Advanced Graphs

Arrays & Hashing

Backtracking

Graphs

Heap / Priority Queue

Intervals

Linked List

Math & Geometry

Sliding Window

Stack

Trees

Tries

Two Pointers

1 - Arrays & Hashing - Prefix Sum + Frequency Map

  • Trigger: count/existence of subarrays with a target sum, equal balance, or divisible sum.
  • Move: scan once; store previous prefix sums or remainders in a map.

Questions:

2 - Arrays & Hashing - Left/Right Contribution Pass

  • Trigger: each index answer depends on everything before and after it, but division or nested loops are awkward.
  • Move: build prefix contribution, suffix contribution, or do two directional passes.

Questions:

3 - Sliding Window - Variable Sliding Window Counts

  • Trigger: longest/shortest substring or subarray with at most/exactly some character/count constraint.
  • Move: expand right, update counts, shrink left while invalid.

Questions:

4 - Sliding Window - Fixed Window Counter Match

  • Trigger: permutation/anagram/subsequence window of fixed length or minimum covering window.
  • Move: maintain deficit counts and a matched/need counter instead of comparing full maps.

Questions:

5 - Sliding Window - Monotonic Window Queue

  • Trigger: sliding window max/min, or window validity depends on current max and min.
  • Move: keep one or two monotonic deques; evict stale indices as left moves.

Questions:

6 - Stack - Monotonic Stack

  • Trigger: next greater/smaller element, histogram area, removing digits/letters greedily.
  • Move: maintain a stack whose values stay increasing or decreasing; pop when the new item proves old items are done.

Questions:

7 - Two Pointers - Sorted Two-Pointer k-Sum

  • Trigger: pair/triplet/quad constraints after sorting, usually sum-related.
  • Move: sort, fix outer values, then move left/right inward; skip duplicates at the level they are created.

Questions:

8 - Intervals - Interval Merge and Intersection

  • Trigger: sorted ranges need to be merged, inserted, intersected, or made non-overlapping.
  • Move: sort by start time, carry current merged interval, or walk two interval lists together.

Questions:

9 - Intervals - Timeline Sweep

  • Trigger: rooms, calendars, overlapping events, employee free time, or active count over time.
  • Move: convert intervals to start/end events or use a min-heap of end times.

Questions:

10 - Heap / Priority Queue - K-Way Merge Frontier

  • Trigger: many sorted lists/rows/streams and the next global smallest/largest is needed.
  • Move: seed a heap with one item per source, then push the next item from the same source after popping.

Questions:

11 - Heap / Priority Queue - Top-K and Selection

  • Trigger: kth largest/smallest, top frequent, nearest points, or keep only the best k candidates.
  • Move: use quickselect, a size-k heap, or bucket counts depending on mutability and ordering needs.

Questions:

12 - Heap / Priority Queue - Streaming Median and Order Stats

  • Trigger: median or percentile after each insertion, or a sliding window median.
  • Move: two heaps for online median; lazy deletion when window removals are involved.

Questions:

13 - Arrays & Hashing - Prefix Sampling

  • Trigger: random choice with weights or repeated random pick by index.
  • Move: build prefix sums and binary-search a random target; use reservoir sampling when the stream is not fully stored.

Questions:

14 - Arrays & Hashing - Hash + Doubly Linked List Cache

  • Trigger: get and put must be O(1), but eviction depends on recency or frequency.
  • Move: hash key to node; move nodes between linked lists or frequency buckets.

Questions:

15 - Arrays & Hashing - O(1) Mutable Indexing

  • Trigger: insert/delete/get-random or frequency stack with constant-time operations.
  • Move: pair array storage with a value-to-index map; for duplicates, map value to a set of indices.

Questions:

16 - Arrays & Hashing - Time-Indexed Design

  • Trigger: queries ask for the latest value at or before a timestamp/version.
  • Move: append sorted (time, value) records per key, then binary-search on query.

Questions:

17 - Stack - Stack Simulation and Expression Parsing

  • Trigger: nested expressions, calculators, decoded strings, call logs, or reverse-polish tokens.
  • Move: use stacks for frames/operators; decide whether precedence is handled during scan or during unwind.

Questions:

18 - Math & Geometry - Structured String Parsing and Formatting

  • Trigger: custom numeric/string grammar, IPs, atoms, file paths, or human-readable conversion.
  • Move: write a small deterministic parser; keep token boundaries explicit.

Questions:

19 - Tries - Trie Search and Autocomplete

  • Trigger: prefix search, wildcard search, stream suffix lookup, or board word search with many words.
  • Move: build a trie; store terminal metadata; prune exhausted branches during DFS.

Questions:

20 - 1-D Dynamic Programming - Word Break Segmentation

  • Trigger: split a string into dictionary words, return possible sentences, or identify compound words.
  • Move: memoize by start index; optionally use a trie to avoid trying every word.

Questions:

21 - Graphs - Grid Flood Fill and Island Shape

  • Trigger: connected land/cells, island area/count/perimeter/closedness/distinct shape.
  • Move: DFS/BFS from each unvisited cell; mark immediately; encode shape when identity matters.

Questions:

22 - Graphs - Multi-Source Grid BFS

  • Trigger: nearest gate/zero/land/infection time, or shortest bridge from all frontier cells.
  • Move: seed queue with all sources at distance 0; expand level by level.

Questions:

23 - Graphs - Implicit State Shortest Path

  • Trigger: each state is not just a node; it can include word, board layout, bus route, key count, or obstacle budget.
  • Move: BFS over state tuples; visited must include the full state dimensions.

Questions:

24 - Graphs - Graph Components: Tree, Clone, Connected

  • Trigger: graph must be cloned, validated as a tree, counted by component, or searched through weighted relationships.
  • Move: build adjacency; BFS/DFS/Union-Find; for tree, require edges === n - 1 plus connectivity.

Questions:

25 - Graphs - Union-Find Entity Merge

  • Trigger: items are equivalent by shared email/name/row/column/string transform.
  • Move: union identifiers, then group by root; choose stable representatives carefully.

Questions:

26 - Graphs - Graph Coloring and Bipartition

  • Trigger: split nodes into two compatible groups or detect odd cycles.
  • Move: BFS/DFS color each component; conflict means impossible.

Questions:

27 - Advanced Graphs - Topological Order from Dependencies

  • Trigger: course order, alien language order, sequence reconstruction, or prerequisite waves.
  • Move: build directed graph plus indegrees; Kahn’s BFS gives order and cycle detection.

Questions:

28 - Trees - Tree Serialization and Structural Identity

  • Trigger: encode/decode trees, compare subtrees, or detect duplicate structures.
  • Move: choose preorder with null markers, level-order with nulls, or postorder structural signatures.

Questions:

29 - Trees - Tree Postorder Gain DP

  • Trigger: answer depends on child contributions but the current node decides whether to extend or close a path.
  • Move: return one value upward; update global answer with the best closed shape at the node.

Questions:

30 - Trees - Tree Views and Coordinate Traversal

  • Trigger: vertical order, right side, boundary, zigzag, distance-k, or level-based projection.
  • Move: BFS with coordinates/levels, or DFS with first-seen/ordered buckets.

Questions:

31 - Trees - BST Ordered Iteration and Repair

  • Trigger: kth/successor/iterator/delete/recover operations depend on inorder order.
  • Move: use inorder traversal, explicit stack iterator, or carry predecessor pointers.

Questions:

32 - Trees - Binary Tree Construction

  • Trigger: rebuild a tree from traversals, preorder strings, or sorted input.
  • Move: pick root from preorder/postorder, split by inorder index, recurse on ranges instead of slicing arrays.

Questions:

33 - Linked List - Linked List Rewiring

  • Trigger: nodes have random pointers, child pointers, circular order, or need cross-list identity.
  • Move: interleave clones, flatten in DFS order, or carefully preserve next pointers before mutation.

Questions:

34 - Linked List - Linked List Reversal and Runner

  • Trigger: reverse whole list, reverse a segment, k-group reverse, reorder, palindrome, nth-from-end, or cycle.
  • Move: combine fast/slow, dummy node, and prev/curr/next reversal.

Questions:

35 - Arrays & Hashing - In-Place Index Marking

  • Trigger: array values are in 1..n and the question asks missing/duplicate/first positive.
  • Move: use index-as-bucket by sign flipping, swapping into correct position, or cycle detection.

Questions:

36 - Binary Search - Binary Search on Answer

  • Trigger: minimize/maximize a numeric answer where a feasibility function is monotonic.
  • Move: binary-search capacity/time/largest sum; write can(x) first.

Questions:

37 - Binary Search - Search in Shifted, 2D, or Unknown Space

  • Trigger: sorted data is rotated, matrix-shaped, mountain-shaped, or has unknown size.
  • Move: define which half or direction is still sorted/valid, then discard the impossible half.

Questions:

38 - Backtracking - Backtracking with Duplicate Control

  • Trigger: enumerate combinations/permutations/subsets/board placements, often with duplicate input.
  • Move: sort first; skip duplicates at the same depth; for boards, mark/unmark on the current recursion path.

Questions:

39 - 2-D Dynamic Programming - Palindrome Center and Interval DP

  • Trigger: palindrome substrings, cuts, subsequences, or minimum insertions.
  • Move: use expand-around-center for substrings; use interval DP when characters at both ends interact.

Questions:

40 - 1-D Dynamic Programming - Prefix-Index DP

  • Trigger: count ways, minimum cost, or validity for a prefix of a sequence.
  • Move: let dp[i] mean answer for prefix ending at i; transition from the few legal previous positions or choices.

Questions: