Lesson 48Advanced1h 5mAssessment-backed

DSA in System Design

Apply data-structure choices inside APIs, indexes, queues, streams, caches, and production services.

What you will be able to do

Translate product requirements into data-structure decisions.

Connect reads, writes, memory, latency, consistency, and operability.

Choose structures for indexes, feeds, queues, search, and streaming systems.

Explain when the simplest structure is the best engineering choice.

Answer SkillSkore assessments with production-grade trade-off reasoning.

Professional DSA is not about naming structures. It is about choosing the right representation for the operation mix and defending the operational consequences.

The Production Decision Framework

Start from product constraints: dominant operations, input growth, latency budget, write frequency, memory, consistency, and failure behavior. Then choose the simplest structure that satisfies those constraints.

Production DSA decision framework — A data structure decision is a product and operations decision.

Scenario: Feed Service

A feed service may use arrays for ordered render slices, maps for item lookup by ID, heaps for ranking candidates, queues for fanout, sets for deduplication, and indexes for search. The system is not one data structure; it is a set of structures aligned to operations.

Feature need	Likely structure	Trade-off to mention
Deduplicate events	Set or bloom filter	Memory and false positives if approximate.
Rank candidates	Heap or sorted index	Update cost and ranking freshness.
Serve ordered feed	Array/list plus cursor	Insertion cost and pagination.
Search old items	Inverted index/trie	Index freshness and storage.

Service map with DSA choices — Production systems compose structures around separate access patterns.

Same Pattern in Java, Python, and JavaScript

A production-style LRU cache combines a hash map for lookup with an ordered structure for eviction.

import java.util.*;

class LruCache<K, V> extends LinkedHashMap<K, V> {
    private final int capacity;
    LruCache(int capacity) { super(capacity, 0.75f, true); this.capacity = capacity; }
    @Override protected boolean removeEldestEntry(Map.Entry<K, V> eldest) { return size() > capacity; }
}

Assessment standard

A strong system-design DSA answer names the access pattern, the structure, the complexity, the operational cost, and how it will be measured.

Interview signalFrequently Asked Interview Questions

These are canonical interview patterns for this topic, phrased as concrete problem statements. They avoid vague theory questions and prepare you for the exact reasoning interviewers expect: invariant, edge cases, complexity, and trade-off.

Design get and put in O(1) average time.
Return the first non-repeating character after each incoming character.
Allow at most k requests per user in the last window of seconds.

Production practiceCompany-Style Practice Examples

These are not claimed as exact company-specific questions. They are the interview patterns repeatedly used by product companies to test whether you can move from brute force to a defensible implementation.

Example	Brute-force approach	Stronger solution	Production notes
LRU cache	Use only a map and scan timestamps on eviction.	Map plus recency order gives fast get/put/evict.	Capacity, TTL, and concurrency policy matter.
Feed service	Store everything in one giant list.	Compose arrays, maps, sets, heaps, and indexes by operation.	Consistency between structures is operational work.
Search suggestions	Run database LIKE query per keystroke.	Use prefix index/trie plus ranked candidate cache.	Freshness and normalization are core requirements.

Solved modelInterview Question Solutions

Question 1: LRU Cache

Design get and put in O(1) average time. Use a hash map for key lookup and an ordered structure for recency. On get/put, move key to most recent; evict least recent at capacity.

import java.util.*;

class LruCache<K, V> extends LinkedHashMap<K, V> {
    private final int capacity;
    LruCache(int capacity) { super(capacity, 0.75f, true); this.capacity = capacity; }
    @Override protected boolean removeEldestEntry(Map.Entry<K, V> eldest) { return size() > capacity; }
}

Question 2: First Non-Repeating Character in Stream

Return the first non-repeating character after each incoming character. Use frequency map plus queue. The queue keeps order; the map tells whether the front is still valid.

import java.util.*;
class FirstUniqueStream { Map<Character,Integer> count = new HashMap<>(); Queue<Character> q = new ArrayDeque<>(); Character add(char ch) { count.put(ch, count.getOrDefault(ch, 0) + 1); q.offer(ch); while (!q.isEmpty() && count.get(q.peek()) > 1) q.poll(); return q.peek(); } }

Question 3: Rate Limiter

Allow at most k requests per user in the last window of seconds. Use a per-user queue of timestamps. Evict expired timestamps, then allow if the queue size is below limit.

import java.util.*;
class RateLimiter { Map<String, Deque<Integer>> hits = new HashMap<>(); boolean allow(String user, int now, int window, int limit) { Deque<Integer> q = hits.computeIfAbsent(user, k -> new ArrayDeque<>()); while (!q.isEmpty() && q.peekFirst() <= now - window) q.pollFirst(); if (q.size() >= limit) return false; q.offerLast(now); return true; } }

Solved modelWorked Interview Answer

Design an LRU cache from two cooperating structures. An LRU cache needs key lookup and recency order. A map handles lookup; ordered storage handles eviction of the least recently used key.

import java.util.*;

class LruCache<K, V> extends LinkedHashMap<K, V> {
    private final int capacity;
    LruCache(int capacity) { super(capacity, 0.75f, true); this.capacity = capacity; }
    @Override protected boolean removeEldestEntry(Map.Entry<K, V> eldest) { return size() > capacity; }
}

Hands-on drillTry It Yourself

Practice task

Pick one product feature you know. List its top three operations, expected size, latency goal, and candidate structures.

Failure patternsCommon Mistakes to Avoid

Choosing impressive structures before requirements.
Ignoring write amplification.
Ignoring memory and eviction.
Forgetting consistency between duplicate structures.
Not defining measurement metrics.

Execution guardrailQuick-Start Checklist

Name access pattern.
Estimate input growth.
Choose simplest sufficient structure.
State read/write complexity.
State memory and consistency cost.
Define observability metrics.

Recall drillKnowledge Check

Question	Strong answer
Why combine map and linked order for LRU?	Map gives lookup; order gives eviction.
What is write amplification?	Extra writes caused by maintaining indexes or derived structures.
What makes a DSA answer production-grade?	It includes constraints, trade-offs, and measurement.

VocabularyKey Terms

Term	Meaning
Access pattern	Operations a feature performs most often.
Index	Derived structure optimized for lookup.
Cache	Stored result for faster future access.
Eviction	Removing entries when capacity is reached.
Consistency	Keeping multiple representations in sync.

Next practiceFurther Reading

Practice LRU cache, autocomplete system design, feed ranking, and rate limiter design.
Compare exact and approximate structures.
Review observability for latency and memory.

Bit Manipulation