Coding Interview Flow

a cheatsheet I printed out for reference during coding interviews


Relax, Beginner’s Mind - Don’t rush, don’t try to compare to problem I have seen!

FRONTEND INTERVIEWS:
Clarifying at beginning

  • How important is styling/CSS or is core functionality the focus?
  • Should I go with straightforward markup/scripting or built a re-usable component?
  • Create two buckets: What are the core requirements for the time we have?
  • What are the optimizations (if time allows), nice-to-haves, future features. (If no time to implement, briefly explain how you’d go about it.)

Pseudocoding / Skeletoning

  • Verbalize your approach (eg “I’ll do the HTML first and add the interactivity later”)
  • Write up comments on overall approach, step by step.
  • Skeleton out some named functions or classes, add comments there.
  • Focus on the hard part, potentially skip over rote work (interviewer may let you pretend you have a library func that handles it).

ALGORITHM INTERVIEWS:
Clarifying at beginning

  • Inputs: what kind? How many?
  • Output: what is it?
  • Constraints: input constraints; time/space complexity constraints. Should we mutate the input, or not?
  • Edge cases: Empty/null input? Unexpected values? How handle?
  • Repeat problem back to interviewer.
  • Simplify input, if it is too complex.

Steps

  • Brute force. Pseudocode it. State time/space.
  • Identify choices explicitly. Make time/space tradeoffs.
  • Optimize*. A DS or Algo. Pseudocode it. State time/space.
  • Check in: "Before I pursue this approach, is there anything I should consider or do you have any questions about it?"
  • Walk through given example input.
  • Implement. Skeleton it out with named func/vars first. Prioritize harder parts.
  • Test / Dry Run.
  • Time/Space Discussion if needed here at the end.

Array Clarifying Questions

  • If an array (or a range 0...n), is it sorted? Or could we sort it? What does that mean?
    • Sorted: Pointers (1 or 2), or 1 pass?
    • Sorted: Binary Search possible
  • Sliding window? Discard old, incorporate new. (strings too)
  • Fixed sliding window? Variable sliding window? (strings too)

Permutations/Combinations/Sets:

  • Get very clear on what we’re talking about.
  • Perms: Order matters. Repeat allowed OR not allowed?
  • Combos: Order doesn’t matter, repetition is not allowed.
  • Sets: combos that are “bags” of ‘empty set’ up to max string/num length.
  • Tree-like “problem space”
  • Template: series of blanks (partial soln) and subprob passed to recursive ‘manager’ who does one thing. Base case: subprob size is 0.

DP / Counting / with Memoization

  • Counting combinations style problems. What are the options at each step? Are there two options (stairs, grid moves) or a list of them (coin change).
  • Base Case returns 0 or 1. Add up the count. Memoize for performance.

Tree Clarifying Questions

  • What kind of tree, and what does that mean?
    • Binary Tree
    • Binary Search Tree - lefts smaller than rights. Inorder = sorted.
    • BST - is it balanced?
    • N-ary Tree (Hierarchical Tree).
    • Tries - n-ary. Each path represents a word, e.g. a dictionary.
  • Tree Approaches
  • Traversal: BFS (levels matter), DFS
  • N-ary tree traversal: BFS or DFS but iterating over children (to q or DFS stack)
  • Top Down DFS - can the result be passed up to global variable?
  • Bottom Up DFS - do we need info passed up to parents?
  • Tree Construction: Top down, (left to right is doable, never studied)
  • Note: “A tree is an undirected connected acyclic graph.”

Graph Clarifying Questions

  • Connected? Unconnected? (Do I eed to handle separate components?).
  • Undirected (two-way edges) or directed (one-way edges).
  • Graph Approaches & Complexities:
  • How to model it? adjList, matrix, something else?
  • … Tackle it with DFS, BFS (layers matter)… or maybe something simpler.
  • Or maybe something more complex (haven’t studied)
  • Directed Graphs: need arrival/dep timestamps for cycle detection.
  • DAG - directed acyclic graph, allows for TOPSORT (linear ordering of vertices from left to right)

*Optimize

  • Decrease and conquer - transform prob into smaller prob I know the solution to.
  • Divide and conquer - e.g. binary search, quick select.
  • Transform and conquer - use a DS.
  • Greedy - Maximize local quantity leads to getting to the glob optimum.
  • Backtracking - incrementally building candidate solutions, then “backtracking” when it determines that a candidate violates a constraint.
  • Backtracking + memoization: special case of top down DP.
  • Heaps - WHEN YOU WANT Kth SMALLEST, USE A MAXHEAP OF SIZE K, WHEN YOU WANT kth largest or K LARGEST, USE A MINHEAP OF SIZE K.
  • Linked Lists - are great for problems that require arbitrary insertion.
  • Doubly Linked Lists - you can insert or delete elements in a linked list in constant time, as long as you know where the element is.
  • Stacks - string stacks Monotone Stacks - eg “find the closest larger/smaller element on the left/right of the curr one.