Level-specific interview preparation

DSA Roadmaps

SDE I · SDE II · SDE III+

01 · Choose your level

Start with the interview you are preparing for.

Levels change the skills and judgment being assessed - not just the difficulty label.

02 · Build your plan

How soon is the interview?

The timeline changes what counts toward this plan; it never removes access to the full curriculum.

Target company Optional

Timed structure comes from PLAN-SENIOR-60: 25 capacity-aware tasks, with completed IDs preserved and unmet outcomes left visible.

Your plan

SDE III+ · No Deadline

Follow the standard Core and Practice curriculum without artificial calendar pressure.

Selected: 46 problems
Required: 46 Core / Practice
Mixed practice: 5 sets
Timed formats: 4

Add timed sessions after the major prerequisite chains are comfortable.

Recommended from this plan

Next Up

Start with this stageCoding Fluency Diagnostic
Refresh compact state, boundary search, and answer-space search through composition rather than syntax drills.
Arrays, Hashing & Ordered SearchProduct of Array Except Self
Next high-priority work in Coding Fluency Diagnostic.
Solve problem
Trees & Recursive ContractsBinary Tree Maximum Path Sum
Next high-priority work in Coding Fluency Diagnostic.
Solve problem
Graph Modeling RefreshNumber of Islands
Next high-priority work in Coding Fluency Diagnostic.
Solve problem

03 · Prioritize

Know what to learn first.

Core

Learn first · 18 topics

High Value

Cover after the core · 11 topics

Advanced

Defer when time is limited · 4 topics

Search and filtersCurated view

SearchPriorityStatusDifficultyTopicStageCompany add-on only

04 · Follow the roadmap

Six stages, revealed when you need them.

No Deadline selects 46 high-signal problems. Topic details stay collapsed until opened.

5 Core

Arrays, Hashing & Ordered SearchRefresh compact state, boundary search, and answer-space search through composition rather than syntax drills.Core

Why am I learning this?

Refresh compact state, boundary search, and answer-space search through composition rather than syntax drills.

Prerequisites

Start here - no required prerequisite.

Learn

Prefix/suffix state
Exact and boundary search
Answer-space predicates

Recognize It When…

Repeated lookup or aggregate state
A monotonic boundary can eliminate candidates

Core Problems

Not StartedProduct of Array Except SelfPrefix/suffix aggregationMediumCore

Solve problem

Why this problem

Builds two-direction aggregate reasoning without division.

Skills tested

prefix productssuffix productsspace optimization

Not StartedSearch in Rotated Sorted ArrayRotated binary searchMediumCore

Solve problem

Why this problem

Combines exact lookup with identifying the usable sorted half.

Skills tested

sorted-half detectionbinary searchbranch correctness

Not StartedKoko Eating BananasBinary search on answerMediumCore

Solve problem

Why this problem

Makes the monotonic feasibility predicate and answer bounds explicit.

Skills tested

feasibility predicateboundsceiling division

Mastery Check

Explain the invariant and edge boundaries without a memorized template.

Trees & Recursive ContractsDefine what each call returns before touching traversal code.Core

Why am I learning this?

Define what each call returns before touching traversal code.

Prerequisites

Start here - no required prerequisite.

Learn

Recursive contracts
Local versus global state
Stack-depth risk

Recognize It When…

A parent combines summaries returned by children

Core Problems

Not StartedBinary Tree Maximum Path SumPostorder tree DPHardCore

Solve problem

Why this problem

Separates the path contribution returned upward from the best complete path seen anywhere.

Skills tested

recursive contractsglobal optimumnegative branches

Mastery Check

State the downward-path return contract and the complete-path update separately.

Graph Modeling RefreshName vertices, edges, direction, weights, and the required graph operation first.Core

Why am I learning this?

Name vertices, edges, direction, weights, and the required graph operation first.

Prerequisites

Start here - no required prerequisite.

Learn

Reachability
Dependency ordering
Weighted paths

Recognize It When…

Relationships form an implicit or explicit network

Core Problems

Not StartedNumber of IslandsConnected componentsMediumCore

Solve problem

Why this problem

The central grid-as-graph exercise for component counting.

Skills tested

componentsgrid DFS/BFSvisited state

Interview follow-ups

How would BFS differ from DFS here?
What changes if mutating the input is not allowed?

Not StartedCourse ScheduleTopological sort / cycle detectionMediumCore

Solve problem

Why this problem

The essential dependency-graph problem for detecting whether all work can be ordered.

Skills tested

indegreesKahn's algorithmcycle detection

Senior follow-ups 3

mutation

What if dependencies change after an ordering is computed?

failure

How would you return the actual cycle instead of only false?

scale

How could independent ready tasks be executed in parallel?

From Algorithm to Design

Where this appears in systems: dependency execution

Partial recomputation matters when edges change.
Ready nodes expose available parallelism.
Cycle reporting improves operational debugging.

Not StartedNetwork Delay TimeDijkstraMediumCore

Solve problem

Why this problem

Optional introduction to weighted shortest paths after BFS is comfortable.

Skills tested

weighted graphsmin heapdistance relaxation

Senior follow-ups 3

correctness

Which property of nonnegative weights makes Dijkstra safe?

mutation

What changes if edge costs update during queries?

scale

How might a graph be partitioned without hiding cross-partition routes?

From Algorithm to Design

Where this appears in systems: routing and path planning

The graph model and weight meaning determine the algorithm.
Changing topology may invalidate precomputed paths.
Partition boundaries add coordination and stale-route concerns.

Mastery Check

Select BFS, topological reasoning, or Dijkstra from graph properties.

