Data Structures
powered by pagefind esc close · ↑↓ navigate · ↵ open
ds · practice

Practice

Interview-style problems chosen so each one demonstrates how a specific data structure is used in practice. Every problem includes progressive hints, a full Rust solution with tests, complexity analysis, and a real-world anchor.

Arrays 3 problems

  1. Two Sum

    easy
    time
    O(n)
    space
    O(n)

    arrays · hash-tables

    in the wild Sensor calibration — pair up two readings whose sum matches a known reference.

  2. Maximum Subarray (Kadane's)

    medium
    time
    O(n)
    space
    O(1)

    arrays · dynamic-programming

    in the wild Best continuous window of SLAM confidence — the longest stretch of trusted tracking.

  3. Trapping Rain Water

    hard
    time
    O(n)
    space
    O(1)

    arrays · two-pointer

    in the wild Terrain reservoirs — given an elevation profile, how much rainwater settles in the valleys?

Linked Lists 3 problems

  1. Merge Two Sorted Linked Lists

    easy
    time
    O(n + m)
    space
    O(1)

    linked-lists · two-pointer

    in the wild Merging two sorted sensor streams (time-stamped) into one ordered timeline.

  2. Reverse a Linked List

    easy
    time
    O(n)
    space
    O(1)

    linked-lists · two-pointer

    in the wild Reverse a transaction log to replay events in undo order; reverse a robot's trajectory chain for backtracking.

  3. Detect a Cycle (Floyd's Tortoise and Hare)

    medium
    time
    O(n)
    space
    O(1)

    linked-lists · two-pointer · cycle-detection

    in the wild Detect an infinite loop in a state-machine transition graph; spot a follow-cycle in social graphs.

Stacks 3 problems

  1. Min Stack

    easy
    time
    O(1)
    space
    O(n)

    stacks · design

    in the wild Robot recovery rollback — keep the cheapest known-safe state reachable in O(1) at any depth of a planning stack.

  2. Evaluate Postfix Expression

    medium
    time
    O(n)
    space
    O(n)

    stacks · parsing

    in the wild RPN calculators (HP-35), JVM bytecode VMs, the WebAssembly stack machine — all evaluate expressions exactly like this.

  3. Next Greater Element

    medium
    time
    O(n)
    space
    O(n)

    stacks · monotonic-stack

    in the wild Find the next higher temperature reading in a sensor stream; find the next price peak in a tick-by-tick feed.

Queues 3 problems

  1. Queue from Two Stacks

    medium
    time
    O(1)
    space
    O(n)

    queues · stacks · design · amortized

    in the wild Bridging a LIFO log-buffer to a FIFO consumer, or wrapping a stack-only API to expose queue semantics.

  2. Bounded Ring Buffer (Robotics)

    medium
    time
    O(1)
    space
    O(capacity)

    queues · ring-buffer · robotics

    in the wild Every ROS topic, every UART driver, every IMU sample stream: a fixed-capacity FIFO where producers can't be allowed to block consumers.

  3. Sliding Window Maximum

    hard
    time
    O(n)
    space
    O(k)

    queues · monotonic-deque · sliding-window

    in the wild Streaming sensor signal: report the maximum reading in the last k samples — a Kalman filter's gate threshold, a vibration-spike detector, a sliding-confidence summary.

Binary Trees 3 problems

  1. Maximum Depth of Binary Tree

    easy
    time
    O(n)
    space
    O(h)

    trees · recursion · dfs

    in the wild Computing a robot's kinematic chain depth (URDF leaf-to-root walk), or the max nesting depth of a JSON/DOM document.

  2. Binary Tree Level-Order Traversal

    medium
    time
    O(n)
    space
    O(w)

    trees · bfs

    in the wild Wavefront expansion on an occupancy grid, organizational-chart visualization (one level per row), and 'show me the network neighbors at depth ≤ k'.

  3. Diameter of Binary Tree

    medium
    time
    O(n)
    space
    O(h)

    trees · recursion · dfs

    in the wild Maximum hop count across a star/tree-shaped network; longest kinematic span across a robot's URDF (joint-to-joint farthest pair).

Binary Search Trees 3 problems

  1. Lowest Common Ancestor in a BST

    easy
    time
    O(h)
    space
    O(1)

    bst · recursion

    in the wild Find the most specific shared category of two products in a taxonomy tree, or the closest junction joining two waypoints in a routing tree.

  2. Kth Smallest Element in a BST

    medium
    time
    O(h + k)
    space
    O(h)

    bst · in-order

    in the wild Order-statistic queries on a sorted index: 'show me the 100th highest-priority pending task', 'find the median sensor reading in this BST-backed sketch'.

  3. Validate Binary Search Tree

    medium
    time
    O(n)
    space
    O(h)

    bst · recursion · dfs

    in the wild Sanity-check a freshly deserialized index, or an in-place tree that you've just rotated — does the BST invariant still hold?

Heaps & Priority Queues 3 problems

  1. Top K Frequent Elements

    medium
    time
    O(n log k)
    space
    O(n)

    heaps · hash-tables · top-k

    in the wild Top-K trending topics, hot URL leaderboard, top-K product views — anywhere a streaming or batch system needs the heaviest hitters.

  2. Median of a Data Stream

    hard
    time
    O(log n) per insert, O(1) per query
    space
    O(n)

    heaps · two-heaps · streaming

    in the wild Latency percentiles in a streaming monitoring system, online sensor median (robust to outlier spikes), real-time score median for fairness.

  3. Merge K Sorted Lists

    hard
    time
    O(n log k)
    space
    O(k)

    heaps · linked-lists · k-way-merge

    in the wild External merge sort, log-file consolidation, distributed query results — anywhere k sorted streams must merge into one sorted output.

Hash Tables 3 problems

  1. Group Anagrams

    medium
    time
    O(n · k)
    space
    O(n · k)

    hash-tables · strings · canonicalization

    in the wild Deduplicate sensor signatures up to permutation; cluster scrambled OCR'd words; group hash-collision keys.

  2. Longest Substring Without Repeating Characters

    medium
    time
    O(n)
    space
    O(min(n, alphabet))

    hash-tables · sliding-window · strings

    in the wild Detect the longest distinct-byte run in a packet stream; longest run of non-repeating tokens in an LLM prompt cache.

  3. LRU Cache

    medium
    time
    O(1)
    space
    O(capacity)

    hash-tables · doubly-linked-list · design

    in the wild Every database buffer pool, every CPU cache layer, browser cache, Redis (with `allkeys-lru`), and OS page cache — the LRU eviction policy is everywhere.

Graphs 3 problems

  1. Course Schedule (Topological Sort)

    medium
    time
    O(V + E)
    space
    O(V + E)

    graphs · topological-sort · cycle-detection

    in the wild Build-system task ordering (make, bazel), package dependency resolution, ROS launch-file ordering, microservice startup choreography.

  2. Number of Islands

    medium
    time
    O(rows · cols)
    space
    O(rows · cols)

    graphs · grid · dfs · connected-components

    in the wild Connected-component segmentation on an occupancy grid (which clumps of obstacles form one object?), region-counting in image masks, flood-fill in paint tools.

  3. Shortest Path in a Maze (BFS)

    medium
    time
    O(rows · cols)
    space
    O(rows · cols)

    graphs · bfs · grid · shortest-path

    in the wild Wavefront path planner on a robot's occupancy grid; warehouse-AGV routing; tile-based-game pathfinding (Pacman, Dwarf Fortress).

Balanced Trees 1 problem

  1. Is Binary Tree Height-Balanced?

    easy
    time
    O(n)
    space
    O(h)

    trees · recursion · dfs

    in the wild Sanity-check that an AVL / Red-Black implementation's rebalance step actually balanced — or detect when a workload pattern degenerates a self-balancing tree.

Dynamic Programming 3 problems

  1. Climbing Stairs

    easy
    time
    O(n)
    space
    O(1)

    dynamic-programming · recursion

    in the wild Counting paths through a state machine where each step has a fixed set of moves; the simplest 'cumulative count' DP that scales to any 1D recurrence.

  2. Coin Change

    medium
    time
    O(amount · |coins|)
    space
    O(amount)

    dynamic-programming

    in the wild Cashier algorithms, transit-fare token minimization, network MTU packing, robot energy-budget step planning.

  3. Longest Common Subsequence

    medium
    time
    O(m · n)
    space
    O(min(m, n))

    dynamic-programming · strings

    in the wild Every diff tool you've ever used (git diff, diff -u) computes LCS internally; bioinformatics sequence alignment (Needleman-Wunsch) is the weighted version.