Python Interview Problems

Thread-Safe Counter

easy · lock ownership

Concurrency · Lock · State Machine

Implement LockedCounter(initial). This is a deterministic model of a counter's critical section, not an OS-thread exercise. Each operation is atomic. acquire(worker) returns True if the lock is free or already owned by worker, otherwise False. increment(worker, delta) changes the counter only when worker owns the lock and returns whether it succeeded. release(worker) succeeds only for the owner. value() reads the counter without changing it. Re-acquiring is idempotent, not recursive: one release unlocks it. Worker names are nonempty strings; delta and initial are integers. The test's capacity field is the initial value. Never use real threads or wall-clock sleeps.

Bounded Blocking Queue

medium · producer consumer

Concurrency · Queue · Simulation

Implement BlockingQueue(capacity), where capacity >= 1. Simulate blocking deterministically; never start threads. put(worker, value) gives an integer directly to the oldest waiting consumer, else appends it if space exists, else queues this producer's pending write. It returns 'done' for immediate completion or 'blocked' for a pending write. take(worker) removes the oldest value, then admits the oldest pending producer if any; on an empty queue it queues a waiting consumer. take returns 'done' or 'blocked'. Every completed take appends [worker, value] to a delivery log. deliveries() returns the full log without clearing it; contents() returns the queued values in FIFO order. Workers have at most one pending operation. Pending operations complete automatically in FIFO order when another operation enables them. put/take are atomic; a blocked producer's value is not lost or duplicated.

Reader-Writer Lock

hard · lock ownership

Concurrency · Set · State Machine

Implement ReaderWriterLock(capacity), ignoring the nonnegative capacity argument. This is a nonblocking deterministic lock model: acquire_read(worker) permits many readers only when there is no writer; repeated reads by the same worker are idempotent. acquire_write(worker) succeeds only when nobody holds any lock. A writer's repeated acquire_write is idempotent. A reader cannot upgrade, and a writer cannot acquire_read. Failed calls return False without changing state. release(worker) releases that worker's read or write lock and returns whether it owned one. state() returns {'readers': sorted worker names, 'writer': name or None}. No waiting/fairness guarantee, real threads, or timing is required.

Lock Ordering to Prevent Deadlock

medium · global ordering

Concurrency · Sorting · Lock

Given requests, a list of integer lock-ID lists (one per worker), return each worker's acquisition order. Deduplicate that worker's IDs and sort them ascending; retain the outer worker order. Every worker must use the same total order to eliminate circular wait. Empty requests and negative lock IDs are valid. This exercise builds a safe acquisition plan; it does not execute threads or simulate waiting. Locks are released in reverse order after the critical section.

Parallel Map with a Thread Pool

medium · heap scheduling

Concurrency · Heap · Simulation

Simulate a thread pool using a fake clock. Given tasks (integers), durations (nonnegative integers of the same length), workers >= 1, and multiplier, assign tasks in input order to the worker with the smallest (available_time, worker_id). Workers start available at time 0 and are numbered from 0. Each task starts at that worker's availability and finishes duration later. Return {'results': mapped task values in INPUT order, 'completion': task indices sorted by (finish_time, task_index)}. A mapped value is task * multiplier. Zero durations are allowed, so the same worker can receive several zero-duration tasks. Use only deterministic scheduling, no threads or sleeps.

Deadlock-Free Bank Transfer

medium · global ordering

Concurrency · Dictionary · Invariant

Process transfers atomically in the given order using a deterministic model. balances maps account names to nonnegative integer balances. Each transfer is [source, destination, amount], with both accounts present and integer amount. A transfer succeeds iff amount > 0, source differs from destination, and source has enough money. Return {'balances': final balances, 'accepted': booleans per transfer, 'lock_orders': sorted distinct [source,destination] for EVERY attempt, including rejected attempts}. Acquire both account locks in lexicographic order and release after each attempt; output the lock plan rather than using real locks. No negative balances or money creation is allowed.

Merge Intervals

medium · intervals

Array · Sorting · Intervals

Amazon · Google · Meta

You are given a list of intervals, where each interval is a pair [start, end]. Two intervals overlap if one starts before or at the point where the other ends. Merge every group of overlapping intervals into a single interval and return the merged intervals in order of increasing start.

