Master data engineering and AI like a big tech engineer

OpenAI

Amazon

Netflix

Tesla

Salesforce

Robinhood

Microsoft

Real Time Formula 1 Analytics

Big Bag Data

Chess.com Analytics

Trading Strategy for Crypto Currency - Analytics Engineering Capstone Submission

BetFlow - Real Time Sports Betting App

Showcase of student projects

Capstone Projects

Book a discovery call with Zach

Discovery call

Our students have gone on to work at companies like Meta, Airbnb and Amazon. As well as achieve 100% raises!

Fast Track Your Career

Immediate free cloud access to Databricks, AWS, Snowflake, Astronomer, and more!

Free Cloud Access with tons of hands on exercises

Weekly Guest Speaker Sessions

Why Choose DataExpert.io Academy?

Anthropic

Databricks

Discord

Snowflake

GitHub

A deep-dive five-question DSA interview for Senior Data Engineers. Covers sliding-window stream processing, heap-based merging with memory budgets, graph dependency traversal with topological sorting, LRU cache with TTL expiration, and external-memory deduplication algorithms. All problems are themed around real data pipeline challenges.

DSA Gauntlet

You are building a real-time analytics system that must detect the top-K most-frequently-appearing keys
(e.g., user IDs, events, or topics) within a rolling time window.

Given a stream of events as a list of tuples:
  events: List[Tuple[int, str]]  # (unix_timestamp, key)

Implement:

def top_k_frequent_in_window(
    events: List[Tuple[int, str]],
    window_size: int,
    k: int
) -> List[Tuple[str, int]]:
    """
    Returns a list of (key, frequency) for the top-K most frequent keys
    within each sliding window of window_size seconds.
    
    Events are NOT guaranteed to be sorted by timestamp.
    Windows are fixed (tumbling) windows of window_size seconds starting
    at the earliest event timestamp.
    Return one (key, frequency) pair per top-K key per window.
    If frequencies tie within a window, prefer the alphabetically smaller key.
    Order the final combined result by key alphabetically.
    """

Constraints:
- Events list can contain up to 1 million entries
- Timestamps span up to 30 days
- Optimize for O(n log n) or better
- Use only standard library (collections allowed)

Input Format:
  Line 1: window_size k
  Line 2: n (number of events)
  Lines 3 to n+2: timestamp key

Output Format:
  One line per (key, frequency) pair in the result, space-separated
  Order by key alphabetically

Sliding Window: Top-K Frequent Keys in Event Stream

In a distributed data system, you have K pre-sorted partition files that must be merged
into a single sorted stream. However, you have a strict memory budget and cannot load all data
into memory at once.

Given K sorted partitions (each represented as a list of integers):
  partitions: List[List[int]]  # K lists, each internally sorted

Implement:

def merge_sorted_partitions(
    partitions: List[List[int]],
    max_heap_size: int
) -> List[int]:
    """
    Merge K sorted partitions into a single sorted list using at most max_heap_size
    elements in memory at any given time.
    
    Args:
        partitions: list of K pre-sorted lists
        max_heap_size: maximum number of elements to hold in the heap
    
    Returns:
        A fully merged and sorted list of all integers from all partitions
    """

Constraints:
- Each partition is already sorted internally (smallest to largest)
- K can be up to 1,000
- Total elements across all partitions can be up to 10 million
- Heap size must not exceed max_heap_size at any point
- Optimize for O((n*K) log K) time complexity

Input Format:
  Line 1: K max_heap_size
  Lines 2 to K+1: space-separated integers for each partition

Output Format:
  One integer per line, in sorted order

Heap-Based Merge: K Sorted Partitions with Memory Budget

In a data warehouse, tables form a directed acyclic graph (DAG) of dependencies.
An edge A -> B means "B depends on data from A" (B cannot be refreshed until A is refreshed).

When a source table is updated (e.g., backfilled), you must identify ALL downstream tables
that are affected and need recomputation to maintain data integrity.

Given:
- A DAG represented as adjacency list: table_name -> [dependent_tables]
- A set of updated tables (the starting points)

Implement:

def minimal_recompute_set(
    dag: Dict[str, List[str]],
    updated_tables: List[str]
) -> List[str]:
    """
    Returns the minimal set of all tables that must be recomputed after the given
    tables are updated. This includes the updated tables themselves.
    
    Args:
        dag: adjacency list; edge A->B means B depends on A
        updated_tables: list of table names that were just updated
    
    Returns:
        Sorted list of all affected tables (including updated_tables)
    """

def topological_sort_with_priorities(
    dag: Dict[str, List[str]],
    node_priority: Dict[str, int],
    nodes: List[str]
) -> List[str]:
    """
    Return a topological sort of the given nodes using Kahn's algorithm.
    Break ties by node_priority (higher priority = earlier in sort).
    
    Returns:
        List of nodes in valid topological order, with higher-priority nodes
        appearing earlier (among nodes at the same topological level)
    """

Constraints:
- DAG has up to 10,000 nodes and 50,000 edges
- Use BFS or DFS for reachability; Kahn's algorithm for topological sort
- O(V + E) time complexity required
- No cycles guaranteed (it's a DAG)

Input Format:
  Line 1: n_tables
  Line 2: n_edges
  Lines 3 to 2+n_edges: source_table dependent_table (one edge per line)
  Line 3+n_edges: n_updated
  Lines 4+n_edges to 3+n_edges+n_updated: table_name

Output Format:
  One table name per line, in sorted order

Graph DP: DAG Table Dependencies & Minimal Recompute Set

Dictionary + doubly-linked list for LRU ordering, timestamps for TTL tracking, O(1) get/put operations, correct expiration checking before access, handles edge cases (expired keys, eviction with mixed TTLs).

LRU Cache with TTL Expiration

Rolling hash or content-addressable dedup, Bloom filter for quick rejection, full hash for collision detection, incremental chunk processing, configurable memory budget, O(n) time and O(chunk_size) space complexity.

DSA Gauntlet

In order. Round N+1 unlocks when Round N passes.