Heap & Streaming RefreshRetain only the candidates required by an online or ranked query.Core

Why am I learning this?

Retain only the candidates required by an online or ranked query.

Prerequisites

Start here - no required prerequisite.

Learn

Bounded heaps
Extreme-value queries
Streaming updates

Recognize It When…

Only the best K or current median matters

Core Problems

Not StartedTop K Frequent ElementsFrequency map + Top KMediumCore

Solve problem

Why this problem

Composes counting with candidate selection and supports multiple valid strategies.

Why this is SDE III+

The senior signal is selecting batch, bounded-state, or approximate processing from the workload rather than defaulting to one accepted algorithm.

Skills tested

frequency mapsheapsbucket alternative

Engineering trade-offs

Top K Frequent Elements approach comparison
Approach	Time	Space	Use when
Full sort	O(n log n)	O(n)	The dataset is already in memory and simplicity matters.
Heap of K	O(n log k)	O(n) + O(k)	k is much smaller than the number of candidates.
Buckets	O(n)	O(n)	Frequency is bounded by input size and memory is acceptable.
Bounded stream state	Update-dependent	Bounded / approximate	The history cannot be retained and exactness is negotiable.

Interview follow-ups

When would you choose a heap over frequency buckets?
How does the complexity change when K is close to n?

Senior follow-ups 4

streaming

What state must be retained when updates never stop?

memory

Can the solution retain K candidates instead of all observations?

approximation

If exact heavy hitters are too expensive, what error could the product tolerate?

scale

How would partial Top-K results be merged across partitions?

From Algorithm to Design

Where this appears in systems: ranking and analytics

Partition-local candidates can be merged into a global ranking.
Time windows change retained state.
Approximate heavy hitters can reduce memory.

Study Leaderboards / Top-K

Not StartedKth Largest Element in a StreamBounded min heapEasyCore

Solve problem

Why this problem

Shows why retaining only K candidates beats sorting every update.

Skills tested

min heapsstream updatessize-K invariant

Mastery Check

Explain what state can be discarded forever.

DP State RefreshUse one sequence problem to verify state definition and optimization fluency.Core

Why am I learning this?

Use one sequence problem to verify state definition and optimization fluency.

Prerequisites

Start here - no required prerequisite.

Learn

State meaning
Transition order
Quadratic versus optimized formulation

Recognize It When…

A sequence answer depends on best smaller prefixes

Core Problems

Not StartedLongest Increasing SubsequenceSequence DP / binary tailsMediumCore

Solve problem

Why this problem

Creates a high-signal comparison between an intuitive quadratic DP and optimized tails invariant.

Skills tested

sequence DPbinary searchinvariant comparison

Senior follow-ups 2

alternative

Compare the explainable O(n²) DP with the O(n log n) tails invariant.

memory

What additional state is needed to reconstruct an actual subsequence?

Mastery Check

Derive the O(n²) state before comparing the tails optimization.

Plan rationale, recommendation groups, and diagnosticOpen when you want the deeper reasoning behind this plan

Selected roadmap

SDE III+ Interview Roadmap

Define invariants, build robust state, and make engineering trade-offs

Stay fluent in coding while making state, API, failure, memory, concurrency, and scale implications explicit.

Reason about InvariantsBuild Robust SolutionsDiscuss ScaleMake Trade-offs

Seniority changes expected reasoning depth, not a simple Easy → Medium → Hard progression.

Prioritized curriculum

What to study - and what can wait.

Focus now6

Highest-return topics for the active plan.

Arrays, Hashing & Ordered SearchCoding Fluency Diagnostic
Trees & Recursive ContractsCoding Fluency Diagnostic
Graph Modeling RefreshCoding Fluency Diagnostic
Heap & Streaming RefreshCoding Fluency Diagnostic
DP State RefreshCoding Fluency Diagnostic
Cache StructuresInvariants & Mutable State

Learn next5

Add after the essential material is stable.

Mutable IntervalsInvariants & Mutable State
Monotonic StructuresInvariants & Mutable State
Connectivity Over TimeGraph & Dependency Reasoning
Tries & Prefix IndexingIndexing, Search & Streaming
Search Suggestions & RankingIndexing, Search & Streaming

Skip for now4

Lower-priority material that can safely wait.

Critical ConnectionsGraph & Dependency Reasoning
Advanced State-Management DrillsOptional Advanced
Segment & Fenwick TreesOptional Advanced
Advanced DP & Specialized BitsOptional Advanced

6 problems remain available outside this plan.

No company selected

Add a target company to see optional, separately counted preparation.

How to use this roadmap

Practice deliberately.

Start with Core.
Solve without revealing the pattern when possible.
Use hints progressively.
Mark substantial-help problems for review.
Use mixed sets before calling a topic mastered.
Add company practice near the interview.

More problems isn't automatically better. Once you can recognize, derive, implement, and explain a pattern consistently, move on and revisit it through mixed practice.

Coding diagnosticOpen when you need a refresh check

Diagnostic refresh

Are your coding fundamentals still interview-ready?

Attempt these shared problems without topic labels. Mark only the areas that need refresh; this view-only diagnostic is not persisted.

Use these checksReach a correct implementation without extensive warm-up.State the governing invariant before coding.Explain one alternative and one changed-constraint follow-up.

Not StartedProduct of Array Except SelfMediumCore

Solve problem

Why this problem

Builds two-direction aggregate reasoning without division.

Skills tested

prefix productssuffix productsspace optimization

Not StartedSearch in Rotated Sorted ArrayMediumCore

