Classic Coding Patterns

What you'll learn

• Python Data Structure Hacks

• defaultdict — Auto-Initialize Keys

• dict.get() vs dict.setDefault()

• Set Operations

• Deque Complexity Table

  | Method | Time | Space | |--------|------|-------| | append() | O(1) | O(1) | | appendleft() | O(1) | O(1) | | pop() | O(1) | O(1) | | popleft() | O(1) | O(1) | | index(ele, beg, end) | O(N) | O(1) | | insert(i, a) | O(N) | O(1) | | rem…

• Key Definitions

  - SubString / Subarray: Consecutive elements — order AND contiguity mandatory - SubSequence: Order preserved but elements need NOT be contiguous - Subset: Any selection of elements — order does NOT matter. For [a,b,c]: [a,c] and [c,a] ar…

• Stack-Based Problems

• Validate Balanced Brackets

  Given a string containing bracket characters, determine if it's valid. Rules: each open bracket must be closed by same type in correct order. Approach: Use a stack. Push opening brackets. When encountering a closing bracket, check if sta…

• Array Manipulation

• Find the Next Lexicographic Arrangement

  Given an array of integers, rearrange into the next lexicographically greater permutation. If already the largest, rearrange to the smallest. Algorithm: 1. Traverse from RIGHT — find first index i where arr[i] arr[i] 4. Swap arr[i] and a…

• Group Strings by Character Composition

  Given a list of strings, group strings that are composed of the same characters (same letters, same frequency). Approach: Sort each string's characters and use as a dictionary key. Strings with the same sorted form are grouped together.…

• Merge Overlapping Intervals

  Given a collection of intervals [start, end], merge all overlapping ones. Approach: Sort by start time. Iterate: if current interval's start ≤ previous end, extend previous end. Otherwise start new interval. Key Insight: Sorting guarante…

• Maximum Profit from Single Transaction

  Given daily prices, find the maximum profit from buying and selling once (must buy before selling). Approach: Track minimum price seen so far. At each step, compute profit if selling today. Key Insight: Single pass O(n). Don't need to tr…

• Bit Manipulation

• Find the Unique Element

  Given an array where every element appears twice except one, find the unique element. Must be O(n) time, O(1) space. Approach: XOR all elements. Duplicate pairs cancel out (x ^ x = 0), leaving only the unique one. Key Insight: XOR is ass…

• Data Structure Design

• Least Recently Used Cache

  Design a cache with O(1) get and put operations. When capacity exceeded, evict the least recently used item. Data Structures: HashMap (key→node) + Doubly Linked List (ordered by recency). Operations: - get(key): Look up in map → remove n…

• Binary Search Variants

• Find Minimum in a Rotated Sorted Array

  A sorted array has been rotated 1-n times. Find the minimum element in O(log n). Key Condition: If arr[mid] Key Insight: Compare with the last element, not the first. The last element is always less than elements in the rotated portion.

• Check for Duplicate Elements

  Given an array, return true if any value appears at least twice. Approach: Use a set. If element already exists in set, return true. Complexity: O(n) time, O(n) space. Alternative: sort first O(n log n) with O(1) space. ---

• Tree Problems

• Lowest Common Ancestor in a Binary Tree

  Given a binary tree and two nodes p and q, find their lowest common ancestor (the deepest node that has both p and q as descendants). Approach: Recursive DFS. If current node is p or q, return it. Recurse left and right. If both subtrees…

• Sliding Window & Monotonic Deque

• Maximum in Every Window of Size K

  Given an array and window size k, return the maximum value in each window position. Approach: Use a monotonic decreasing deque storing (value, index) pairs. Leftmost element is always the current maximum. Key Insight: Monotonic deque ens…

• Prefix Sum

• Core Concept

  A prefix sum array stores cumulative sums where prefix[i] = sum of elements from index 0 to i. This allows O(1) range sum queries after O(n) preprocessing.

• Pattern: Subarray with Target Sum

  Given an array, determine if any contiguous subarray sums to a target value. Use a running prefix sum and a HashSet to check if (prefixSum - target) was seen before. Why this works: If prefix[j] - prefix[i] == target, then the subarray f…

• Pattern: Maximum Sum Subarray of Fixed Length K

• Pattern: Equilibrium Index

  Find an index where the sum of elements on the left equals the sum on the right. With prefix sums: prefix[i-1] == prefix[n-1] - prefix[i].

• 2D Prefix Sums

  For matrix range queries, extend to 2D: Key Insight: Prefix sums transform range sum queries from O(n) to O(1) at the cost of O(n) preprocessing space. ---

• Segment Tree

• When to Use

  Use a Segment Tree when you need both: 1. Range queries (sum, min, max over a range) 2. Point updates (modify individual elements) Prefix sums give O(1) queries but O(n) updates. Segment Trees give O(log n) for both.

• Implementation (Iterative, Array-Based)

