31 articles
Learn how to split a linked list into k roughly equal parts in O(n) time using integer division and remainder math. A clean medium interview problem asked at Amazon and Facebook that tests linked list traversal and arithmetic reasoning.
Count primes below n sounds trivial — until your naive solution times out on n=5,000,000. Master the Sieve of Eratosthenes, one of the most elegant algorithms in all of computer science, and learn the exact intuition that separates candidates who pass Amazon and Google screens from those who do not.
LeetCode 268 — asked at Amazon, Microsoft, and Google. Find the missing number from 0 to n using the Gauss sum formula in O(n) time and O(1) space. Alternatively use XOR for a bit-manipulation approach. Both are classic array interview questions at FAANG companies.
LeetCode 462 — asked at Amazon, Meta, and Google. Find the minimum number of moves to equalize all array elements where each move increments or decrements one element by 1. The optimal target is the median — provable by absolute deviation minimization. O(n log n) time.
LeetCode 149 asks you to find the maximum number of collinear points on a 2D plane. The trick is representing slope as a GCD-reduced integer fraction — no floats, no precision bugs — and using a HashMap to count how many points share the same slope relative to each anchor. This post covers the full intuition, a step-by-step visual dry run, every edge case (vertical lines, duplicates, sign normalization), well-commented Python and JavaScript solutions, and the real FAANG follow-up questions that separate good candidates from great ones.
Compute the integer square root (floor) of x using right-boundary binary search. Find the largest k where k*k <= x, understand the upper-mid trick, and learn why this is the mirror image of the left-boundary template.
LeetCode 268 Missing Number: find the one missing integer in [0..n] using XOR cancellation or the Gauss arithmetic-series formula. Two O(n) techniques every FAANG interviewer expects you to compare.
LeetCode 264 (Medium) — generate the n-th ugly number using a min-heap with a dedupe set or a three-pointer DP merge that runs in pure O(n).
Master mathematical algorithms for FAANG DSA interviews: primes, GCD, modular arithmetic, fast exponentiation, combinatorics, and number theory with complexity reference and full problem index.
LC 204 Count Primes is the gateway sieve problem at Google and Amazon. Master the Sieve of Eratosthenes, understand why you start marking at p*p, and apply the technique to interval queries, prime factorization, and every sieve variant an interviewer can ask.
LC 1979 Find Greatest Common Divisor of Array is the entry point to GCD problems at Google and Meta. Master the Euclidean algorithm in O(log n), compute LCM without overflow, and apply extended GCD for modular inverse.
Modular arithmetic powers nearly every competitive programming problem and is foundational at Google, Stripe, and any system that handles big numbers. Master binary exponentiation in O(log n), modular inverse via Fermat little theorem, and the modulo identities that prevent overflow on the hot path.
Prime factorization is the workhorse of number-theoretic interview problems at Amazon and Microsoft. Master trial division in O(sqrt n), the smallest-prime-factor sieve for batched factorization in O(log n) per query, and the divisor-counting tricks they unlock.
Eulers totient function phi(n) counts integers up to n coprime to n and underpins RSA, modular inverse for composite moduli, and Eulers theorem. Master the prime-factorization formula, the sieve variant in O(N log log N), and the multiplicative-function tricks that make phi indispensable for competitive programming.
Computing C(n, r) modulo a prime appears in nearly every counting problem at Google and Meta. Master Pascal triangle for small n, precomputed factorials with modular inverse for n up to 10^6, and Lucas theorem for n up to 10^18.
Number theory basics — divisibility, congruences, digit DP, perfect numbers — power half of the math problems at Amazon and Microsoft. Master the divisibility rules, modular congruence properties, and digit-extraction tricks before tackling advanced number theory.
Matrix exponentiation collapses any linear recurrence into O(log n) by raising a transition matrix to the n-th power. Master Fibonacci, k-th order recurrences, and DP optimization tricks that let you answer queries with n up to 10^18 in milliseconds.
Bit manipulation is the cheat code of competitive programming and tier-1 interviews. Master the XOR identities, n & (n-1) tricks, subset enumeration over a bitmask, and bitmask DP techniques that turn O(2^n) brute force into elegant constant-factor wins.
Recognising classical number sequences — Fibonacci, Catalan, triangular, Pascal-derived — is the difference between a 30-minute brute force and a 5-minute closed form. Master the recurrences, generating functions, and combinatorial interpretations every interviewer expects you to know.
Learn the Chinese Remainder Theorem from scratch. Understand the math, build CRT from extended GCD, handle non-coprime moduli, and ace cryptography and competitive programming interview questions.
Master square root decomposition for range sum, range minimum, and Mo's algorithm. The simplest range-query data structure that beats brute force for competitive programming and interviews.
Avoid silent overflow bugs and floating-point traps. Learn safe multiplication, modular arithmetic, BigInt, integer square root, and binary search on the answer for competitive programming and interviews.
Solve probability DP problems used by quantitative interviews. Master expected value recurrences, geometric distribution, knight probability, and the soup servings memoization trick.
Master the computational geometry primitives every interviewer expects: cross product orientation, segment intersection, Graham scan convex hull, polygon area via shoelace, and point in polygon.
Master combinatorial game theory: Nim XOR strategy, Grundy numbers, Sprague-Grundy theorem, mex, and minimax DP for stone games and impartial games in competitive programming and interviews.
Master randomized algorithms in interviews: reservoir sampling for streams, quickselect for O(n) kth element, Fisher-Yates shuffle, and Bloom filters with probability proofs.
Apply the inclusion-exclusion principle to divisibility counting, derangements, Euler totient, and surjection problems. The single most useful tool for combinatorial counting in interviews and competitive programming.
Complete reference for math and number theory DSA patterns: algorithm selection guide, complexity table, template library, and top 25 interview problems ranked by FAANG frequency.
Evaluate a Reverse Polish Notation expression by pushing operands and applying operators to the top two stack elements in O(n) time. The canonical stack-based expression evaluation problem asked at Amazon, LinkedIn, and Microsoft.
Calculate the score of a balanced parentheses string where () = 1 and (A) = 2*A using a stack and an elegant O(1) space depth-doubling trick. A FAANG medium problem that rewards deep thinking with a beautiful bit-shift optimization.
How to derive the OLS Estimator with matrix notation and a tour of math typesetting using markdown with the help of KaTeX.