Solve problem

Why this problem

Combines exact lookup with identifying the usable sorted half.

Skills tested

sorted-half detectionbinary searchbranch correctness

Not StartedBinary Tree Maximum Path SumHardCore

Solve problem

Why this problem

Separates the path contribution returned upward from the best complete path seen anywhere.

Skills tested

recursive contractsglobal optimumnegative branches

Not StartedNumber of IslandsMediumCore

Solve problem

Why this problem

The central grid-as-graph exercise for component counting.

Skills tested

componentsgrid DFS/BFSvisited state

Interview follow-ups

How would BFS differ from DFS here?
What changes if mutating the input is not allowed?

Not StartedTop K Frequent ElementsMediumCore

Solve problem

Why this problem

Composes counting with candidate selection and supports multiple valid strategies.

Why this is SDE III+

The senior signal is selecting batch, bounded-state, or approximate processing from the workload rather than defaulting to one accepted algorithm.

Skills tested

frequency mapsheapsbucket alternative

Engineering trade-offs

Top K Frequent Elements approach comparison
Approach	Time	Space	Use when
Full sort	O(n log n)	O(n)	The dataset is already in memory and simplicity matters.
Heap of K	O(n log k)	O(n) + O(k)	k is much smaller than the number of candidates.
Buckets	O(n)	O(n)	Frequency is bounded by input size and memory is acceptable.
Bounded stream state	Update-dependent	Bounded / approximate	The history cannot be retained and exactness is negotiable.

Interview follow-ups

When would you choose a heap over frequency buckets?
How does the complexity change when K is close to n?

Senior follow-ups 4

streaming

What state must be retained when updates never stop?

memory

Can the solution retain K candidates instead of all observations?

approximation

If exact heavy hitters are too expensive, what error could the product tolerate?

scale

How would partial Top-K results be merged across partitions?

From Algorithm to Design

Where this appears in systems: ranking and analytics

Partition-local candidates can be merged into a global ranking.
Time windows change retained state.
Approximate heavy hitters can reduce memory.

Study Leaderboards / Top-K

Not StartedCourse ScheduleMediumCore

Solve problem

Why this problem

The essential dependency-graph problem for detecting whether all work can be ordered.

Skills tested

indegreesKahn's algorithmcycle detection

Senior follow-ups 3

mutation

What if dependencies change after an ordering is computed?

failure

How would you return the actual cycle instead of only false?

scale

How could independent ready tasks be executed in parallel?

From Algorithm to Design

Where this appears in systems: dependency execution

Partial recomputation matters when edges change.
Ready nodes expose available parallelism.
Cycle reporting improves operational debugging.

Not StartedNetwork Delay TimeMediumCore

Solve problem

Why this problem

Optional introduction to weighted shortest paths after BFS is comfortable.

Skills tested

weighted graphsmin heapdistance relaxation

Senior follow-ups 3

correctness

Which property of nonnegative weights makes Dijkstra safe?

mutation

What changes if edge costs update during queries?

scale

How might a graph be partitioned without hiding cross-partition routes?

From Algorithm to Design

Where this appears in systems: routing and path planning

The graph model and weight meaning determine the algorithm.
Changing topology may invalidate precomputed paths.
Partition boundaries add coordination and stale-route concerns.

Not StartedLongest Increasing SubsequenceMediumCore

Solve problem

Why this problem

Creates a high-signal comparison between an intuitive quadratic DP and optimized tails invariant.

Skills tested

sequence DPbinary searchinvariant comparison

Senior follow-ups 2

alternative

Compare the explainable O(n²) DP with the O(n log n) tails invariant.

memory

What additional state is needed to reconstruct an actual subsequence?

Not StartedLRU CacheMediumCore

Solve problem

Why this problem

The canonical stateful design exercise for composing O(1) lookup, recency updates, and eviction.

Why this is SDE III+

Senior depth comes from defining ownership and recency invariants, then reasoning about races, TTL, durability, partitioning, and hot keys without losing the O(1) core.

Invariant

The linked list is ordered from most recently used to least recently used.
Every cached key maps to exactly one linked-list node.
The list size never exceeds capacity after put completes.

Skills tested

API invariantslinked-list mutationhash indexing

Engineering trade-offs

LRU Cache approach comparison
Approach	Time	Space	Use when
Coarse lock	Simple contention	Low overhead	Correctness and maintainability dominate peak concurrency.
Partitioned cache	Parallel by shard	Per-shard metadata	Key partitioning can reduce lock contention and approximate global LRU is acceptable.

Senior follow-ups 4

Concurrency Follow-up

get() mutates recency. Which state needs protection, and would a coarse lock be acceptable?

persistence

What changes if cache state must survive process restart?

scale

If capacity is distributed across machines, where should eviction decisions happen?

failure

How do TTL expiry, hot keys, and background cleanup interact with the list invariant?

API Contract

Operations

get(key) → value or miss
put(key, value)

Complexity goals

O(1) lookup
O(1) recency update and eviction

Assumptions

Capacity is fixed and non-negative
Thread safety is a follow-up, not assumed

What can go wrong?

Duplicate nodes for one key
Dangling previous/next pointers
Incorrect head or tail updates
Capacity-zero boundary behavior

From Algorithm to Design

Where this appears in systems: caching and eviction

Expiration and capacity eviction are separate policies.
Metadata overhead matters when values are small.
Distributed caches may trade exact global recency for partition-local decisions.

Study cache eviction

Diagnostic review marks last only in the current roadmap view and are not saved to an account.

Mixed and timed practice5 mixed sets · 4 timed formats in this plan

