Data engineer algorithms interview questions

As asked

Implement a data structure that supports two operations: addNum(int num) adds a number from a data stream, and findMedian() returns the median of all numbers added so far. The solution must support both operations in better than O(n) time.

Sample answer outline

The canonical solution uses two heaps: a max-heap for the lower half of numbers and a min-heap for the upper half. After each insertion, rebalance so the heaps differ in size by at most one. findMedian returns the top of the larger heap (odd total) or the average of both tops (even total). addNum is O(log n) and findMedian is O(1). Candidates should handle the rebalancing invariant correctly and consider edge cases like a single element.

Reference implementation (python)

import heapq

class MedianFinder:
    def __init__(self):
        self.lo = []  # max-heap (negate values)
        self.hi = []  # min-heap

    def addNum(self, num: int) -> None:
        heapq.heappush(self.lo, -num)
        # move largest of lo to hi
        heapq.heappush(self.hi, -heapq.heappop(self.lo))
        # rebalance sizes
        if len(self.hi) > len(self.lo):
            heapq.heappush(self.lo, -heapq.heappop(self.hi))

    def findMedian(self) -> float:
        if len(self.lo) > len(self.hi):
            return -self.lo[0]
        return (-self.lo[0] + self.hi[0]) / 2.0

Expect these follow-ups

• How would you extend this to return the p90 percentile instead of the median?
• If numbers arrive from multiple Spark partitions in parallel, how would you compute the approximate median at scale?

As asked

You are profiling a Databricks SQL warehouse and want to find the most common query patterns. Given an integer array representing query-type IDs and an integer k, return the k most frequent IDs in any order. Your solution must be better than O(n log n) time complexity.

Sample answer outline

The optimal approach uses bucket sort: count frequencies with a hash map (O(n)), then create n buckets indexed by frequency and place each number in its frequency bucket (O(n)). Iterate buckets from highest to lowest, collecting elements until you have k. This is O(n) overall. A simpler but slightly less optimal approach uses a min-heap of size k (O(n log k)). The candidate should explain why bucket sort achieves O(n) and verify correctness on a small example.

Reference implementation (python)

from collections import Counter

def topKFrequent(nums, k):
    count = Counter(nums)
    buckets = [[] for _ in range(len(nums) + 1)]
    for num, freq in count.items():
        buckets[freq].append(num)

    result = []
    for i in range(len(buckets) - 1, 0, -1):
        for num in buckets[i]:
            result.append(num)
            if len(result) == k:
                return result
    return result

Expect these follow-ups

• How would you compute the top-k frequent elements across a distributed dataset without collecting everything to the driver?
• What changes if elements have equal frequency and you need a stable tie-breaking rule?

As asked

A Databricks job scheduler stores job priority IDs in a sorted array, but a failover event rotated the array at an unknown pivot. Given this rotated array of distinct integers and a target job ID, return the index of the target or -1 if it is not present. Your solution must run in O(log n) time.

Sample answer outline

The candidate should use binary search but determine at each step which half is sorted. If nums[left] <= nums[mid], the left half is sorted. If the target is within [nums[left], nums[mid]], search left; otherwise search right. If the right half is sorted, apply the symmetric logic. Candidates should handle the edge case where left == mid (array of length 2) and verify on examples like [4,5,6,7,0,1,2] with target=0.

Reference implementation (python)

def search(nums, target):
    left, right = 0, len(nums) - 1
    while left <= right:
        mid = (left + right) // 2
        if nums[mid] == target:
            return mid
        if nums[left] <= nums[mid]:  # left half sorted
            if nums[left] <= target < nums[mid]:
                right = mid - 1
            else:
                left = mid + 1
        else:  # right half sorted
            if nums[mid] < target <= nums[right]:
                left = mid + 1
            else:
                right = mid - 1
    return -1

Expect these follow-ups

• How does your approach change if the array can contain duplicates?
• Can you extend this to find the rotation pivot index itself?

