Cracking the Backup Dependency Management System — LLD Interview Deep Dive

Asked at Rubrics · Java Multithreading · Senior / L5 · ~18 min read

Most candidates prepare for LLD rounds by memorizing solutions. Senior engineers get hired by demonstrating how they think. This post teaches you both — the reasoning behind every decision, and the code that follows from it.

Table of Contents

1. Understand the problem before writing a single line
2. Build the right mental model
3. Choosing your data structures
4. The concurrency layer — this is where most people fail
5. API design and algorithms, one by one
6. The complete implementation
7. Complexity analysis
8. Common interview pitfalls
9. Follow-up questions and how to answer them

The Problem Statement

Design and implement a thread-safe backup dependency management system that supports:

• Adding backup dependencies
• Finding recovery chains for Point-In-Time (PIT) restore
• Expiring old backups based on a retention policy

Backup types:

Prefix Type Example f Full backup (root) f1 d Differential d1 i Incremental i1, i2

Dependency chain example:

f1 → d1 → i1 → i2

Meaning: d1 depends on f1, i1 depends on d1, i2 depends on i1. To restore i2, the entire ancestor chain is required.

Three APIs to implement:

add_dependency(backup_id, dependent_id, retention, end)
find_recovery_chain(backup_id, pit)
expire_backups(current_time)

1. Understand the Problem Before Writing a Single Line

The first thing a strong LLD candidate does is not start coding. They ask questions, restate the problem in their own words, and verify their understanding aloud. This signals seniority.

Here is how you should open with your interviewer:

“So we’re modelling a backup dependency graph — each backup has a parent it depends on. To restore to a point in time, I need to reconstruct the ancestor chain up to that timestamp. Backups also have an expiry window after which they should be cleaned up. And all of this needs to work safely across multiple threads. Does that sound right?”

This one paragraph tells the interviewer you understand: the graph structure, traversal direction, PIT semantics, retention lifecycle, and the concurrency requirement. You’ve also bought yourself a moment to think.

Clarifying questions to ask:

• Can a backup have multiple children? (Yes — multiple differentials can branch off one full backup)
• Can a backup have multiple parents? (No — one linear ancestor chain per node)
• Will PIT ever fall between two backup timestamps? (No — guaranteed to match exact end times)
• Can expire and add run concurrently? (Yes — this is the whole point of the threading requirement)
• Are backup IDs globally unique? (Yes)

2. Build the Right Mental Model

The core abstraction here is a directed acyclic graph (DAG) — but because each backup has exactly one parent, it’s really a set of trees, each rooted at a full backup. Traversal is always child-to-root (backward through the ancestry).

f1 (Full, t=10)  →  d1 (Differential, t=20)  →  i1 (Incremental, t=30)  →  i2 (Incremental, t=40)

When you call find_recovery_chain("i2", 30):

• Walk from i2 backward through parent pointers
• Include only backups where endTime ≤ pit
• i2 ended at t=40, PIT=30 → excluded
• i1 (t=30), d1 (t=20), f1 (t=10) → included
• Output: f1 → d1 → i1

The key insight: you never need a forward adjacency list. You only ever walk up the tree, and each node stores its own parent pointer (dependentId). This makes find_recovery_chain a simple pointer-chasing loop — no BFS, no DFS, no graph traversal library needed.

💡 Interview signal: Drawing this diagram on the whiteboard before touching code is a green flag for interviewers. It shows you think in abstractions, not implementations.

3. Choosing Your Data Structures

The Backup Node

Each backup needs to store: its own ID, its parent’s ID, its retention window, and its end time. Model it as an immutable value object.

Why immutable? Because once a backup is created, none of these fields ever change. Immutability gives you thread safety on the object itself for free — no synchronisation needed on field reads after construction.

// Immutable — safe to read from any thread after construction
static class Backup {
    final String id;
    final String dependentId;   // "0" means root (full backup)
    final long retention;
    final long endTime;
    final BackupType type;

    boolean isExpired(long currentTime) {
        return endTime + retention <= currentTime;
    }
}

The Store

A flat HashMap<String, Backup> keyed by backup ID is all you need. O(1) lookup by ID — exactly what the pointer-chasing traversal requires.

In a multithreaded context you have three options:

Option Thread Safety Read Concurrency Verdict HashMap + synchronized ✅ Safe ❌ Readers block each other Too coarse ConcurrentHashMap alone ✅ Safe ✅ Full read concurrency ❌ Insufficient — expire needs atomicity across multiple removes ConcurrentHashMap + ReentrantReadWriteLock ✅ Safe ✅ Full read concurrency ✅ Best fit

⚠️ Common mistake: Many candidates jump to ConcurrentHashMap and think they're done. They're not. expire_backups performs a full scan and then multiple deletes — a non-atomic compound operation. Without a write lock, a concurrent reader could see a half-expired state mid-cleanup.

4. The Concurrency Layer — This Is Where Most People Fail

The threading design is the heart of this question. Here is the exact reasoning to walk through with your interviewer.

Identify Each Operation’s Access Pattern