Mixed practice

Remove the pattern label.

Real interviews do not announce the technique. Attempt each set before revealing the recognition cue.

Set A - Stateful

Mix cache, historical state, and heap/index composition without visible labels.

Not StartedLRU CacheMediumCore

Solve problem

Why this problem

The canonical stateful design exercise for composing O(1) lookup, recency updates, and eviction.

Why this is SDE III+

Senior depth comes from defining ownership and recency invariants, then reasoning about races, TTL, durability, partitioning, and hot keys without losing the O(1) core.

Invariant

The linked list is ordered from most recently used to least recently used.
Every cached key maps to exactly one linked-list node.
The list size never exceeds capacity after put completes.

Skills tested

API invariantslinked-list mutationhash indexing

Engineering trade-offs

LRU Cache approach comparison
Approach	Time	Space	Use when
Coarse lock	Simple contention	Low overhead	Correctness and maintainability dominate peak concurrency.
Partitioned cache	Parallel by shard	Per-shard metadata	Key partitioning can reduce lock contention and approximate global LRU is acceptable.

Senior follow-ups 4

Concurrency Follow-up

get() mutates recency. Which state needs protection, and would a coarse lock be acceptable?

persistence

What changes if cache state must survive process restart?

scale

If capacity is distributed across machines, where should eviction decisions happen?

failure

How do TTL expiry, hot keys, and background cleanup interact with the list invariant?

API Contract

Operations

get(key) → value or miss
put(key, value)

Complexity goals

O(1) lookup
O(1) recency update and eviction

Assumptions

Capacity is fixed and non-negative
Thread safety is a follow-up, not assumed

What can go wrong?

Duplicate nodes for one key
Dangling previous/next pointers
Incorrect head or tail updates
Capacity-zero boundary behavior

From Algorithm to Design

Where this appears in systems: caching and eviction

Expiration and capacity eviction are separate policies.
Metadata overhead matters when values are small.
Distributed caches may trade exact global recency for partition-local decisions.

Study cache eviction

Not StartedSnapshot ArrayMediumCore

Solve problem

Why this problem

Avoids copying the full array by storing only version changes and searching historical values.

Why this is SDE III+

Sparse version storage demonstrates how a strong representation avoids full-copy cost while preserving historical reads.

Invariant

Each index stores changes ordered by snapshot id.
Reading snapshot s returns the latest change with id ≤ s.

Skills tested

versioned statesparse historyboundary binary search

Senior follow-ups 2

memory

When can adjacent equal versions be coalesced?

persistence

How would snapshots and compaction work on disk?

API Contract

Operations

set(index, value)
snap() → snapshot id
get(index, snapshot id)

Complexity goals

Avoid O(n) snapshot copies
Logarithmic historical lookup

Assumptions

Snapshot ids are monotonically increasing

What can go wrong?

Copying the entire array for every snapshot
Wrong historical binary-search boundary
Recording redundant writes in one snapshot

From Algorithm to Design

Where this appears in systems: sparse version histories

Copy-on-write avoids copying unchanged data.
Compaction can coalesce redundant historical state.
Durability adds snapshot metadata and recovery.

Study database indexes

Not StartedStock Price FluctuationMediumPractice

Solve problem

Why this problem

Demonstrates why heaps need an index or version map when updates invalidate arbitrary historical entries.

Invariant

The timestamp map holds the current value for every timestamp.
Heap entries are valid only when they match the current map version.

Skills tested

lazy deletionversioned updatesextreme queries

Senior follow-ups 2

memory

When and how should stale heap entries be compacted?

streaming

Which queries require ordered state versus only extreme values?

What can go wrong?

Returning a stale heap value
Incorrect latest timestamp after correction
Unbounded stale heap growth

Set B - Graph Reasoning

Choose among dependency ordering, weighted paths, and connectivity.

Not StartedCourse ScheduleMediumCore

Solve problem

Why this problem

The essential dependency-graph problem for detecting whether all work can be ordered.

Skills tested

indegreesKahn's algorithmcycle detection

Senior follow-ups 3

mutation

What if dependencies change after an ordering is computed?

failure

How would you return the actual cycle instead of only false?

scale

How could independent ready tasks be executed in parallel?

From Algorithm to Design

Where this appears in systems: dependency execution

Partial recomputation matters when edges change.
Ready nodes expose available parallelism.
Cycle reporting improves operational debugging.

Not StartedCheapest Flights Within K StopsMediumCore

Solve problem

Why this problem

Forces distance state to include the stop budget rather than one value per node.

Invariant

The state includes both current node and used/remaining edge budget.
A cheaper path with too many stops cannot dominate a valid bounded path.

Skills tested

state modelingbounded relaxationtrade-offs

What can go wrong?

Collapsing all states for one node into one distance
Off-by-one between stops and edges
Incorrect early termination

Not StartedAccounts MergeMediumCore

Solve problem

Why this problem

Composes identity modeling, connectivity, and deterministic output grouping.

Skills tested

entity mappingunion/findcomponent aggregation

Senior follow-ups 3

mutation

Why is Union Find attractive when links are added incrementally?

failure

Why are edge deletions difficult for basic Union Find?

scale

What identity and partition keys would make distributed grouping difficult?

What can go wrong?

Unioning non-root parents
Losing the canonical owner metadata
Counting components before all unions complete

Set C - Online Data

Retain bounded state for streaming, rolling windows, and ordered updates.

Not StartedFind Median from Data StreamHardCore

Solve problem

Why this problem

Maintains a balance invariant across updates and supports a constant-time median query.

Why this is SDE III+