Koko Eating Bananas

medium · binary search on answer

Array · Binary Search

Google · Amazon

Koko loves bananas. There are piles of bananas, where piles[i] is the number of bananas in pile i, and she has `h` hours before the guards return. Each hour she chooses one pile and eats up to `k` bananas from it (if the pile has fewer than k, she eats the whole pile and the hour still counts). Return the smallest integer speed `k` (bananas per hour) that lets her finish all the piles within `h` hours.

Idempotent Chunked Upload

medium · idempotency

Storage · Dictionary · Manifest

Given total >= 0 and writes of [chunk_index, text], build an idempotent upload manifest. Indices in [0,total) are valid. Accept a new chunk or an identical retry (True); reject out-of-range indices or a conflicting retry (False), keeping the first contents. Return {'accepted': booleans, 'manifest': received indices sorted ascending, 'complete': whether all chunks exist, 'content': concatenated index-ordered chunks only when complete, else None}. Empty uploads are complete with content ''. Chunk text can be empty or Unicode. All writes are sequential fake storage operations.

Parallel Processing over Shards

medium · map reduce

Storage · Array · Simulation

Each shard is a list of integers. completions is a possibly duplicated order of shard indices returned by simulated workers; all indices are valid. Count each completed shard at most once. Return {'partials': per-shard sum or None if never completed, 'total': sum of completed partials, 'complete': all shards completed}. Return partials in shard-index order, never completion order. Negative values and empty shards are valid. This deterministic reducer does not start real workers.

Sharded Key-Value Store

medium · stable hashing

Storage · Hash Table · Routing

Implement ShardedStore(capacity), using capacity >= 1 shards. route(key) returns sum(key.encode('utf-8')) modulo shard count; do not use Python's randomized hash(). put(key, value) stores an integer and returns None; get(key) returns the stored integer or None; delete(key) returns whether the key existed. dump() returns a list of shard dictionaries in shard-index order. Empty and Unicode keys are allowed. The same key must always route to the same shard; shard count never changes.

Checkpoint and WAL Replay

medium · log replay

Storage · Dictionary · Checkpoint

Given snapshot (string-to-integer dictionary), checkpoint (nonnegative sequence number), and wal records, recover state. Each record is [sequence, operation, key, value], with sequence >= 1 and operation 'set' or 'delete' (value ignored for delete). Process records in ascending sequence order and keep the FIRST record in input order if a sequence repeats. Ignore sequences <= checkpoint. A delete of a missing key is a no-op. Return {'state': recovered dictionary, 'last_sequence': greatest applied sequence or checkpoint if none}. Gaps are allowed and are not errors; do not mutate the snapshot.

Merge K Sorted Runs

medium · k-way merge

Storage · Heap · Array

Merge a list of sorted integer runs into one ascending list. Preserve duplicate values. Runs can be empty; there may be zero runs. Each run is already nondecreasing. Use a heap with at most one pending value per nonempty run, rather than flattening and sorting all values. Return values only, so equal values are indistinguishable.

Content-Hash Deduplication

easy · content addressing

Storage · Hash Table · Hashing

Deduplicate a list of text documents by the SHA-256 hash of their UTF-8 bytes. Return {'unique': texts in first-appearance order, 'indices': for each input text its index in unique}. Identical text is duplicate; do not normalize whitespace, case, or Unicode. Use hashlib.sha256, available in Python's standard library, and no external storage or network. Treat digest collisions as outside this exercise's domain.

Token Bucket Rate Limiter

medium · fake clock

API · Simulation · Rate Limiting

Given capacity >= 1, refill >= 0 tokens per integer time unit, and requests in nondecreasing time order, return one admission boolean per request. The bucket starts full at time 0. Refill up to capacity according to elapsed time before each request; an admitted request costs one token. Rejected requests cost nothing. All values are integers, repeated timestamps are valid, and time never goes backward. Do not read a real clock or sleep.

Sliding-Window Rate Limiter

medium · sliding window

API · Queue · Rate Limiting

Given limit >= 1, window >= 1, and nondecreasing integer request times >= 0, return admission booleans. At time t count only ACCEPTED earlier requests in (t-window, t], then admit if the count is below limit. Remove a request exactly at t-window. Rejected requests are not recorded. Multiple requests may have the same timestamp. Use the supplied fake times only.

