Last active 5 days ago

Interview prep notes

linkjobai revised this gist 5 days ago. Go to revision

1 file changed, 44 insertions

segtree.md(file created)

@@ -0,0 +1,44 @@
1 + # Segment Trees for Interviews: Range Queries with Updates
2 +
3 + Prefix sums answer range-sum queries in O(1), but a single update costs O(n). When a problem mixes **point updates and range queries** (LeetCode 307, Range Sum Query - Mutable), a segment tree gives O(log n) for both.
4 +
5 + ## Iterative segment tree (compact version)
6 +
7 + ```python
8 + class SegTree:
9 + def __init__(self, nums):
10 + self.n = len(nums)
11 + self.t = [0] * (2 * self.n)
12 + self.t[self.n:] = nums
13 + for i in range(self.n - 1, 0, -1):
14 + self.t[i] = self.t[2 * i] + self.t[2 * i + 1]
15 +
16 + def update(self, i, val):
17 + i += self.n
18 + self.t[i] = val
19 + while i > 1:
20 + i //= 2
21 + self.t[i] = self.t[2 * i] + self.t[2 * i + 1]
22 +
23 + def query(self, l, r): # inclusive l..r
24 + res, l, r = 0, l + self.n, r + self.n + 1
25 + while l < r:
26 + if l & 1: res += self.t[l]; l += 1
27 + if r & 1: r -= 1; res += self.t[r]
28 + l //= 2; r //= 2
29 + return res
30 + ```
31 +
32 + Swap `+` for `min`, `max` or `gcd` to support other associative operations.
33 +
34 + ## When an interviewer expects it
35 +
36 + - Range updates *and* range queries: mention **lazy propagation**.
37 + - Counting inversions or "count of smaller numbers after self" (315): a segment tree or Fenwick tree over value ranks.
38 +
39 + ## Fenwick tree comparison
40 +
41 + A Fenwick (binary indexed) tree is shorter to write and enough for prefix sums, but a segment tree handles min/max and lazy range updates more naturally. Saying which you'd pick and why is often worth more than the code.
42 +
43 + ---
44 + *Disclosure: I work on [Linkjob.ai](https://www.linkjob.ai/), which offers real-time interview help.*
Newer Older