State the partition invariant first, then discuss synchronization, bounded memory, and when exact quantiles stop being worth their cost.

Invariant

The heaps differ in size by at most one.
Every value in the lower max-heap is less than or equal to every value in the upper min-heap.

Skills tested

heap partitionrebalance invariantstreaming API

Senior follow-ups 3

Concurrency Follow-up

What atomicity is required if updates and median reads interleave?

memory

Can exact median be maintained without retaining all values?

approximation

At distributed scale, when would an approximate quantile sketch be acceptable?

What can go wrong?

Heap sizes drift by more than one
Lower-half maximum exceeds upper-half minimum
Median arithmetic overflows before conversion

From Algorithm to Design

Where this appears in systems: streaming statistics

Exact global quantiles are expensive to merge.
Windowed statistics add expiry or deletion.
Approximation can bound memory and communication.

Study time-series storage

Not StartedSliding Window MaximumHardCore

Solve problem

Why this problem

Makes candidate lifetime, online updates, and amortized O(n) reasoning explicit.

Why this is SDE III+

This is a compact senior exercise in candidate lifetime, amortized reasoning, online processing, and heap-versus-deque trade-offs.

Invariant

Deque indices are inside the current window.
Their values are monotonically decreasing from front to back.
The front is the maximum for the current window.

Skills tested

deque invariantamortized analysisstreaming windows

Engineering trade-offs

Sliding Window Maximum approach comparison
Approach	Time	Space	Use when
Monotonic deque	O(n)	O(k)	Window size is fixed and values arrive in order.
Heap + lazy deletion	O(n log n)	O(n)	A priority queue is easier to adapt but stale entries need validation.

Senior follow-ups 3

alternative

Compare a heap with lazy deletion to the monotonic deque.

streaming

What state is retained when values arrive continuously?

mutation

What changes if the window size changes dynamically?

From Algorithm to Design

Where this appears in systems: rolling metrics

Event-time windows may receive late data.
Large-scale aggregation partitions state by key.
Retention should match the longest query window.

Not StartedTime Based Key-Value StoreMediumCore

Solve problem

Why this problem

Models append-only time-indexed state and query semantics before choosing binary search.

Why this is SDE III+

Treat timestamps and ordering as API assumptions, then reason about retention, out-of-order writes, compaction, and disk-backed indexes.

Invariant

Each key's versions are ordered by timestamp under the stated write contract.
A lookup returns the newest version whose timestamp is not greater than the query.

Skills tested

API designversioned valuesbinary search

Senior follow-ups 3

mutation

What if timestamps arrive out of order?

memory

What if historical versions are retained forever?

persistence

How would the index change if values live on disk?

API Contract

Operations

set(key, value, timestamp)
get(key, timestamp) → latest eligible value

Complexity goals

Append or indexed write
Logarithmic historical lookup

Assumptions

Timestamp ordering must be explicit
Retention is initially unbounded

What can go wrong?

Assuming sorted timestamps without an API guarantee
Using the wrong upper-bound result
Unbounded history without retention

From Algorithm to Design

Where this appears in systems: versioned data

Retention and compaction control historical growth.
Out-of-order writes affect index choice.
Disk-backed storage adds pages, caching, and recovery.

Set D - Coding + Follow-up

Solve one high-signal problem, then open its production-oriented extension.

Not StartedSearch Suggestions SystemMediumCore

Solve problem

Why this problem

Supports a strong comparison between static binary-search indexes, tries, and precomputed ranked suggestions.

Why this is SDE III+

Use this to compare static ordered indexes, tries, and precomputation before discussing ranking freshness and personalization.

Skills tested

prefix boundsindex trade-offsranking extension

Engineering trade-offs

Search Suggestions System approach comparison
Approach	Time	Space	Use when
Sorted array + prefix bounds	O(log n + k)	Low extra	The catalog is mostly static.
Trie	O(prefix + k)	High	Prefix navigation is frequent and memory is acceptable.
Precomputed Top-K per node	Fast reads	High	Reads dominate and ranking changes infrequently.

Senior follow-ups 3

mutation

What changes when products update continuously?

memory

How much memory does prefix expansion or precomputed Top-K consume?

scale

How would popularity, locale, or personalization change ranking and caching?

From Algorithm to Design

Where this appears in systems: autocomplete and search indexing

Static catalogs favor sorted indexes and offline precomputation.
Fresh ranking makes updates more expensive.
Personalization changes cache keys and candidate merging.

Study Search Autocomplete

Not StartedDesign TwitterMediumPractice

Solve problem

Why this problem

Combines API contracts, mutable relationships, append-only histories, and bounded feed assembly.

Why this is SDE III+

Keep the coding scope to API state and feed assembly, then use follow-ups to compare read/write fan-out, pagination, and celebrity behavior.

Invariant

Tweet sequence values establish a total recency order.
Follow relationships do not duplicate candidates.
Feed assembly returns at most the requested newest items.

Skills tested

API modelingheap mergestate ownership

Engineering trade-offs

Design Twitter approach comparison
Approach	Time	Space	Use when
Collect and sort	High per read	Low extra state	Small follow sets make the simple baseline sufficient.
K-way heap merge	O(limit log follows)	O(follows)	Per-user histories are ordered and feeds are assembled on read.

Senior follow-ups 4

alternative

Compare collect-and-sort with a K-way heap merge.

scale

Fan-out-on-read or fan-out-on-write: what changes for celebrity accounts?

persistence

How are feed pagination and storage growth handled?

failure

What consistency is acceptable if follow updates and tweet reads race?