Retries with Backoff and Jitter

medium · fake clock

API · Retry · Simulation

Simulate one request's retries. outcomes is a list of booleans supplied by a fake API (True means success). max_attempts >= 0, base >= 0, cap >= 0, and jitter is a list of nonnegative integer delays with at least max_attempts entries. Attempt 0 is at time 0. After failed attempt i, delay min(cap, base * 2**i) + jitter[i] before the next attempt. Stop on success, max_attempts, or exhausted outcomes; do not schedule a sleep after the final attempt. Return {'attempt_times': timestamps, 'success': boolean}. No network, randomness, or real sleeping.

Paginated Fetch-All

easy · cursor traversal

API · Set · Pagination

pages is a fake API mapping string cursor to {'items': list of integers, 'next': string cursor or None}. Starting at start, append page items in order, including duplicates. Stop at a None next cursor, a missing cursor, or before fetching a cursor a second time. Return {'items': collected values, 'visited': cursors in request order, 'error': None, 'missing_cursor', or 'cursor_cycle'}. A missing cursor is not added to visited because no page was fetched. start may be None (empty successful traversal). No HTTP requests.

Batching In-Flight Requests

medium · request coalescing

API · Dictionary · Batching

Implement RequestBatcher(capacity), where capacity >= 1 is the maximum unique keys per fake API batch. request(key) returns an integer request ID. IDs start at 0 and increase only when a key is not currently pending. Duplicate requests for a pending key return its existing ID. flush() completes ALL pending requests, returning batches of [key, id] pairs in first-request order, split into groups of at most capacity. After flush, requesting a completed key creates a NEW ID (there is no result cache). flush on an empty batch returns []. This models coalescing and batch dispatch with a fake client; no HTTP, futures, threads, or timers.

Circuit Breaker with a Fake Clock

hard · state machine

API · Circuit Breaker · Simulation

Given threshold >= 1, cooldown >= 1 and calls [time, success] in nondecreasing integer time, simulate a circuit breaker initially closed with zero failures. In closed state, forward each call; success resets consecutive failures, failure increments them and reaching threshold opens the breaker at that time. While open, block calls before opened_time + cooldown. At or after that boundary permit one atomic half-open probe: success closes and clears failures, failure reopens at the probe time. Calls are sequential and instantaneous. A blocked call MUST NOT consume its supplied outcome or extend cooldown. Return one [forwarded_boolean, resulting_state] per call, with state 'open' or 'closed' (half-open is transient). No real API calls or clock.

Number of Islands

medium · tree/graph

Array · Graph · Depth-First Search · Breadth-First Search

Amazon · Google · Meta

You are given a rectangular grid of characters, where '1' means land and '0' means water. An island is a group of '1's connected horizontally or vertically (not diagonally). Count how many islands there are and return that number.

Course Schedule

medium · graph

Graph · Depth-First Search · Topological Sort

Google · Meta · Amazon

There are `num_courses` courses, labeled 0 through num_courses - 1. You are given a list `prerequisites`, where each pair [course, prerequisite] means you must take `prerequisite` before `course`. Decide whether it is possible to finish every course, or whether the prerequisites contain a cycle that makes it impossible.

Lowest Common Ancestor

medium · tree traversal

Tree · Depth-First Search · Dictionary

nodes maps unique string node IDs to [left_id_or_None, right_id_or_None]. It describes a valid binary tree rooted at root (which may be None). Given p and q IDs, return their lowest common ancestor ID, or None if either is not reachable from root. An ancestor may be the node itself, and p may equal q. Build parent links or traverse the tree; node identity is the ID, not a value. There are at most 100 nodes.

Clone a Graph

medium · graph traversal

Graph · Breadth-First Search · Dictionary

graph maps string IDs to lists of neighbor IDs; all listed neighbors exist. It may contain cycles, self-loops, repeated neighbors, or disconnected components. Return a deep independent adjacency dictionary for only the nodes reachable from start. Preserve each node's exact neighbor-list order and duplicates; dictionary key order is irrelevant. Return {} if start is None or absent. Build new neighbor lists rather than returning aliases into graph. For this JSON-based exercise, a clone is represented by its reachable adjacency lists, not custom node objects.

