Coding Practice
#19 7 pagesCoding Practice — DSA for Backend/Infra Interviews
DSA problems that recur specifically in backend/infrastructure/platform engineering interviews — not generic LeetCode grinding. Every implementation ships in Go, Python, and Java (full, working, tested — pick whichever tab matches your interview language), matching the practitioner-notes style of the rest of DevOpsIndex. The point is to understand the systems these structures back (caches, rate limiters, sharding, dedup, and the B-trees/skip lists behind databases/ itself) rather than memorize a solution. Every file also carries the repo's standard interactive treatment — step-through walkthroughs of inserts/splits/evictions, Mermaid diagrams, and knowledge-check quizzes (see website/COMPONENTS.md) — and every structural file (all but concurrent-patterns.md) has a live simulator you can actually insert/search/delete into and watch reshape in real time, not just a diagram. Rendered on the website.
Files
| File | Covers | Live simulator | Typical interview relevance |
|---|---|---|---|
| concurrent-patterns.md | Thread-safe counter (mutex vs atomic), bounded worker pool, pub/sub via channels, debounce/throttle, goroutine/thread leak detection and fix | — | The highest-frequency category in Go-specific infra interviews; leak detection in particular is a common "find the bug" exercise |
| btree.md | B-tree vs B+tree from scratch, node-split-on-insert walkthrough, linked-leaf range scans | ✅ insert/delete/search a real order-4 B+tree | Tests whether you understand why the structure backing every Postgres/MySQL default index is disk-page-aligned rather than a plain binary tree — see databases/postgres-internals.md, databases/mysql-internals.md |
| skip-list.md | Skip list from scratch, randomized-level insert/search traversal | ✅ real randomized-level insert/delete | Tests understanding of probabilistic balancing as an alternative to rebalancing trees — this is what backs Redis sorted sets, see databases/redis-internals.md |
| lru-cache.md | LRU cache from scratch (doubly linked list + hashmap), thread-safe variant, LFU comparison, TTL eviction variant | ✅ Get/Put against a live capacity-3 cache | Extremely common — "design an in-memory cache" shows up in nearly every backend/infra loop; tests whether you understand why two data structures are needed together, not just whether you can recite the algorithm |
| rate-limiter-implementations.md | Token bucket, leaky bucket, fixed window, sliding window log — all four from scratch, plus an HTTP middleware wrapper | ✅ token bucket refilling on the real clock | Standard system-design-adjacent coding question; tests whether you can translate a system design concept (see system-design/rate-limiting.md) into working, thread-safe code |
| consistent-hashing.md | Hash ring with virtual nodes, add/remove node walkthrough | ✅ add/remove nodes on an actual ring | Comes up when discussing sharding, distributed caches, or load balancer request routing; tests understanding of why naive modulo hashing fails at scale |
| bloom-filter.md | Bloom filter from scratch, false positive rate math with a worked example | ✅ insert words, trigger a real false positive | Tests both coding ability and math/estimation skills; relevant to any "avoid expensive lookup" or dedup discussion (DB pre-checks, stream processing) |
Read Order
No strict dependency between files, but if new to Go concurrency and the underlying tree/list structures specifically, read in this order:
concurrent-patterns.md (Go concurrency primitives first)
btree.md (disk-oriented tree fundamentals — backs databases/postgres-internals.md, mysql-internals.md)
skip-list.md (probabilistic list fundamentals — backs databases/redis-internals.md)
lru-cache.md (data structure fundamentals + thread safety)
rate-limiter-implementations.md
consistent-hashing.md
bloom-filter.md
How to Use This Section
Each file is self-contained: full working code in Go, Python, and Java, a test file for each, complexity analysis, and — where relevant — an explanation of the underlying systems problem (why the naive approach fails, what production systems actually use this for). Run the code locally to verify before an interview:
# Go
go mod init practice
go test ./...
# Python
python3 -m unittest
# Java
javac *.java && java <TestClassName>
Or just open the file on the website and use the live simulator — click Insert/Delete/Search and watch the structure itself, no local setup needed.
These are deliberately not "clever one-liner" solutions. Interviewers evaluating backend/infra candidates are usually checking for production-grade instincts — thread safety, bounded resource usage, correct edge-case handling — over algorithmic cleverness. Each file's "interview follow-ups" section calls out the specific probing questions an interviewer is likely to ask next.