API Contract

Operations

postTweet(user, tweet)
getNewsFeed(user)
follow(user, target)
unfollow(user, target)

Complexity goals

Bound feed output
Avoid sorting unbounded global history

Assumptions

Single-process state for the coding problem
Production distribution is discussion-only

From Algorithm to Design

Where this appears in systems: feed assembly

Read versus write fan-out shifts cost and freshness.
Celebrity accounts create skew.
Pagination requires a stable cursor or ordering key.

Not StartedNetwork Delay TimeMediumCore

Solve problem

Why this problem

Optional introduction to weighted shortest paths after BFS is comfortable.

Skills tested

weighted graphsmin heapdistance relaxation

Senior follow-ups 3

correctness

Which property of nonnegative weights makes Dijkstra safe?

mutation

What changes if edge costs update during queries?

scale

How might a graph be partitioned without hiding cross-partition routes?

From Algorithm to Design

Where this appears in systems: routing and path planning

The graph model and weight meaning determine the algorithm.
Changing topology may invalidate precomputed paths.
Partition boundaries add coordination and stale-route concerns.

Set E - Senior Round

Begin from incomplete requirements, clarify the contract, then choose one of these implementations.

Not StartedLRU CacheMediumCore

Solve problem

Why this problem

The canonical stateful design exercise for composing O(1) lookup, recency updates, and eviction.

Why this is SDE III+

Senior depth comes from defining ownership and recency invariants, then reasoning about races, TTL, durability, partitioning, and hot keys without losing the O(1) core.

Invariant

The linked list is ordered from most recently used to least recently used.
Every cached key maps to exactly one linked-list node.
The list size never exceeds capacity after put completes.

Skills tested

API invariantslinked-list mutationhash indexing

Engineering trade-offs

LRU Cache approach comparison
Approach	Time	Space	Use when
Coarse lock	Simple contention	Low overhead	Correctness and maintainability dominate peak concurrency.
Partitioned cache	Parallel by shard	Per-shard metadata	Key partitioning can reduce lock contention and approximate global LRU is acceptable.

Senior follow-ups 4

Concurrency Follow-up

get() mutates recency. Which state needs protection, and would a coarse lock be acceptable?

persistence

What changes if cache state must survive process restart?

scale

If capacity is distributed across machines, where should eviction decisions happen?

failure

How do TTL expiry, hot keys, and background cleanup interact with the list invariant?

API Contract

Operations

get(key) → value or miss
put(key, value)

Complexity goals

O(1) lookup
O(1) recency update and eviction

Assumptions

Capacity is fixed and non-negative
Thread safety is a follow-up, not assumed

What can go wrong?

Duplicate nodes for one key
Dangling previous/next pointers
Incorrect head or tail updates
Capacity-zero boundary behavior

From Algorithm to Design

Where this appears in systems: caching and eviction

Expiration and capacity eviction are separate policies.
Metadata overhead matters when values are small.
Distributed caches may trade exact global recency for partition-local decisions.

Study cache eviction

Not StartedTime Based Key-Value StoreMediumCore

Solve problem

Why this problem

Models append-only time-indexed state and query semantics before choosing binary search.

Why this is SDE III+

Treat timestamps and ordering as API assumptions, then reason about retention, out-of-order writes, compaction, and disk-backed indexes.

Invariant

Each key's versions are ordered by timestamp under the stated write contract.
A lookup returns the newest version whose timestamp is not greater than the query.

Skills tested

API designversioned valuesbinary search

Senior follow-ups 3

mutation

What if timestamps arrive out of order?

memory

What if historical versions are retained forever?

persistence

How would the index change if values live on disk?

API Contract

Operations

set(key, value, timestamp)
get(key, timestamp) → latest eligible value

Complexity goals

Append or indexed write
Logarithmic historical lookup

Assumptions

Timestamp ordering must be explicit
Retention is initially unbounded

What can go wrong?

Assuming sorted timestamps without an API guarantee
Using the wrong upper-bound result
Unbounded history without retention

From Algorithm to Design

Where this appears in systems: versioned data

Retention and compaction control historical growth.
Out-of-order writes affect index choice.
Disk-backed storage adds pages, caching, and recovery.

Senior practice modes

Clarify first. Review before rewriting.

These original Foundry exercises test requirement discovery and code judgment without pretending that every interview begins from a polished problem statement.

Ambiguous interview mode

Ask before you implement.

Versioned Store

Design an in-memory structure that stores values by key and retrieves a value as of a timestamp.

Questions to ask

Can writes arrive out of timestamp order?
What should happen before the first version?
How many writes and historical reads are expected?
Must history be retained forever?
Are concurrent readers and writers in scope?

Reveal constraints

Writes are initially timestamp-ordered per key.
Historical lookup should be logarithmic in versions for that key.
Retention and persistence are follow-ups.

Bounded Cache

Design a bounded cache with constant-time reads and writes.

Questions to ask

Which eviction policy defines the bound?
Does a read update policy state?
Can capacity be zero?
Is TTL required?
What thread-safety assumptions apply?

Reveal constraints

Use recency-based eviction.
Both reads and writes update recency.
Start single-threaded; concurrency is a follow-up.

Rolling Ranking

Maintain the most important items from a continuous stream.

Questions to ask

What defines importance?
Is the answer exact?
Is there a time window?
Can scores be corrected?
How large can the key space become?

Reveal constraints

Begin with exact Top-K frequencies in one process.
Then discuss bounded memory and partitioned aggregation.

Code review mode

Find the broken invariant.

Broken LRU Update

Review a plausible recency update that leaves two structures inconsistent.