Operation Reads map? Writes map? Needs atomicity? add_dependency No Yes (1 put) Yes — no reader should see a node whose parent doesn't exist yet find_recovery_chain Yes (multiple gets) No Yes — chain must be a consistent snapshot expire_backups Yes (full scan) Yes (multiple removes) Yes — scan + delete must be atomic

Why ReentrantReadWriteLock Is the Right Choice

A ReentrantReadWriteLock enforces this contract:

• Many readers, zero writers — multiple threads can call find_recovery_chain simultaneously
• One writer, zero readers — add_dependency and expire_backups get exclusive access

This is a significant win over synchronized for read-heavy workloads — which backup systems almost always are. You query far more than you add or expire.

private final ConcurrentHashMap<String, Backup> backupStore = new ConcurrentHashMap<>();
private final ReentrantReadWriteLock rwLock     = new ReentrantReadWriteLock();
private final ReentrantReadWriteLock.ReadLock  readLock  = rwLock.readLock();
private final ReentrantReadWriteLock.WriteLock writeLock = rwLock.writeLock();

Always Use try-finally for Locks

This is non-negotiable. If you forget finally, an exception mid-method leaves the lock permanently acquired — a deadlock. Every lock acquisition in production code looks like this:

writeLock.lock();
try {
    // critical section
} finally {
    writeLock.unlock(); // always runs, even if exception is thrown
}

🚨 Instant red flag: Writing lock() without try-finally in an interview is an immediate signal that you haven't worked with real concurrent systems. The interviewer will notice.

5. API Design and Algorithms, One by One

add_dependency

Create an immutable Backup object, acquire write lock, insert into map, release lock.

The write lock ensures that if a reader is mid-traversal on a chain, it doesn’t see a newly-added child node whose parent pointer hasn’t been committed yet — the classic partially-visible state problem in concurrent systems.

public void add_dependency(String backupId, String dependentId, long retention, long end) {
    Backup backup = new Backup(backupId, dependentId, retention, end);
    writeLock.lock();
    try {
        backupStore.put(backupId, backup);
    } finally {
        writeLock.unlock();
    }
}

Complexity: Time O(1) · Space O(1)

find_recovery_chain

The steps are:

1. Start at the given backupId
2. Walk parent pointers until dependentId == "0" (root) or node is missing (chain broken by expiry)
3. At each node, include it only if endTime ≤ pit
4. Use addFirst() on a LinkedList to prepend — you walk root-last but want root-first output

public String find_recovery_chain(String backupId, long pit) {
    readLock.lock();
    try {
        LinkedList<String> chain = new LinkedList<>();
        String current = backupId;

        while (current != null && !current.equals("0")) {
            Backup backup = backupStore.get(current);
            if (backup == null) break;  // chain broken — backup was expired

            if (backup.endTime <= pit) {
                chain.addFirst(backup.id);  // prepend → root ends up first
            }
            current = backup.dependentId;
        }

        return String.join(" -> ", chain);
    } finally {
        readLock.unlock();
    }
}

Complexity: Time O(D) · Space O(D) where D = chain depth

expire_backups

Key design decision: collect then delete, not delete-while-iterating. Iterating a map and deleting from it simultaneously can throw ConcurrentModificationException. Even with ConcurrentHashMap's weakly-consistent iterator, the semantics become unclear. Collect IDs first, then batch-remove under the same write lock.

public void expire_backups(long currentTime) {
    writeLock.lock();
    try {
        List<String> expired = new ArrayList<>();

        for (Map.Entry<String, Backup> entry : backupStore.entrySet()) {
            if (entry.getValue().isExpired(currentTime)) {
                expired.add(entry.getKey());
            }
        }

        expired.forEach(backupStore::remove);
    } finally {
        writeLock.unlock();
    }
}

Complexity: Time O(N) · Space O(E) where N = all backups, E = expired count

6. The Complete Implementation

import java.util.*;
import java.util.concurrent.*;
import java.util.concurrent.locks.*;

public class BackupDependencySystem {

    enum BackupType { FULL, DIFFERENTIAL, INCREMENTAL }

    static class Backup {
        final String id, dependentId;
        final long retention, endTime;
        final BackupType type;

        Backup(String id, String dependentId, long retention, long endTime) {
            this.id = id;
            this.dependentId = dependentId;
            this.retention = retention;
            this.endTime = endTime;
            this.type = resolveType(id);
        }

        private static BackupType resolveType(String id) {
            return switch (id.charAt(0)) {
                case 'f' -> BackupType.FULL;
                case 'd' -> BackupType.DIFFERENTIAL;
                case 'i' -> BackupType.INCREMENTAL;
                default  -> throw new IllegalArgumentException("Unknown backup type prefix");
            };
        }

        boolean isExpired(long currentTime) {
            return endTime + retention <= currentTime;
        }
    }

    private final ConcurrentHashMap<String, Backup> backupStore = new ConcurrentHashMap<>();
    private final ReentrantReadWriteLock rwLock     = new ReentrantReadWriteLock();
    private final ReentrantReadWriteLock.ReadLock  readLock  = rwLock.readLock();
    private final ReentrantReadWriteLock.WriteLock writeLock = rwLock.writeLock();