Word Ladder Length

hard · breadth-first search

Graph · String · Queue

Given begin, end and words (equal-length lowercase ASCII words), change one character at a time so each word AFTER begin belongs to words. Return the number of words in the shortest chain, including begin and end, or 0 if impossible. begin need not belong to words. If begin == end, return 1 even if absent from words. Duplicate dictionary entries do not matter. At most 200 words of length at most 8.

Dijkstra Shortest Paths

medium · dijkstra

Graph · Heap · Shortest Path

Given n >= 1 vertices numbered 0..n-1, directed edges [source,destination,weight] with nonnegative integer weights, and a valid source, return a length-n distance list. Use None for unreachable vertices; source has distance 0. Parallel edges, self-loops and zero weights are allowed. Edges are directed, not automatically bidirectional. At most 100 vertices and 1000 edges.

Diameter of a Binary Tree

easy · tree traversal

Tree · Depth-First Search · Recursion

nodes maps unique string IDs to [left_id_or_None,right_id_or_None] for a valid binary tree rooted at root, or an empty tree when root is None. Return the largest number of EDGES on any path between two nodes; the path need not pass through root. Empty and one-node trees have diameter 0. There are at most 100 reachable nodes.

Trapping Rain Water

hard · two pointers

Array · Two Pointers · Stack

Amazon · Google · Meta

You are given a list `height` where height[i] is the height of a wall at position i. After it rains, water collects in the dips between walls. At any position, the water level is limited by the tallest wall to its left and the tallest wall to its right. Compute the total number of units of water trapped.

Coin Change

medium · dynamic programming

Array · Dynamic Programming · Breadth-First Search

Amazon · Google · Microsoft

You are given coin denominations `coins` and an amount of money `amount`. You may use any number of coins of each denomination. Find the fewest coins needed to make up exactly `amount`. If no combination of the coins can make the amount, return -1.

Longest Increasing Subsequence

medium · dynamic programming

Array · Binary Search · Dynamic Programming

Return the length of the longest strictly increasing subsequence of integer nums. A subsequence preserves input order but may skip elements. Equal values do not extend it. Empty input returns 0. At most 300 numbers; either quadratic DP or a tails/binary-search approach is acceptable.

Edit Distance

medium · dynamic programming

String · Dynamic Programming

Return the minimum number of single-character insertions, deletions, and replacements needed to transform source into target. Every edit costs 1. Matching characters cost 0; transposition is not one edit. Strings may be empty and have at most 100 characters. Compare Python characters exactly and case-sensitively.

House Robber

medium · dynamic programming

Array · Dynamic Programming

Given nonnegative integer money values for houses in a straight line, choose a subset with no adjacent houses and return the maximum total. Choosing no house is allowed. Empty input returns 0. The first and last houses are not neighbors unless they are adjacent in the list. At most 1000 houses.

0/1 Knapsack

medium · dynamic programming

Array · Dynamic Programming

Given positive integer weights, nonnegative integer values of equal length, and capacity >= 0, return the largest value of a subset whose total weight is at most capacity. Each indexed item can be used at most once, including when multiple items have equal weight/value. Empty input returns 0. At most 100 items and capacity <= 1000.

Unique Grid Paths

easy · dynamic programming

Grid · Dynamic Programming · Counting

Return the number of ways to go from the top-left to bottom-right of a rows-by-cols grid using only right or down moves. There are no obstacles. rows and cols are integers from 0 to 30; if either is zero, return 0. A 1-by-1 grid has one path (no moves). Return an exact integer.

Valid Parentheses

easy · stack

String · Stack

Amazon · Google · Microsoft

You are given a string `s` that contains only the characters `(`, `)`, `{`, `}`, `[`, `]`. Decide whether the string is valid: every opening bracket must be closed by the same type of bracket, and brackets must close in the correct order — the most recently opened bracket must be the first one closed. An empty string counts as valid.

Longest Substring Without Repeating Characters

medium · sliding window

String · Sliding Window · Hash Table

Amazon · Google · Microsoft

You are given a string `s`. Find the length of the longest substring (a contiguous block of characters) that contains no repeating character. Return that length as an integer.