put(key, value):
  if key exists:
    map[key].value = value
    return
  node = Node(key, value)
  map[key] = node
  addToFront(node)
  if map.size > capacity:
    removeTail()

Review prompts

Which operation fails to update recency?
What must eviction remove from the map?
What happens at capacity zero?

Reveal findings

Updating an existing key returns without moving its node to the front.
removeTail must also delete the evicted key from the map.
Capacity zero needs a valid empty-list path.

Late-Visited BFS

Find the complexity and correctness risks in a traversal that marks nodes only when dequeued.

queue = [start]
while queue not empty:
  node = queue.popFront()
  visited.add(node)
  for next in graph[node]:
    if next not in visited:
      queue.pushBack(next)

Review prompts

Can a node enter the queue more than once?
What happens in a dense cyclic graph?
Where should visited be updated?

Reveal findings

Several parents can enqueue the same node before its first dequeue.
Queue growth can become much larger than O(V).
Mark the node visited when it is enqueued.

Broken Lower Bound

Audit a binary search whose interval contract and return value disagree.

left = 0; right = values.length - 1
while left < right:
  mid = (left + right) // 2
  if values[mid] < target:
    left = mid
  else:
    right = mid
return left

Review prompts

Can the loop stop shrinking?
What input demonstrates it?
Should the search interval be closed or half-open?

Reveal findings

left = mid can repeat forever when right = left + 1.
The return contract does not represent insertion after the final element.
Use a consistent closed or half-open lower-bound template.

Timed progression

Rehearse the whole interview.

The timer is not the skill. Practice the sequence from clarification through manual testing and follow-ups.

30–40 min

Fluency Check

One coding problem with no production follow-up.

Clarify quickly
State invariant
Implement and test

45 min

Senior Coding Round

One coding problem plus an explicit algorithm trade-off discussion.

Establish a baseline
Compare alternatives
Avoid unnecessary complexity

50–60 min

Coding + Extension

Coding followed by a focused 10–15 minute production or API extension.

Finish the local invariant first
Discuss one scale or failure dimension
Keep the bridge concise

45–60 min

Ambiguous Round

Clarify an incomplete requirement set before implementation.

Ask operation questions
Set assumptions
Revise when constraints appear

Review queue

Review what actually needs another pass.

Nothing needs review right now.Diagnostic review marks will appear here for this view.

Includes account-backed Review status and temporary diagnostic marks for this view.

Readiness

Use evidence, not a fake pass percentage.

Not enough practice dataPattern Recognition

Complete a mixed set before this can be assessed.

Not enough practice dataImplementation

No account-backed problem attempts are available.

Not enough practice dataComplexity Analysis

Record high confidence on independently reproducible solved work to supply evidence.

Not enough practice dataTrees & Graphs

No tree or graph practice evidence yet.

Not enough practice dataTimed Practice

Complete a timed session before this can be assessed.

Not enough practice dataStateful Design & Invariants

Invariant and follow-up mastery are not persisted yet.

SDE II failure modes

Correct the decision process.

Coding before defining the contract

Clarify operations, complexity, ordering, and mutation assumptions first.

Invisible invariants

Write the relationships that every mutation must preserve before implementation.

Heap-only thinking

Ask how arbitrary corrections or deletions make entries stale and require an index.

Graph abstraction drift

Name vertices, edges, weights, and the required operation before choosing an algorithm.

Ignoring memory growth

Identify retained history, metadata overhead, and a deletion or retention policy.

Premature distribution

Finish the correct in-process algorithm before discussing partitions and failures.

Vague concurrency answers

Name the protected state and atomic boundary rather than only saying use a lock.

Overvaluing Hard counts

Use competency gaps and follow-up quality - not arbitrary totals - to direct practice.

Optional before an SDE III+ interview

Stretch only when the core is comfortable.

These topics do not block roadmap completion. Deferring them does not mean you are behind.

Advanced State-Management DrillsUseful for roles that heavily emphasize intricate mutable structures; not a universal senior readiness gate.