    public void add_dependency(String backupId, String dependentId, long retention, long end) {
        Backup backup = new Backup(backupId, dependentId, retention, end);
        writeLock.lock();
        try {
            backupStore.put(backupId, backup);
        } finally {
            writeLock.unlock();
        }
    }

    public String find_recovery_chain(String backupId, long pit) {
        readLock.lock();
        try {
            LinkedList<String> chain = new LinkedList<>();
            String current = backupId;
            while (current != null && !current.equals("0")) {
                Backup b = backupStore.get(current);
                if (b == null) break;
                if (b.endTime <= pit) chain.addFirst(b.id);
                current = b.dependentId;
            }
            return String.join(" -> ", chain);
        } finally {
            readLock.unlock();
        }
    }

    public void expire_backups(long currentTime) {
        writeLock.lock();
        try {
            List<String> expired = new ArrayList<>();
            for (Map.Entry<String, Backup> e : backupStore.entrySet()) {
                if (e.getValue().isExpired(currentTime)) expired.add(e.getKey());
            }
            expired.forEach(backupStore::remove);
        } finally {
            writeLock.unlock();
        }
    }
}

7. Complexity Analysis

Always state this clearly at the end of your implementation. It shows engineering rigour.

Operation Time Space Notes add_dependency O(1) O(1) HashMap put find_recovery_chain O(D) O(D) D = chain depth, typically < 100 expire_backups O(N) O(E) N = all backups, E = expired count

Optimising expire_backups: Maintain a PriorityQueue sorted by endTime + retention. Then expiry becomes O(E log N) instead of O(N) for the scan — you pop from the heap until the top entry isn't expired yet.

8. Common Interview Pitfalls

Pitfall 1 — Using synchronized on the method Serialises all readers. Kills throughput on a read-heavy backup system.

Pitfall 2 — Skipping try-finally One exception leaves the lock held forever. Deadlock. The interview is over.

Pitfall 3 — Using only ConcurrentHashMap Fine for single operations, but expire_backups is a compound scan+delete that needs a write lock around the whole thing.

Pitfall 4 — Building a forward adjacency list Unnecessary complexity. You never need parent-to-children traversal for PIT restore. Parent pointers on each node are sufficient.

Pitfall 5 — Forgetting the null check in find_recovery_chain If a node was expired mid-chain, the loop must terminate gracefully with break, not throw a NullPointerException.

Pitfall 6 — Deleting while iterating the map ConcurrentModificationException. Always collect expired IDs first, delete after the loop.

9. Follow-up Questions and How to Answer Them

Q: What happens if we expire f1 but i1 and i2 still exist?

The current design handles this gracefully — find_recovery_chain stops when it hits a missing node and returns a partial chain. However in production, you'd want cascade expiry validation: before expiring a backup, check if any live descendants exist. To do this efficiently, maintain a reverse dependency map — Map<String, Set<String>> children — alongside the store. If children.get(id) is non-empty, block expiry or cascade-delete all descendants first.

Q: How would you scale this to multiple JVMs or microservices?

Replace the in-process ConcurrentHashMap with a distributed store like Redis. Replace ReentrantReadWriteLock with a distributed lock — Redisson's RReadWriteLock is a drop-in equivalent over Redis. For expiry at scale, use Redis TTL on each key instead of a manual scan — Redis handles expiry asynchronously and efficiently.

Q: How would you optimise expire_backups for millions of backups?

Replace the O(N) linear scan with a PriorityQueue<Backup> sorted by endTime + retention. On each expire_backups(t) call, poll the heap while the top element's expiry ≤ t. This reduces the scan to O(E log N) where E is the number actually expired — usually far smaller than N. Maintain the heap in sync with the map inside the write lock.

Q: What if two threads call expire_backups at the same time?

The write lock serialises them — only one runs at a time. The second thread queues behind and when it acquires the lock, most backups are already gone. The isExpired check is idempotent, so rechecking already-removed entries is harmless. No double-delete issue.

Q: Why ReentrantReadWriteLock over a Semaphore?

A Semaphore with permit=1 is essentially a mutex — it doesn't distinguish read vs write access. ReentrantReadWriteLock encodes the semantic intent: many readers are safe concurrently, only writers need exclusivity. It's also reentrant — a thread holding the write lock can re-acquire it without deadlocking itself, which matters in recursive or nested call patterns.

Key Takeaways

If you remember nothing else from this post, remember these five things:

1. Restate the problem aloud before touching code — it’s a senior signal
2. Immutable objects eliminate a whole class of concurrency bugs for free
3. **ReentrantReadWriteLock** is the right tool when reads dominate and writes need exclusive access
4. Always use try-finally with locks — no exceptions, literally
5. Collect then delete — never mutate a collection while iterating it

The difference between a candidate who codes this in 20 minutes and one who codes it in 45 isn’t knowledge — it’s the habit of thinking before typing.

Written by Ranjeet Kumar — Senior Backend Engineer, Bengaluru Tags: Java, Multithreading, System Design, LLD, Interview Preparation, Backend Engineering