Group Anagrams

medium · hashmap

String · Hash Table · Sorting

Amazon · Google · Meta

You are given a list of strings `strs`. Two strings are anagrams of each other if they contain exactly the same letters, each appearing the same number of times, just in a different order. Split the list into groups so that every group holds strings that are all anagrams of each other, and no two groups share an anagram.

Longest Palindromic Substring

medium · expand around center

String · Two Pointers

Return the longest contiguous substring of text that reads identically forward and backward. If several have maximum length, return the one with the smallest starting index in text. Empty input returns ''. Compare characters case-sensitively. At most 300 characters.

Minimum Window Substring

hard · sliding window

String · Hash Table · Sliding Window

Return the shortest contiguous substring of text containing every character of required with at least its required multiplicity. Ignore no characters: comparisons are case-sensitive. If shortest windows tie, choose the smallest starting index. Return '' if required is empty or no window exists. Strings have at most 500 characters.

String to Integer (atoi)

medium · parsing

String · State Machine

Parse text into a signed 32-bit integer. Skip leading ASCII spaces only (' '), read at most one optional '+' or '-', then consume consecutive ASCII digits '0'..'9'. Stop at the first other character. If no digits were consumed, return 0. Clamp to [-2147483648,2147483647]. Do not treat tabs, Unicode digits, decimal points or internal spaces as digits. At most 200 characters.

Valid Anagram

easy · frequency counting

String · Hash Table

Return whether a and b contain exactly the same characters with the same multiplicities. Order does not matter; case, spaces, and Unicode characters do matter. Do not normalize the text. Empty strings are anagrams of each other. Each string has at most 1000 characters.

K-Step Bit Flip with Retention

medium · simulation / string manipulation

String · Simulation

You are given a binary string S of length n and a positive integer k. You must apply exactly k transformations to S, one after another. Think of the transformations as being labeled with the values k, k-1, k-2, ..., 1 (the first transformation applied is labeled k, the last is labeled 1). For the transformation labeled with value v, applied to the current string: if v is odd, find the leftmost '1' in the current string — this position is the 'retained' position. If v is even, find the leftmost '0'. If the string has no character of the required type (odd's turn but the string is all '0's, or even's turn but all '1's), retain the last index of the string instead. Then produce the new string by flipping every character ('0' → '1', '1' → '0') except the retained position, which stays unchanged. Repeat for all k labeled transformations (k down to 1) and return the final string.

Enumerate Subsets

easy · backtracking

Array · Backtracking

nums contains distinct integers. Return all subsets. Each subset must be sorted ascending and the OUTER list must be in Python lexicographic list order (the empty list comes first, a prefix comes before extensions). Input order does not affect output. At most 10 integers. Return [[]] for empty input.

Enumerate Permutations

medium · backtracking

Array · Backtracking

nums contains distinct integers. Return every full-length permutation in Python lexicographic list order, regardless of input order. At most 7 integers. Empty input has one permutation: [[]]. Do not generate duplicate rows.

Combination Sum

medium · backtracking

Array · Backtracking

candidates contains distinct positive integers. Return combinations summing to target >= 0, reusing a candidate any number of times. Sort values within each combination ascending and return the outer list in Python lexicographic list order; no duplicate combinations. target <= 30 with at most 8 candidates. Target 0 has exactly one combination, [].

Count N-Queens Solutions

hard · backtracking

Backtracking · Set · Grid

Return the number of ways to place n queens on an n-by-n board with no shared row, column, or diagonal. Count distinct board arrangements; rotations/reflections count separately. n is an integer from 0 to 9. By convention n=0 has one empty arrangement. Return only the count, not board layouts.

Two Sum

easy · hashmap

Array · Hash Table

Amazon · Google · Meta

You are given a list of integers `nums` and an integer `target`. Find two different positions in the list whose values add up to `target`, and return their indices as a list `[i, j]`. There is exactly one pair that works, and you may not use the same position twice.

Single Number

easy · bit magic

Array · Bit Manipulation

Amazon · Apple

You are given a list of integers `nums` in which every value appears exactly twice, except for one value that appears exactly once. Find and return that single value.

Top K Frequent Elements

medium · heap

Array · Hash Table · Heap

