CodingInterviews

Coding Interviews

A. Parsing, Calculators, and String Processing

These problems usually look complicated at first glance, but they share a common core idea:

Scan the string once and use a stack (or recursion) to manage states.

Common Problems

  • Reverse Polish Notation (RPN) Calculator
  • Basic Calculator I / II
  • Decode String (e.g. 3[a2[c]])
  • String to Integer (atoi)
  • Valid Parentheses
  • Minimum Remove to Make Valid Parentheses
  • Simplify Path (Linux path normalization)

Key Techniques

  • Stack for operators and intermediate values
  • Careful handling of spaces, signs, and invalid input
  • One-pass scanning whenever possible

Interview Focus

  • Can you handle edge cases (division by zero, overflow, malformed input)?
  • Is your solution O(n)?
  • Can you clearly explain your assumptions?

Typical explanation

“This is essentially a parsing problem. I scan the string once and use a stack to maintain intermediate states.”

B. Arrays, Two Pointers, and Sliding Window (Amazon Favorite)

This category appears in almost every SDE I interview.

Common Problems

  • Two Sum
  • 3Sum (with deduplication)
  • Merge Intervals
  • Product of Array Except Self
  • Maximum Subarray (Kadane’s Algorithm)
  • Longest Substring Without Repeating Characters
  • Minimum Window Substring

Core Patterns

Pattern When to Use
Two pointers Sorted arrays, shrinking ranges
Sliding window Subarrays or substrings
Prefix scanning O(1) extra space optimization

Interview Focus

  • Why the window can expand or shrink
  • When to use a HashMap
  • How you ensure linear time complexity

Sliding window template

“I maintain a window using two pointers and a hashmap.
When the window becomes invalid, I move the left pointer until it is valid again.”

C. Hash Maps, Counting, and Top-K Problems

These problems emphasize trading space for time.

Common Problems

  • Group Anagrams
  • Top K Frequent Elements
  • First Unique Character in a String
  • Subarray Sum Equals K
  • Longest Consecutive Sequence
  • Kth Largest Element in an Array

Core Techniques

  • HashMap for frequency counting
  • Heap for Top-K problems
  • Bucket sort when constraints allow O(n)

Interview Focus

  • Can you justify the time complexity?
  • Do you handle negative numbers correctly?
  • Can you compare heap vs bucket solutions?

Typical explanation

“We can use a min-heap of size k, giving O(n log k).
If the value range is limited, bucket sort reduces this to O(n).”

D. Stack and Monotonic Stack (High-Frequency Pattern)

If the problem asks for “next greater”, “maximum area”, or “water trapping”, think monotonic stack.

Common Problems

  • Daily Temperatures
  • Next Greater Element I / II
  • Largest Rectangle in Histogram
  • Trapping Rain Water
  • Evaluate Reverse Polish Notation

Core Patterns

Problem Type Stack Strategy
Next greater element Monotonic decreasing stack
Histogram / rectangle Monotonic increasing stack
Trapping rain water Two pointers or stack

Interview Focus

  • When and why elements are popped
  • Whether the stack stores indices or values
  • Why the solution is still O(n)

Key explanation

“Each element is pushed and popped at most once, so the total time complexity is O(n).”

E. BFS, DFS, and Graph Fundamentals

Graph problems test your ability to model relationships and traversal.

Common Problems

  • Number of Islands
  • Clone Graph
  • Course Schedule I / II
  • Word Ladder
  • Graph Valid Tree
  • Shortest Path in Binary Matrix

Core Patterns

Scenario Solution
Connected components DFS or BFS
Shortest path (unweighted) BFS
Dependencies Topological sort
Graph cloning DFS + HashMap

Interview Focus

  • BFS vs DFS trade-offs
  • Avoiding repeated visits
  • Detecting cycles

Topological sort explanation

“This is a classic topological sorting problem.
We track indegrees and use BFS to process nodes with zero indegree.”

F. Linked Lists and Trees (Core Fundamentals)

These problems test pointer manipulation and recursion clarity.

Common Problems

  • Reverse Linked List
  • Merge Two Sorted Lists
  • Linked List Cycle
  • Binary Tree Level Order Traversal
  • Lowest Common Ancestor
  • Serialize and Deserialize Binary Tree

Core Techniques

  • Iterative pointer manipulation for linked lists
  • DFS / BFS for trees
  • Recursion with clear base cases

Interview Focus

  • Correct pointer updates
  • Clean recursion exits
  • Robust null handling