Thread Safety, Deadlock Prevention, and Arrays vs Linked Lists

In a rapid-fire concepts segment of a software engineering interview, the interviewer asked four short questions in a row about concurrency and basic data structures. Answer each one concisely and precisely, as you would aloud, and use a small concrete example where it makes the answer clearer. ### Clarifying Questions - Should the answers be language-neutral, or tied to the language you code in (for example, Java's `synchronized` and its memory model)? - Is the scope threads inside one process, or also separate processes and distributed locks? - How deep should each answer go: a definition and an example, or implementation details as well? ### Part 1 — Thread safety What is your understanding of thread safety? What makes a piece of code thread-safe? ```hint Start from a broken counter Picture two threads both running `count = count + 1` on the same shared variable. Work out what can go wrong, then what any fix has to guarantee. ``` #### What This Part Should Cover - A definition in terms of correct behavior when several threads use the code at the same time, without extra coordination by the callers - The problems it rules out: race conditions on shared mutable state, broken invariants, and stale or reordered reads - The main ways to achieve it and what each one costs ### Part 2 — Deadlock What is a deadlock? ```hint Two threads, two locks Describe the smallest scenario that gets stuck, then ask which properties of that scenario must all be present for it to happen. ``` #### What This Part Should Cover - A precise definition and a minimal example - The conditions that must all hold for a deadlock to occur - How deadlock differs from livelock and starvation ### Part 3 — Resolving deadlocks What methods can you think of to deal with deadlocks? ```hint Attack one condition Every condition a deadlock needs is a place where it can be broken. Also separate making deadlock impossible from noticing it and recovering. ``` #### What This Part Should Cover - Prevention by breaking one of the necessary conditions, with lock ordering and timed lock attempts as the practical cases - Avoidance, and why it is rarely used in application code - Detection and recovery, as databases do it - Engineering habits that keep deadlocks out of real code, and how to diagnose one ### Part 4 — Arrays and linked lists How do you understand arrays and linked lists? Compare how each is laid out in memory, the cost of common operations, and when you would choose one over the other. ```hint Beyond big-O Walking either structure from start to end takes linear time. Think about what the processor's cache does during each walk. ``` #### What This Part Should Cover - Memory layout: one contiguous block versus separately allocated nodes linked by pointers - Costs of access by index, search, insertion and deletion at the ends and in the middle, including amortized append on a growable array - Cache locality and per-element memory overhead - Concrete situations that favor each structure ### What a Strong Answer Covers - Precise definitions rather than loose descriptions - A concrete example behind each concept, such as a lost update on a shared counter or two threads taking two locks in opposite orders - The cost of every remedy, not just its name - Practical judgment about what you would actually use in production code - Short, well-organized answers that fit a rapid-fire format ### Follow-up Questions - A map whose individual methods are all synchronized is used as "if the key is absent, insert it". Is that sequence thread-safe? Why or why not? - How would you find the cause of a deadlock in a service that is hung in production? - Lock ordering is easy with two fixed locks. How do you apply it when the locks are chosen at run time, such as a transfer between two accounts? - Why can walking a linked list be several times slower than walking an array of the same length, even though both are linear?