1. Big-O Complexity

Why Interviewers Care

Every FAANG solution requires a complexity analysis at the end. If you can't state and justify the Big-O of your solution, you will not pass — even if the code is correct.

Key Complexity Classes

Complexity	Meaning	Example
$O(1)$	Constant — independent of input size	Hash map lookup
$O(\log n)$	Halves the problem each step	Binary search
$O(n)$	One pass through all elements	Linear scan
$O(n \log n)$	Sort, or $n$ heap operations	sorted(), merge sort
$O(n^2)$	Nested loop	Brute force pair search
$O(2^n)$	Every subset	Recursive subset generation
$O(n!)$	Every permutation	Recursive permutation generation

# O(1) — hash map lookup, array index access
d = {1: "a", 2: "b"}
val = d[1]          # O(1)
arr = [10, 20, 30]
x   = arr[2]        # O(1)

# O(log n) — binary search
import bisect
idx = bisect.bisect_left([1,3,5,7,9], 5)   # O(log n)

# O(n) — single loop
total = sum(range(1000000))    # O(n)

# O(n²) — nested loop (often avoidable with hashing)
def has_pair_slow(arr, target):
    for i in range(len(arr)):
        for j in range(i+1, len(arr)):    # O(n²) — avoid when n > 10,000
            if arr[i] + arr[j] == target:
                return True
    return False

def has_pair_fast(arr, target):
    seen = set()
    for x in arr:                         # O(n) — use a hash set
        if target - x in seen:
            return True
        seen.add(x)
    return False

---

Conceptual Q&A

Q1: "What is the time complexity of this function? How would you improve it?"

def find_common(list_a: list, list_b: list) -> list:
    result = []
    for a in list_a:
        if a in list_b:      # ← what is this line's complexity?
            result.append(a)
    return result

Walkthrough:

"Let me analyse line by line. The outer loop runs $n$ times (length of list_a). The in operator on a list is $O(m)$ where $m$ = length of list_b — it scans every element. So overall: $O(n \times m)$, or $O(n^2)$ if both lists are the same size.

To improve this, I'd convert list_b to a set before the loop. Set membership is $O(1)$ average, so the total becomes $O(n + m)$ — linear."

def find_common_fast(list_a: list, list_b: list) -> list:
    set_b = set(list_b)          # O(m) to build
    return [a for a in list_a if a in set_b]   # O(n) total

---

Q2: "Your solution is O(n log n). The interviewer asks: can you do better?"

Walkthrough:

"I should ask: is the input sorted? If yes, $O(n)$ might be achievable. If not, I need to consider whether the problem requires ordering — if it does, $O(n \log n)$ may be a lower bound. I should reason through: what information must I gather to produce the answer? If I must look at every element once, $O(n)$ is optimal."

---