• Storage Layout

  The tree is stored in a flat array of size 2 n: - Internal nodes: indices [1..n-1] - Leaves: indices [n..2n-1] (map directly to original array elements) - Parent of node i: i // 2 - Children of node i: 2i (left), 2i+1 (right)

• Example: Sum of Smaller Elements Seen So Far

  Given an array, for each element compute the sum of all previously seen elements that are smaller. Uses coordinate compression + segment tree.

• Segment Tree vs Alternatives

  | Structure | Query | Update | Build | Use When | |-----------|-------|--------|-------|----------| | Prefix Sum Array | O(1) | O(n) | O(n) | Static array, many range queries | | Segment Tree | O(log n) | O(log n) | O(n) | Dynamic update…

• DSA Problem Pattern Recognition

  When approaching a new problem, match the pattern to select your approach:

• Array/String Patterns

  | Signal in Problem Statement | Pattern to Apply | |----------------------------|-----------------| | "Find pair/group satisfying condition" | HashMap/HashSet for complement lookup | | "Rearrange in specific order" | Sorting (often custo…

• Advanced Patterns

  | Signal in Problem Statement | Pattern to Apply | |----------------------------|-----------------| | "Minimum coins/steps/cost" (optimal substructure) | Dynamic Programming | | "Can we do it?" + optimal substructure + greedy choice | Gr…

• Design Problems

• Snake Game Simulation

  Design a snake game. The snake moves on a grid, grows when eating food, dies when hitting wall or itself. Data Structure: Deque for snake body (head at front, tail at back). Set for O(1) body collision detection.

• Rate-Limited Logger

  Design a logger that prints a message only if the same message hasn't been printed in the last 10 seconds. Key Insight: Store next-allowed timestamp per message. O(1) per call.

• Event Counter (Hits in Last 5 Minutes)

  Design a counter tracking events in the past 300 seconds. Approach 1 — Deque (unbounded memory if many events): Approach 2 — Circular Buffer (fixed O(300) memory, scales with high traffic): Trade-off: Deque is simpler but unbounded. Circ…

• Greedy & Math

• Count Complete Staircase Rows

  Given n coins, build a staircase where row i has exactly i coins. Return the number of complete rows. Approach: Greedily subtract 1, 2, 3, ... until you can't complete the next row.

• Count Valid Arrangements (Backtracking)

  Given n integers labeled 1 to n, count permutations where for every position i: either perm[i] divides i, or i divides perm[i]. Approach: Backtracking with pruning — only try placing number at position if divisibility condition is met. K…

• String Parsing

• Delimited Text Parser (Progressive Complexity)

  Design a function that parses delimited text (e.g., CSV) into structured data. This is a classic interview problem because it starts simple and adds complexity through follow-ups. Base Problem: Parse a delimited string where the first ro…

• Follow-up 1: Error Handling

  Questions to ask: - On error: partial save or complete failure? - Should errors be collected and reported all at once (so user can fix all in one pass), or fail on first error? - Any normalization needed (e.g., case-insensitive headers)?…

• Follow-up 2: Quoted Fields with Commas

  Handle fields that contain the delimiter character, wrapped in quotes: 4,"the, new, pixel!",5 → should parse as three fields: 4, the, new, pixel!, 5 Questions to ask: - Can we assume values with commas are always quoted? - Can we assume…

• Follow-up 3: Multi-line Quoted Fields

  Handle quoted fields that span multiple lines: Should parse as: 4, the\npixel!, 5 Questions to ask: - Can we assume multi-line values are always quoted? - Can header lines also be multiline? Key change: You can no longer split by line de…

• Bit Manipulation

• Binary Number System

  Computers use base-2 (binary). Each bit position represents a power of 2:

• Two's Complement (Negative Numbers)

  In two's complement, the most significant bit (MSB) represents a negative value: Why two's complement? - Only one representation of zero (unlike sign-magnitude which has +0 and -0) - Addition/subtraction hardware works identically for po…

• Bitwise Operators

  | Operator | Symbol | Rule | Example (5=0101, 6=0110) | |----------|--------|------|--------------------------| | OR | \| | 1 if either bit is 1 | 5 \| 6 = 0111 = 7 | | AND | & | 1 only if both bits are 1 | 5 & 6 = 0100 = 4 | | XOR | ^ |…

• Bit Shifting

  | Type | Symbol | Behavior | Effect | |------|--------|----------|--------| | Left shift | > | Shift right, copy MSB (sign bit) | Divide by 2^n (preserves sign) | | Logical right | >>> | Shift right, fill left with 0 | Divide unsigned; m…

• Common Bit Operations (Building Blocks)

• Power of Two Check

  All powers of two have exactly one bit set:

• Count Set Bits (Brian Kernighan's Algorithm)

• Useful Bit Tricks

  | Operation | Expression | Why It Works | |-----------|-----------|--------------| | Get lowest set bit | n & (-n) | -n is two's complement: flips bits and adds 1 | | Clear lowest set bit | n & (n-1) | n-1 flips all bits up to and includ…