videos explaining fundamental probability ideas).
- Interactive: Khan Academy – Probability (online course) covers everything from simple events to Bayes’
theorem with practice problems. For statistics basics (like expectation and variance), the “Statistics and
Probability” section on Khan Academy can be helpful too.
- Text/Reference: Probability for Computer Science by David Morin (free PDF) – good for a deeper
understanding if needed, though likely more than required for interviews.
Example Applications: Probability-related questions in interviews are often tied to algorithms. A common
example is “Shuffle an Array” (LeetCode) which expects an implementation of the Fisher-Yates shuffle,
ensuring each permutation is equally likely 12 . Another is reservoir sampling – e.g. “Linked List Random
Node” or similar problems where you must pick a random element from a stream or list with equal
probability. Understanding conditional probability can help with puzzle questions (like the famous Monty
Hall problem or card-draw problems), though such puzzles are less frequent in pure coding interviews.
Expected value appears in analyzing algorithms like randomized QuickSort (expected $O(n \log n)$ time) or
skip lists (expected balanced height). In summary, know how to apply probability in algorithmic contexts: to
prove correctness of random shuffles, to calculate probabilities in combinatorial outcomes, or to compute
expected results (e.g. expected number of trials for a random process).
Discrete Math Foundations (Recurrences & Sets)
Why it matters in DSA: Discrete mathematics is the backbone of computer science reasoning 18 . For
coding problems, two discrete math areas are especially relevant: recurrence relations (which model
recursive algorithms and dynamic programming) and basic set theory/logic (which underpins
understanding of collections, power sets, and relations). Mastering recurrences helps you break down and
solve recursive or divide-and-conquer problems by finding patterns or formulas, and analyze time
complexity for recursive algorithms. Set theory basics (elements, subsets, unions, intersections) come up
when reasoning about combinations of data or using data structures like sets/maps. They also form the
language for problems asking about relations or grouping (though the math is usually straightforward).
Must-Know Concepts: Recurrence relations – understand how to formulate a recurrence for the running
time or solution count of a recursive algorithm. For example, the recurrence $T(n) = 2T(n/2) + n$ describes
Merge Sort’s time complexity 19 , and $F(n) = F(n-1)+F(n-2)$ describes the Fibonacci sequence. Know how to
identify base cases and solve simple recurrences by unrolling or using known formulas (e.g. $T(n)=2T(n/
2)+n$ solves to $O(n \log n)$ by the Master Theorem). For dynamic programming, recognizing a recurrence
(like the way “Climbing Stairs” or Fibonacci has $dp[n]=dp[n-1]+dp[n-2]$) is crucial. Also understand
mathematical induction at a high level – it’s a method to prove the correctness of recurrences or
combinatorial formulas (useful if you need to justify a DP solution’s correctness).
For set theory basics, know definitions: what sets, subsets, and power sets are (e.g. power set of an $n$-set
has $2^n$ subsets), union and intersection operations, and the principle of inclusion-exclusion in set
terms (e.g. $|A\cup B| = |A|+|B| - |A\cap B|$). This is mostly intuitive in coding contexts – for example,
ensuring you don’t double-count elements when combining results from two sets of possibilities 20 . Basic
logic (AND, OR, NOT, implications) is also part of discrete math, though in coding interviews it usually comes
down to writing correct boolean expressions and understanding conditions.
Nice-to-Know: The Master Theorem (as mentioned) is a quick method for solving many divide-and-
conquer recurrences 21 – nice for analyzing algorithm complexity, though not needed to solve coding