Not StartedAll O`one Data StructureBucketed frequency listHardStretch

Solve problem

Why this problem

An advanced state-management drill where minimum, maximum, buckets, and key positions must stay synchronized in O(1).

Why this is SDE III+

Use this as an advanced state-management drill, not a universal senior readiness gate.

Invariant

Frequency buckets are strictly ordered.
Every key appears in exactly one bucket.
Minimum and maximum keys are available from the boundary buckets.

Skills tested

bucket listshash indexingboundary mutation

What can go wrong?

Orphaned empty bucket
Key present in multiple buckets
Broken boundary pointer after deletion

Not StartedData Stream as Disjoint IntervalsOrdered mutable intervalsHardStretch

Solve problem

Why this problem

Tests incremental merging and the choice of an ordered index for interleaved updates and queries.

Skills tested

ordered stateinterval mergingAPI invariants

Not StartedRange ModuleMutable range indexHardStretch

Solve problem

Why this problem

An advanced workload-driven structure for adding, removing, and querying covered ranges without assuming a static sort.

Skills tested

range updatesordered intervalsquery invariants

Segment & Fenwick TreesCompany- and role-dependent structures for mutable range workloads.

Not StartedRange Sum Query - MutableFenwick / segment treeMediumStretch

Solve problem

Why this problem

Represents the point-update plus range-query workload without making advanced trees mandatory for general senior interviews.

Skills tested

range aggregationpoint updatesstructure comparison

Advanced DP & Specialized BitsOptional breadth that should not delay normal senior interview preparation.

Not StartedBurst BalloonsInterval dynamic programmingHardStretch

Solve problem

Why this problem

A deliberately optional advanced DP drill for changing the decision perspective from first action to last action.

Skills tested

interval stateboundary sentinelstransition order

Not StartedSingle Number IIBit-state countingMediumStretch

Solve problem

Why this problem

A specialized constant-space bit invariant that belongs in role-dependent advanced practice.

Skills tested

bit countsfinite-state reasoningconstant space

Loading roadmap planner…

Top K Frequent Elements approach comparison

Approach

Time

Space

Use when

Full sort

O(n log n)

O(n)

The dataset is already in memory and simplicity matters.

Heap of K

O(n log k)

O(n) + O(k)

k is much smaller than the number of candidates.

Buckets

O(n)

Frequency is bounded by input size and memory is acceptable.

Bounded stream state

Update-dependent

Bounded / approximate

The history cannot be retained and exactness is negotiable.

Top K Frequent Elements approach comparison

Approach

Time

Space

Use when

Full sort

O(n log n)

O(n)

The dataset is already in memory and simplicity matters.

Heap of K

O(n log k)

O(n) + O(k)

k is much smaller than the number of candidates.

Buckets

O(n)

Frequency is bounded by input size and memory is acceptable.

Bounded stream state

Update-dependent

Bounded / approximate

The history cannot be retained and exactness is negotiable.

LRU Cache approach comparison

Approach

Time

Space

Use when

Coarse lock

Simple contention

Low overhead

Correctness and maintainability dominate peak concurrency.

Partitioned cache

Parallel by shard

Per-shard metadata

Key partitioning can reduce lock contention and approximate global LRU is acceptable.

LRU Cache approach comparison

Approach

Time

Space

Use when

Coarse lock

Simple contention

Low overhead

Correctness and maintainability dominate peak concurrency.

Partitioned cache

Parallel by shard

Per-shard metadata

Key partitioning can reduce lock contention and approximate global LRU is acceptable.

Sliding Window Maximum approach comparison

Approach

Time

Space

Use when

Monotonic deque

O(n)

O(k)

Window size is fixed and values arrive in order.

Heap + lazy deletion

O(n log n)

O(n)

A priority queue is easier to adapt but stale entries need validation.

Search Suggestions System approach comparison

Approach

Time

Space

Use when

Sorted array + prefix bounds

O(log n + k)

Low extra

The catalog is mostly static.

Trie

O(prefix + k)

High

Prefix navigation is frequent and memory is acceptable.

Precomputed Top-K per node

Fast reads

High

Reads dominate and ranking changes infrequently.

Design Twitter approach comparison

Approach

Time

Space

Use when

Collect and sort

High per read

Low extra state

Small follow sets make the simple baseline sufficient.

K-way heap merge

O(limit log follows)

O(follows)

Per-user histories are ordered and feeds are assembled on read.

LRU Cache approach comparison

Approach

Time

Space

Use when

Coarse lock

Simple contention

Low overhead

Correctness and maintainability dominate peak concurrency.

Partitioned cache

Parallel by shard

Per-shard metadata

Key partitioning can reduce lock contention and approximate global LRU is acceptable.

Use evidence, not a fake pass percentage.

Not enough practice dataPattern Recognition

Complete a mixed set before this can be assessed.

Not enough practice dataImplementation

No account-backed problem attempts are available.

Not enough practice dataComplexity Analysis

Record high confidence on independently reproducible solved work to supply evidence.

Not enough practice dataTrees & Graphs

No tree or graph practice evidence yet.

Not enough practice dataTimed Practice

Complete a timed session before this can be assessed.

Not enough practice dataStateful Design & Invariants

Invariant and follow-up mastery are not persisted yet.

Start with the interview you are preparing for.

How soon is the interview?

SDE III+ · No Deadline

Next Up

Know what to learn first.

Six stages, revealed when you need them.

Coding Fluency Diagnostic

Arrays, Hashing & Ordered Search

Why am I learning this?

Prerequisites

Learn

Recognize It When…

Core Problems

Mastery Check

Trees & Recursive Contracts

Why am I learning this?

Prerequisites

Learn

Recognize It When…

Core Problems

Mastery Check

Graph Modeling Refresh

Why am I learning this?

Prerequisites

Learn

Recognize It When…

Core Problems

Mastery Check

Heap & Streaming Refresh

Why am I learning this?

Prerequisites

Learn

Recognize It When…

Core Problems

Mastery Check

DP State Refresh

Why am I learning this?

Prerequisites

Learn

Recognize It When…

Core Problems

Mastery Check

Invariants & Mutable State

Graph & Dependency Reasoning

Indexing, Search & Streaming

Coding → Production Bridge

Senior Interview Simulation

SDE III+ Interview Roadmap

What to study - and what can wait.

Practice deliberately.

Are your coding fundamentals still interview-ready?

Remove the pattern label.

Clarify first. Review before rewriting.

Ask before you implement.

Questions to ask

Questions to ask

Questions to ask

Find the broken invariant.

Review prompts

Review prompts

Review prompts

Rehearse the whole interview.

Fluency Check

Senior Coding Round

Coding + Extension

Ambiguous Round

Review what actually needs another pass.

Use evidence, not a fake pass percentage.

Correct the decision process.

Stretch only when the core is comfortable.

Start with the interview you are preparing for.

How soon is the interview?

SDE III+ · No Deadline

Next Up

Know what to learn first.

Six stages, revealed when you need them.

Coding Fluency Diagnostic

Arrays, Hashing & Ordered Search

Why am I learning this?

Prerequisites