As asked

Your Kafka source delivers events at least once. Write code or pseudocode that emits each event downstream at most once, allowing for a 1 hour deduplication window.

Sample answer outline

Each event needs a stable idempotency key (event_id from the producer, ideally). Keep a TTL-based set or Bloom filter of seen IDs for the dedup window. On each event, check the set; if not present, emit and add. Bloom filter trades memory for a small false-positive rate (drops a few legitimate events) and zero false negatives. For exactly-once downstream, pair this with idempotent writes on the destination keyed on the same event_id. Discuss the failure mode where the dedup state itself is lost.

Reference implementation (typescript)

interface DedupStore {
  has(key: string): Promise<boolean>;
  add(key: string, ttlSeconds: number): Promise<void>;
}

export async function processOnce(
  event: { id: string; payload: unknown },
  store: DedupStore,
  emit: (e: unknown) => Promise<void>,
  windowSeconds = 3600,
): Promise<void> {
  if (await store.has(event.id)) return;
  await emit(event.payload);
  await store.add(event.id, windowSeconds);
}

Expect these follow-ups

• What if the producer cannot guarantee a stable event_id?
• How does this change if the dedup window is 24 hours and you have 1M events per minute?
• Why does at-least-once + idempotent write usually beat true exactly-once?

As asked

Databricks Workflows can model job dependencies as a directed acyclic graph, but in general pipeline routing problems the graph may have cycles and weights. Given a list of edges as (source, destination, weight) tuples and a start node, implement Dijkstra's algorithm to find the shortest distance from the start node to every other node in the graph.

Sample answer outline

The candidate should use a min-heap (priority queue) initialized with (0, start). At each step, pop the minimum distance node, skip it if already visited, then relax all outgoing edges. The algorithm terminates when the heap is empty. Distance to unvisited nodes is initialized to infinity. Candidates should handle disconnected nodes and negative weights (Dijkstra does not work with negative weights, Bellman-Ford does).

Reference implementation (python)

import heapq
from collections import defaultdict

def dijkstra(edges, n, start):
    graph = defaultdict(list)
    for u, v, w in edges:
        graph[u].append((w, v))

    dist = {i: float('inf') for i in range(n)}
    dist[start] = 0
    heap = [(0, start)]

    while heap:
        d, u = heapq.heappop(heap)
        if d > dist[u]:
            continue
        for w, v in graph[u]:
            if dist[u] + w < dist[v]:
                dist[v] = dist[u] + w
                heapq.heappush(heap, (dist[v], v))
    return dist

Expect these follow-ups

• What is the time complexity of your implementation, and how does the choice of priority queue affect it?
• How would you compute the actual shortest path, not just the distance?

As asked

You are monitoring executor CPU metrics sampled every second in a Databricks cluster and want to report the peak usage over every k-second window. Given an integer array nums of CPU samples and an integer k, return an array of the maximum value in each sliding window of size k as the window moves from left to right.

Sample answer outline

The optimal O(n) solution uses a monotonic deque that stores indices in decreasing order of their values. For each new element, remove indices from the back of the deque that are smaller than the current element (they can never be a future window maximum). Remove from the front any index that is outside the current window. The front of the deque always holds the index of the maximum for the current window. Candidates should verify on [1,3,-1,-3,5,3,6,7] with k=3 to get [3,3,5,5,6,7].

Reference implementation (python)

from collections import deque

def maxSlidingWindow(nums, k):
    dq = deque()  # stores indices, front = max
    result = []
    for i, num in enumerate(nums):
        # remove elements outside window
        while dq and dq[0] < i - k + 1:
            dq.popleft()
        # maintain decreasing order
        while dq and nums[dq[-1]] < num:
            dq.pop()
        dq.append(i)
        if i >= k - 1:
            result.append(nums[dq[0]])
    return result

Expect these follow-ups

• How would you adapt this to return the minimum instead of maximum?
• If the window size k changes dynamically, how would your approach need to change?