Coding & CS Fundamentals: real interview questions

Talk pointers out loud: three references (prev, curr, next), advance carefully, return prev. Mention the recursive variant and its stack cost.

Iteratively: keep prev (starts null) and curr (starts head). Each step: save curr.next, point curr.next at prev, advance prev=curr, curr=saved. When curr is null, prev is the new head. O(n) time, O(1) space. The recursive version is elegant — reverse(rest) then head.next.next = head — but costs O(n) stack and risks overflow on long lists, which is exactly the kind of trade-off worth saying out loud. The interviewer usually cares less about the code than whether you can narrate pointer surgery without losing a node: the classic bug is overwriting curr.next before saving it.

Cover hashing to buckets, collision handling (chaining vs open addressing), load factor and resizing, and why keys must be immutable/consistent in hashCode-equals.

A hash map hashes the key to an index in a bucket array. Collisions (two keys, one bucket) are handled by chaining (a list/tree per bucket — Java upgrades long chains to red-black trees) or open addressing (probe for the next slot, like Python's dict). As entries grow past the load factor (~0.75), the array doubles and everything rehashes — that's the amortized cost behind 'O(1)'. Worst case degrades to O(n) with adversarial collisions, which is why hash functions get randomized/seeded. Two practical gotchas worth mentioning: mutating a key after insertion strands the entry (its hash no longer matches its bucket), and equals/hashCode must agree or lookups silently fail.

Refuse the false binary: choose per workload. Name the concrete deciding factors — transactions, query flexibility, scale pattern, consistency needs.

Default to relational: ACID transactions, ad-hoc querying, joins, and mature tooling cover most products, and Postgres scales further than people assume. Reach for NoSQL when a specific pressure justifies it: key-value/wide-column for massive single-key throughput with known access patterns (session stores, feeds), document stores when entities are naturally self-contained aggregates, search/vector/graph engines for their specialized queries. The real question is what you're willing to give up — NoSQL typically trades joins, transactions, and flexible queries for horizontal scale and predictable latency. I'd also say the unsexy truth: many systems use both — Postgres as source of truth, Redis and a search index as derived views.

Show a methodical funnel: measure first (never guess), isolate the layer, fix the dominant cost, verify. Name real tools at each step.

First, quantify: is it slow for everyone or p99 only? Check the endpoint's latency dashboard and recent deploys. Then trace one slow request end-to-end (distributed tracing) to see where time goes — app code, database, external calls, or queueing. In my experience it's usually the database: I'd pull the queries (APM or slow-query log), EXPLAIN the worst one, and typically find a missing index or an N+1 pattern — fix, then re-measure. If it's downstream calls: add timeouts, parallelize independent calls, cache. If it's CPU: profile with a flame graph. The discipline is the answer: measure → isolate → fix the biggest cost → prove it with the same metric you started with.

Define it in one sentence, then spend the time on a concrete example (check-then-act) and layered prevention: atomicity, locks, idempotency.

A race condition is when correctness depends on the timing of concurrent operations. The classic: two requests both read balance=100, both approve a 100 withdrawal, both write — the account goes negative. That's check-then-act without atomicity. Prevention, in order of preference: make the operation atomic in the data layer (UPDATE ... SET balance = balance - 100 WHERE balance >= 100 — the row lock does the work), use explicit locking (SELECT ... FOR UPDATE) for multi-step invariants, or optimistic concurrency (version column, retry on conflict) when contention is low. In distributed systems add idempotency keys so retries don't double-apply. The interview win is showing you push atomicity down to the database instead of sprinkling app-level locks.

Skip the textbook; tell a story where complexity became an outage or a cost, and show you think in growth rates about real data sizes.

Big-O is about how cost grows with data — and production data always grows. Real example: an endpoint that checked each incoming item against a list with a nested loop. At 100 items it was invisible; at 50k items it was O(n²) = 2.5B comparisons and the endpoint started timing out — months after shipping, because the data grew into the complexity. The fix was a set lookup: O(n). That's the practical lesson I'd offer: complexity bugs are time bombs that pass code review and tests on small data. I now ask 'what's n today, and what's n in two years?' for any loop-in-loop, and I treat sorting inside a request handler as a smell worth checking.