Amazon · Google · Meta

You are given a list of integers `nums` and an integer `k`. Return the `k` elements that appear most often in the list. Return them in order of decreasing frequency; when several elements have the same frequency, return the smaller elements first.

LRU Cache

medium · design

Design · Hash Table · Linked List

Amazon · Google · Meta · Microsoft

Build a cache with a fixed capacity that supports two operations: get(key) returns the stored value, or -1 if the key is not present; put(key, value) stores the pair, updating the value if the key already exists. When the cache is full and a new key is added, the least recently used key (the one not read or written for the longest) is evicted. Reading or writing a key marks it as recently used. The cache is created with LRUCache(capacity).

Min Stack

easy · stack invariant

Stack · Design

Implement MinStack(capacity); the nonnegative capacity argument is unused (the stack is unbounded). push(value) returns None. pop() returns the removed integer or None if empty. top() returns the most recent value or None if empty. get_min() returns the minimum current value or None if empty. All operations should take O(1) time, including repeated equal minimum values.

Time-Based Key-Value Store

medium · binary search

Design · Hash Table · Binary Search

Implement TimeStore(capacity), ignoring the nonnegative capacity argument. set(key, value, timestamp) stores a string value and returns None; timestamps are nonnegative integers and arrive in nondecreasing order per key. Repeating a key/timestamp overwrites its previous value. get(key, timestamp) returns the value at the greatest stored timestamp <= query time, or None if none exists. Queries may arrive in any order. Keys and values may be empty strings. Use binary search for historical queries.

LFU Cache

hard · frequency buckets

Design · Hash Table · Cache

Implement LFUCache(capacity), with nonnegative capacity. get(key) returns its integer value or -1 if missing; a successful get increases its frequency and makes it most recently used at its new frequency. put(key,value) returns None; inserting starts frequency 1, updating an existing key also increases its frequency. When full, evict the lowest-frequency key; tie-break by least recently used within that frequency. Missing gets do not change any recency or frequency. Capacity 0 stores nothing. Keys are integers and may be negative; aim for O(1) expected operations.

Hit Counter

medium · sliding window

Design · Queue · Fake Clock

Implement HitCounter(capacity), where capacity >= 1 is the window length in seconds. hit(timestamp) records one hit and returns None. count(timestamp) returns hits in (timestamp-capacity, timestamp], excluding the left boundary. ALL method timestamps are nonnegative integers and nondecreasing across calls, including count calls; duplicate timestamps are separate hits. Use supplied fake times only, never a real clock. Discard expired hits to bound retained history.

Image Processor

medium · job queue / producer–consumer

Queue · Simulation · Design · Job Lifecycle

Build an image processor with a single worker and a FIFO queue. The constructor takes a `process_fn` — the function applied to each job. `submit(job)` appends the job to the queue and returns a job id (integers starting at 1, in submission order). `status(job_id)` returns 'queued', 'running', 'done', 'cancelled', or 'unknown' (for an id that was never submitted). `result(job_id)` returns the processed value for a done job, and None otherwise. `cancel(job_id)` cancels a queued job and returns True; it returns False for a running, done, cancelled, or unknown job — a running job always finishes. `step()` advances the simulation by one unit: if a job is running, finish it (run `process_fn` on it, store the result, mark it done); otherwise start the next queued job (FIFO) and mark it running. If nothing is queued and nothing is running, `step()` does nothing.

Parking Lot

medium · classes + state, allocation

Low-Level Design

Design a parking lot with several floors. Each floor has spots of three

Elevator System

medium · state machine, SCAN scheduling

Low-Level Design

Design one elevator for a building of `num_floors` floors, numbered

ATM

medium · transactions, fault tolerance, rollback

Low-Level Design

Design an ATM. It holds accounts (`account_id` → balance in cents

Tic-Tac-Toe

easy · game state, turn validation

Low-Level Design

Implement a 3×3 Tic-Tac-Toe game. X moves first. `move` returns

Library Management System

easy · CRUD + business rules

Low-Level Design

Design a library. It tracks books (copies available), members, and

URL Shortener

medium · hashing / encoding, idempotency, expiry

Low-Level Design

Design the core of a URL shortener as a single class. Short codes are

Vending Machine

medium · state machine, exact change from a limited coin pool

Low-Level Design

Design a vending machine. Prices and money are integer cents.

Expense Sharing (Splitwise)

medium · balances, greedy settlement

Low-Level Design

Design the core of Splitwise. Friends record expenses; each expense

Movie Ticket Booking (BookMyShow)

medium · booking, atomicity, seat map

Low-Level Design

Design a movie ticket booking system. A show has numbered seats

Snake Game

medium · simulation, collision rules

Low-Level Design

Implement the Snake game on a `width × height` grid, rows `0..height-1`,

Logger

easy · levels, filtering, sink injection

Low-Level Design

Design a logging framework. Levels are `DEBUG < INFO < WARN < ERROR`.

Cache with TTL

medium · LRU eviction + time-based expiry

Low-Level Design

Design a cache with a fixed capacity. Every entry may carry a TTL

Search Autocomplete

medium · trie

Low-Level Design

Design a search autocomplete system. `add(term, weight)` inserts a

Meeting Room Scheduler

medium · interval overlap, greedy room choice

Low-Level Design

Design a meeting room scheduler. Rooms have capacities. A booking

Task Scheduler

medium · fake clock, priority by due time

Low-Level Design

Design a one-shot task scheduler. `schedule(task_id, fn, delay_seconds)`

Pub-Sub

easy · observer, topics

Low-Level Design

Design a publish-subscribe system. Subscribers register a callback

HashMap

medium · hashing, chaining

Low-Level Design

Implement a hash map for integer keys. `get` returns `-1` for a

Cab Booking

medium · nearest-neighbour matching, ride lifecycle, fare

Low-Level Design

Design a ride-hailing system. Drivers and riders have `(x, y)`

Chess Game

hard · rules engine, move validation

Low-Level Design

Implement a simplified chess game on an 8×8 board. Rows `0..7`

File System

medium · tree, paths

Low-Level Design

Implement a simple in-memory file system. Directories contain

Amazon Locker

medium · allocation (best fit), pickup codes, expiry

Low-Level Design

Design an Amazon Locker bank. The bank has lockers in three sizes —

Pizza Pricing

easy · decorator

Low-Level Design

Design a pizza ordering system. There are three base pizzas —

Food Ordering

medium · order lifecycle, nearest-partner matching

Low-Level Design

Design a food ordering system. Restaurants have menus (item →

Unix Find Command

medium · tree traversal, composable filters

Low-Level Design

Implement the core of the Unix `find` command over an in-memory

Stock Broker

hard · limit order book, price-time priority

Low-Level Design

Implement a simplified stock exchange. Orders are placed for a

Deck of Cards

easy · a finite set with a seeded shuffle

Low-Level Design

Implement a standard 52-card deck. Ranks are `2–10, J, Q, K, A`;

LRU Cache

medium · design

Design · Hash Table · Linked List

Amazon · Google · Meta · Microsoft

Build a cache with a fixed capacity that supports two operations: get(key) returns the stored value, or -1 if the key is not present; put(key, value) stores the pair, updating the value if the key already exists. When the cache is full and a new key is added, the least recently used key (the one not read or written for the longest) is evicted. Reading or writing a key marks it as recently used. The cache is created with LRUCache(capacity).

LFU Cache

hard · frequency buckets

Design · Hash Table · Cache

Implement LFUCache(capacity), with nonnegative capacity. get(key) returns its integer value or -1 if missing; a successful get increases its frequency and makes it most recently used at its new frequency. put(key,value) returns None; inserting starts frequency 1, updating an existing key also increases its frequency. When full, evict the lowest-frequency key; tie-break by least recently used within that frequency. Missing gets do not change any recency or frequency. Capacity 0 stores nothing. Keys are integers and may be negative; aim for O(1) expected operations.

Token Bucket Rate Limiter

medium · fake clock

API · Simulation · Rate Limiting

Given capacity >= 1, refill >= 0 tokens per integer time unit, and requests in nondecreasing time order, return one admission boolean per request. The bucket starts full at time 0. Refill up to capacity according to elapsed time before each request; an admitted request costs one token. Rejected requests cost nothing. All values are integers, repeated timestamps are valid, and time never goes backward. Do not read a real clock or sleep.