Data scientist algorithms interview questions

As asked

Given an array of integers and a target value, return the indices of the two numbers that add up to the target. You may not use the same index twice. Now: can you do it in O(n) time? And if memory is extremely tight, what is the best space complexity you can achieve?

Sample answer outline

O(n) time with a hash map, O(n) space. For the space-constrained version, a sorted array plus two pointers gives O(n log n) time and O(1) space, but requires the original indices to be stored alongside values. A strong answer explains the trade-off clearly: sorting destroys original indices unless you save them, and O(1) space means O(n log n) time. Interviewers often follow up to force the candidate to articulate why they cannot do better than O(n) time with O(1) space for the general case.

Reference implementation (python)

def two_sum(nums: list[int], target: int) -> list[int]:
    seen = {}  # value -> index
    for i, num in enumerate(nums):
        complement = target - num
        if complement in seen:
            return [seen[complement], i]
        seen[num] = i
    return []

Expect these follow-ups

• What if the array were already sorted?
• What if you needed to return all pairs, not just one?

As asked

Given a list of 2D points and an integer K, return the K points closest to the origin (0, 0). You do not need to return them in sorted order. Now walk me through the time complexity of each approach you can think of.

Sample answer outline

Three viable approaches: sort all points by Euclidean distance in O(n log n), use a max-heap of size K in O(n log K) which is better when K is much smaller than n, or use QuickSelect (partition-based) for O(n) average time. A strong answer compares all three and picks the right one based on the constraints given. The candidate should also note they can compare squared distances to avoid the sqrt computation.

Reference implementation (python)

import heapq

def k_closest(points: list[list[int]], k: int) -> list[list[int]]:
    # Max-heap of size k: negate distance to simulate max-heap with Python's min-heap
    heap = []
    for x, y in points:
        dist = -(x*x + y*y)  # negated squared distance
        heapq.heappush(heap, (dist, x, y))
        if len(heap) > k:
            heapq.heappop(heap)
    return [[x, y] for _, x, y in heap]

Expect these follow-ups

• What if K were very large, close to N?
• How would you handle streaming points arriving one at a time?

As asked

Given an integer array and a value K, return the K most frequent elements. You can return the answer in any order. What is the optimal time complexity and how do you achieve it?

Sample answer outline

Count frequencies with a hash map in O(n), then either use a min-heap of size K to track the top K in O(n log K), or use bucket sort (group counts by frequency in an array indexed by count, scan from max to min) in O(n). The bucket sort approach is O(n) time and space and beats the heap approach, though the heap is more general (works when K is known but n is unknown, like a stream). A strong candidate presents both and picks bucket sort when asked to optimize.

Reference implementation (python)

def top_k_frequent(nums: list[int], k: int) -> list[int]:
    count = {}
    for n in nums:
        count[n] = count.get(n, 0) + 1
    # bucket sort: index = frequency
    buckets = [[] for _ in range(len(nums) + 1)]
    for num, freq in count.items():
        buckets[freq].append(num)
    result = []
    for freq in range(len(buckets) - 1, 0, -1):
        result.extend(buckets[freq])
        if len(result) >= k:
            return result[:k]
    return result

Expect these follow-ups

• How would you solve this on a stream of integers where you cannot store all the data?
• What if K equals N, what does your algorithm degenerate to?

As asked

Given an array of points on a 2D plane, return the k closest points to the origin. You do not need to sort the result. What is the most efficient approach and its time complexity?

Sample answer outline

The interviewer is looking for the candidate to discuss multiple approaches: sorting in O(n log n), a max-heap of size k in O(n log k), and QuickSelect in O(n) average time. A strong candidate implements the heap solution for correctness first, then explains QuickSelect and its O(n^2) worst case. They should note that floating-point square roots are unnecessary since we only compare distances.

Expect these follow-ups

• When would you prefer QuickSelect over the heap approach?
• How would this change if the points arrive as a stream?

As asked

You receive a continuous stream of trade events. Each event has an asset ticker. You need to return the top K tickers by trade count at any point in time. Implement this efficiently and explain how your approach behaves as the number of distinct tickers grows.

Sample answer outline

A strong answer uses a hash map for O(1) count updates per ticker plus a min-heap of size K to maintain the top K in O(log K) per update, for O(n log K) overall on a stream of n events. The candidate should explain why sorting the entire hash map on every query is O(n log n) and worse for a stream, and discuss the memory tradeoff of storing all tickers versus only the top K. A follow-up question about approximate results might lead to a Count-Min Sketch discussion.

Reference implementation (python)

import heapq
from collections import defaultdict

def top_k_assets(events: list[str], k: int) -> list[str]:
    counts = defaultdict(int)
    for ticker in events:
        counts[ticker] += 1
    # return top k by count
    return heapq.nlargest(k, counts, key=counts.get)

Expect these follow-ups

• How would you make this work in a distributed system where trade events arrive on multiple nodes?
• What approximate data structure would you use if exact counts were not required and you needed to handle billions of tickers?

As asked

DoorDash runs in multiple geographic regions. Each region produces a sorted stream of order events by timestamp. You receive k sorted arrays of order events and need to merge them into a single sorted output efficiently. Write the solution and analyze its time and space complexity.

Sample answer outline

The optimal solution uses a min-heap of size k, initialized with the first element from each array. Each extraction from the heap takes O(log k) and there are N total elements, giving O(N log k) time and O(k) space. The candidate should compare this to the naive approach of concatenating and sorting (O(N log N)) and explain why the heap wins when k is small relative to N. For streaming data, they should mention that each region's stream can be a generator rather than a full array in memory.

Reference implementation (python)

import heapq

def merge_k_sorted(streams):
    heap = []
    for i, stream in enumerate(streams):
        if stream:
            heapq.heappush(heap, (stream[0].timestamp, i, 0, stream))
    result = []
    while heap:
        ts, stream_idx, elem_idx, stream = heapq.heappop(heap)
        result.append(stream[elem_idx])
        if elem_idx + 1 < len(stream):
            next_elem = stream[elem_idx + 1]
            heapq.heappush(heap, (next_elem.timestamp, stream_idx, elem_idx + 1, stream))
    return result

Expect these follow-ups

• How does your approach change if event timestamps are not perfectly monotonic due to clock drift?
• How would you parallelize this merge across multiple machines?

As asked

You are building a DoorDash dashboard that shows the top 10 restaurants by order count in the last 60 minutes, updating every 30 seconds. There are 500,000 restaurants and millions of orders per hour. How would you compute this efficiently, and what data structure or system backs it?

Sample answer outline

A strong answer uses a sliding window backed by a Redis sorted set (ZADD with order timestamp, ZREMRANGEBYSCORE to expire old entries, ZREVRANGE to get top K). For the sliding window at scale they mention summarizing into 1-minute count buckets per restaurant to reduce cardinality, merging the last 60 buckets per query rather than tracking every individual order event. The candidate should compare this to a stream-processing approach (Flink or Kafka Streams with tumbling or sliding windows) for higher throughput and fault tolerance. They should also note that a min-heap of size K can extract the top K from the full sorted structure in O(K log N) rather than sorting all 500,000 restaurants.

Expect these follow-ups

• How do you ensure the dashboard update at 30 second intervals does not cause a thundering herd against Redis?
• How does this design change if you need the top K per cuisine category, not globally?

As asked

You have a stream of LinkedIn profile skill lists, one list per member. Implement a function that returns the top K skills by frequency across all profiles seen so far. The stream is too large to fit in memory all at once.

Sample answer outline

A complete answer covers a hash map for exact counts combined with a min-heap of size K for the top-K tracking, giving O(n log K) time overall. For the true streaming case, the candidate should mention Count-Min Sketch for approximate frequency with bounded memory, or a divide-and-conquer partition approach. They should discuss the tradeoff between exactness and memory.

Reference implementation (python)

import heapq
from collections import defaultdict

def top_k_skills(profiles: list[list[str]], k: int) -> list[str]:
    counts = defaultdict(int)
    for profile in profiles:
        for skill in profile:
            counts[skill] += 1
    # min-heap of (count, skill) of size k
    heap = []
    for skill, count in counts.items():
        heapq.heappush(heap, (count, skill))
        if len(heap) > k:
            heapq.heappop(heap)
    return [skill for _, skill in sorted(heap, reverse=True)]

Expect these follow-ups

• How would you parallelize this across 100 machines if the stream is partitioned?
• How does your approach change if you only want top-K skills for members in a specific region?

As asked

Given a stream of title IDs representing user plays, return the K most frequently played titles at any point in time. The stream is too large to sort. What data structure do you use, and what is the time complexity per insertion and per query?

Sample answer outline

A strong answer uses a hash map for counts plus a min-heap of size K. Each insertion updates the count in O(1) and conditionally updates the heap in O(log K). Querying returns the K elements in O(K log K) to sort them. The candidate should compare this to a sorted bucket approach, explain why a full sort of all elements is O(n log n) versus O(n log K) for the heap approach, and discuss how this changes if K is very large relative to the number of unique titles.

Expect these follow-ups

• How would you extend this to find the top K over a sliding window of the last 24 hours instead of all time?
• If the stream is distributed across 100 nodes, how do you compute the global top K efficiently?

As asked

You receive a continuous stream of integers. At any point, a caller can ask for the current median. Implement a data structure that supports inserting a new number in O(log n) and returning the median in O(1). What is the space complexity, and how would you handle a stream so large it does not fit in memory?

Sample answer outline

The standard in-memory solution uses two heaps: a max-heap for the lower half and a min-heap for the upper half, balanced to differ by at most one element. Median is the top of the larger heap or the average of both tops. For streams that exceed memory, the candidate should describe approximate methods like reservoir sampling, a count-min sketch, or a B-tree-backed external sort with percentile estimation.

Reference implementation (python)

import heapq

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

    def add_num(self, num: int) -> None:
        heapq.heappush(self.lo, -num)
        heapq.heappush(self.hi, -heapq.heappop(self.lo))
        if len(self.hi) > len(self.lo):
            heapq.heappush(self.lo, -heapq.heappop(self.hi))

    def find_median(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

• What if the values are bounded integers in [0, 1000000]? Can you do better?
• How would you extend this to return the p95 percentile instead of the median?

As asked

You have a graph with roughly 10 million nodes and 100 million directed weighted edges. Edge weights change frequently based on real-time sensor data. You need to support point-to-point shortest-path queries with latency under 100 ms. Dijkstra on the raw graph is too slow. How do you design this system?

Sample answer outline

A strong answer covers precomputation strategies such as contraction hierarchies or landmark-based ALT algorithms, the trade-off between precomputation cost and query speed, and how frequent edge weight changes invalidate the preprocessing. The candidate should discuss delta updates, approximate methods for near-real-time weights, and partitioning the graph spatially or topologically. They should also address concurrency: how many parallel queries the system must serve.

Expect these follow-ups

• How would your approach change if 90% of queries are between the same 1000 high-traffic nodes?
• How do you handle an edge weight update that changes the shortest path between two nodes that are cached?

As asked

You have a 200 GB log file on disk. You need to find the 10 most frequently occurring words. You have 4 GB of RAM. Walk me through your approach step by step, and give me the time and space complexity.

Sample answer outline

Chunk the file and stream it through a hash map to accumulate counts; if the map grows too large, spill sorted runs to disk and merge them externally. Once counts are complete, use a min-heap of size K to track the top K entries. Time complexity is O(N log K) where N is total word count. The candidate should also mention hash partitioning across multiple passes as an alternative if the distinct word space is very large.

Expect these follow-ups

• What if the file is spread across 100 machines in HDFS? How does your approach change?
• How would you handle Unicode edge cases in word tokenisation?

As asked

Given a list of intervals representing time windows when sensors are active, return a list of merged intervals with no overlaps. The input is unsorted. Optimize for the case where the list is nearly sorted and updates arrive in near-real-time.

Sample answer outline

Sort by start time then do a linear scan, merging when the current interval overlaps the last merged one. For near-sorted streaming data, a balanced BST (like a sorted list with bisect) lets you insert and query in O(log n) rather than re-sorting each time. The candidate should handle edge cases: empty list, single interval, all intervals identical, and intervals that share only a boundary point.

Reference implementation (python)

def merge(intervals: list[list[int]]) -> list[list[int]]:
    if not intervals:
        return []
    intervals.sort(key=lambda x: x[0])
    merged = [intervals[0]]
    for start, end in intervals[1:]:
        if start <= merged[-1][1]:
            merged[-1][1] = max(merged[-1][1], end)
        else:
            merged.append([start, end])
    return merged

Expect these follow-ups

• How would you store the merged intervals if new intervals arrive at 10,000 per second?
• How does your answer change if intervals can have open versus closed endpoints?

As asked

An integer array was sorted in ascending order and then rotated at an unknown pivot. Given the array and a target, return the index of the target or -1 if it is not present. You must achieve O(log n) time. How does your answer change if the array can contain duplicates?

Sample answer outline

Modified binary search: at each step, determine which half is sorted by comparing mid to left or right boundary. Check if the target falls in the sorted half; if so, narrow there; otherwise search the other half. With duplicates, when nums[left] == nums[mid] == nums[right] you cannot determine which side is sorted, so you must shrink the window by one on each side, giving O(n) worst case. The candidate should handle all edge cases: single element, no rotation, target at pivot.

Reference implementation (python)

def search(nums: list[int], target: int) -> int:
    lo, hi = 0, len(nums) - 1
    while lo <= hi:
        mid = (lo + hi) // 2
        if nums[mid] == target:
            return mid
        # Left half is sorted
        if nums[lo] <= nums[mid]:
            if nums[lo] <= target < nums[mid]:
                hi = mid - 1
            else:
                lo = mid + 1
        else:  # Right half is sorted
            if nums[mid] < target <= nums[hi]:
                lo = mid + 1
            else:
                hi = mid - 1
    return -1

Expect these follow-ups

• How do you find the index of the pivot point itself in O(log n)?
• What if the array can be rotated multiple times?

As asked

Given an integer array and an integer K, find the maximum sum of a contiguous subarray where you are allowed to remove at most K elements from within the subarray (they do not count toward the sum, but the subarray remains contiguous around them). What is the time and space complexity of your solution?

Sample answer outline

This extends Kadane's algorithm with a DP dimension for removals: dp[i][j] is the maximum subarray sum ending at index i with j removals used. Transition: dp[i][j] = max(dp[i-1][j] + nums[i], dp[i-1][j-1]) where the second option skips nums[i] at the cost of one removal. Running max over all i and j gives the answer. Time is O(n * K), space is O(K) with a rolling array. The candidate should verify base cases and note that when K is large enough to cover the entire subarray, negative elements can always be removed and the answer degenerates to the sum of all positives.

Expect these follow-ups

• How would you recover the actual subarray indices, not just the sum?
• What if K can be as large as N? Is there a simpler solution in that case?

As asked

Snowflake's coding interviews often start with a classic warm-up to establish baseline problem-solving fluency. Given an array of integers and a target integer, return the indices of the two numbers that add up to the target. You may assume exactly one solution exists and you may not use the same element twice. What is the most efficient approach and what is its time and space complexity?

Sample answer outline

The optimal solution uses a hash map: iterate the array once, storing each value's index. For each element, check whether (target - element) exists in the map before inserting the current element. This gives O(n) time and O(n) space. The candidate should also describe the naive O(n^2) brute-force and explain why the hash map is better. Bonus: mention edge cases like negative numbers, zeros, and the single-element input.

Reference implementation (python)

def two_sum(nums: list[int], target: int) -> list[int]:
    seen = {}  # value -> index
    for i, num in enumerate(nums):
        complement = target - num
        if complement in seen:
            return [seen[complement], i]
        seen[num] = i
    return []

Expect these follow-ups

• How would you solve it if the array were sorted and you needed O(1) extra space?
• How does this generalize to finding three numbers that sum to zero (3Sum)?

As asked

In Snowflake engineering interviews the top-K problem appears in contexts like finding the most queried tables or the most frequent values in a column sample. Given an integer array and an integer k, return the k most frequent elements. You do not need to return them in any particular order. The solution should be faster than O(n log n) overall.

Sample answer outline

The optimal approach uses a frequency map (O(n)) combined with a min-heap of size k (O(n log k)) to track the top k elements, giving O(n log k) total. Alternatively, bucket sort: create an array of lists indexed by frequency (since max frequency is n), fill it from the frequency map, and scan from the end to collect k elements in O(n). The candidate should compare the two and know when bucket sort is faster (when k is close to n).

Reference implementation (python)

import heapq
from collections import Counter

def top_k_frequent(nums: list[int], k: int) -> list[int]:
    freq = Counter(nums)
    # min-heap of size k
    return heapq.nlargest(k, freq.keys(), key=lambda x: freq[x])

Expect these follow-ups

• How would you solve this if the array were a data stream where elements arrive one at a time and you can only use O(k) space?
• What changes if the problem asks for the kth most frequent single element rather than the top k?

As asked

You are given a stream of track IDs representing plays arriving in real time. At any point, return the K most-played tracks. The stream is unbounded and K is small, say 10. What data structure gives you the best time complexity per insertion, and how do you handle ties?

Sample answer outline

A strong answer uses a hash map to count plays per track and a min-heap of size K to maintain the top-K candidates. Each insertion is O(log K). The candidate explains why a max-heap over all tracks would use more memory and why sorting the entire count map is too slow for a streaming context. Ties can be broken by insertion order or alphabetically, and the candidate picks one and states why.

Reference implementation (python)

import heapq
from collections import defaultdict

def top_k_tracks(stream, k):
    counts = defaultdict(int)
    heap = []  # min-heap of (count, track_id)

    for track_id in stream:
        counts[track_id] += 1
        # maintain heap of size k
        # TODO

    return [track for _, track in sorted(heap, reverse=True)]

Expect these follow-ups

• How would your approach change if K were 1 million instead of 10?
• How would you compute the top K tracks within a rolling 24-hour window?

As asked

Given a continuous stream of charge events where each event has a merchant_id and an amount in cents, return the top K merchants by total volume at any point in time. The stream is unbounded. How do you do this efficiently in memory?

Sample answer outline

The standard approach maintains a hash map of merchant_id to cumulative volume and a min-heap of size K. When a merchant's updated volume exceeds the heap minimum, replace the minimum. The candidate should analyze time complexity per event: O(log K) for heap operations. For the approximate version on truly unbounded streams, the Space-Saving or Count-Min-Sketch approach trades accuracy for bounded memory and is worth mentioning.

Reference implementation (python)

# Python sketch
import heapq
from collections import defaultdict

def top_k_merchants(stream, k):
    totals = defaultdict(int)
    heap = []  # (volume, merchant_id), min-heap

    for merchant_id, amount in stream:
        totals[merchant_id] += amount
        # maintain heap of size k
        heapq.heappush(heap, (totals[merchant_id], merchant_id))
        if len(heap) > k:
            heapq.heappop(heap)

    return sorted(heap, reverse=True)

Expect these follow-ups

• How does your answer change if K is 1 million and the number of distinct merchants is 10 million?
• What if you needed the top-K over a sliding 24-hour window instead of all time?

As asked

Tesla's telemetry pipeline continuously receives sensor readings from the fleet, and on-call engineers need the real-time median of a signal (such as battery temperature) to detect fleet-wide anomalies without waiting for a batch job. Design a class that continuously ingests a stream of integers and, at any point, returns the median of all integers seen so far. Both addNum(int num) and findMedian() must be as fast as possible.

Sample answer outline

The solution uses two heaps: a max-heap for the lower half and a min-heap for the upper half. After each insertion, the heaps are rebalanced so they differ in size by at most one element. findMedian is O(1); addNum is O(log n). The candidate should explain why a sorted array or BST are inferior alternatives and mention that an augmented order-statistic tree would allow arbitrary percentile queries, which is relevant to Tesla's telemetry use case.

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)
        heapq.heappush(self.hi, -heapq.heappop(self.lo))
        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 does this change if you only need the median of a sliding window of the last 1000 values?
• What if the data stream contains floating-point sensor readings with duplicates?

As asked

You are processing a live stream of numeric engagement scores (likes, retweets). Implement a data structure that supports adding a new score in O(log n) and returning the current median in O(1) at any point in the stream.

Sample answer outline

A strong answer maintains two heaps: a max-heap for the lower half and a min-heap for the upper half, keeping them balanced within 1 element of each other. On each insert, the candidate should correctly route the new element and rebalance if sizes diverge. Median retrieval is the top of the larger heap for odd total, or the average of both tops for even total.

Reference implementation (python)

import heapq

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

    def addNum(self, num: int) -> None:
        heapq.heappush(self.lo, -num)
        heapq.heappush(self.hi, -heapq.heappop(self.lo))
        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

• If scores can only be integers in the range 0 to 100, can you do better than two heaps?
• How does your solution change if you need the median only over a sliding window of the last 10,000 observations?

As asked

Given a stream of tweets, implement a function that returns the number of times a specific word appeared in the last 5 minutes. Tweets arrive at roughly 10,000 per second and each tweet can contain multiple words. The count must be accurate to within 1 second of the actual 5-minute window.

Sample answer outline

A strong answer uses a circular buffer of 300 one-second buckets (5 min x 60 sec), incrementing the current second's bucket on each match and summing all 300 on a query. The candidate should handle the edge case where multiple seconds elapse between updates (reset stale buckets), discuss the memory footprint per tracked word, and compare this approach to a sorted deque for exact sliding windows.

Expect these follow-ups

• You now need to track not one word but the top 100 words simultaneously. How does your data structure scale?
• What is the maximum error in your count and when does it occur?

As asked

Given an array of integers and a target value, return the indices of the two numbers that add up to the target. You may not use the same index twice. Now: can you do it in O(n) time? And if memory is extremely tight, what is the best space complexity you can achieve?

Sample answer outline

O(n) time with a hash map, O(n) space. For the space-constrained version, a sorted array plus two pointers gives O(n log n) time and O(1) space, but requires the original indices to be stored alongside values. A strong answer explains the trade-off clearly: sorting destroys original indices unless you save them, and O(1) space means O(n log n) time. Interviewers often follow up to force the candidate to articulate why they cannot do better than O(n) time with O(1) space for the general case.

Reference implementation (python)

def two_sum(nums: list[int], target: int) -> list[int]:
    seen = {}  # value -> index
    for i, num in enumerate(nums):
        complement = target - num
        if complement in seen:
            return [seen[complement], i]
        seen[num] = i
    return []

Expect these follow-ups

• What if the array were already sorted?
• What if you needed to return all pairs, not just one?

As asked

Given a list of 2D points and an integer K, return the K points closest to the origin (0, 0). You do not need to return them in sorted order. Now walk me through the time complexity of each approach you can think of.

Sample answer outline

Three viable approaches: sort all points by Euclidean distance in O(n log n), use a max-heap of size K in O(n log K) which is better when K is much smaller than n, or use QuickSelect (partition-based) for O(n) average time. A strong answer compares all three and picks the right one based on the constraints given. The candidate should also note they can compare squared distances to avoid the sqrt computation.

Reference implementation (python)

import heapq

def k_closest(points: list[list[int]], k: int) -> list[list[int]]:
    # Max-heap of size k: negate distance to simulate max-heap with Python's min-heap
    heap = []
    for x, y in points:
        dist = -(x*x + y*y)  # negated squared distance
        heapq.heappush(heap, (dist, x, y))
        if len(heap) > k:
            heapq.heappop(heap)
    return [[x, y] for _, x, y in heap]

Expect these follow-ups

• What if K were very large, close to N?
• How would you handle streaming points arriving one at a time?

As asked

Given an integer array and a value K, return the K most frequent elements. You can return the answer in any order. What is the optimal time complexity and how do you achieve it?

Sample answer outline

Count frequencies with a hash map in O(n), then either use a min-heap of size K to track the top K in O(n log K), or use bucket sort (group counts by frequency in an array indexed by count, scan from max to min) in O(n). The bucket sort approach is O(n) time and space and beats the heap approach, though the heap is more general (works when K is known but n is unknown, like a stream). A strong candidate presents both and picks bucket sort when asked to optimize.

Reference implementation (python)

def top_k_frequent(nums: list[int], k: int) -> list[int]:
    count = {}
    for n in nums:
        count[n] = count.get(n, 0) + 1
    # bucket sort: index = frequency
    buckets = [[] for _ in range(len(nums) + 1)]
    for num, freq in count.items():
        buckets[freq].append(num)
    result = []
    for freq in range(len(buckets) - 1, 0, -1):
        result.extend(buckets[freq])
        if len(result) >= k:
            return result[:k]
    return result

Expect these follow-ups

• How would you solve this on a stream of integers where you cannot store all the data?
• What if K equals N, what does your algorithm degenerate to?

As asked

Given an array of points on a 2D plane, return the k closest points to the origin. You do not need to sort the result. What is the most efficient approach and its time complexity?

Sample answer outline

The interviewer is looking for the candidate to discuss multiple approaches: sorting in O(n log n), a max-heap of size k in O(n log k), and QuickSelect in O(n) average time. A strong candidate implements the heap solution for correctness first, then explains QuickSelect and its O(n^2) worst case. They should note that floating-point square roots are unnecessary since we only compare distances.

Expect these follow-ups

• When would you prefer QuickSelect over the heap approach?
• How would this change if the points arrive as a stream?

As asked

You receive a continuous stream of trade events. Each event has an asset ticker. You need to return the top K tickers by trade count at any point in time. Implement this efficiently and explain how your approach behaves as the number of distinct tickers grows.

Sample answer outline

A strong answer uses a hash map for O(1) count updates per ticker plus a min-heap of size K to maintain the top K in O(log K) per update, for O(n log K) overall on a stream of n events. The candidate should explain why sorting the entire hash map on every query is O(n log n) and worse for a stream, and discuss the memory tradeoff of storing all tickers versus only the top K. A follow-up question about approximate results might lead to a Count-Min Sketch discussion.

Reference implementation (python)

import heapq
from collections import defaultdict

def top_k_assets(events: list[str], k: int) -> list[str]:
    counts = defaultdict(int)
    for ticker in events:
        counts[ticker] += 1
    # return top k by count
    return heapq.nlargest(k, counts, key=counts.get)

Expect these follow-ups

• How would you make this work in a distributed system where trade events arrive on multiple nodes?
• What approximate data structure would you use if exact counts were not required and you needed to handle billions of tickers?

As asked

DoorDash runs in multiple geographic regions. Each region produces a sorted stream of order events by timestamp. You receive k sorted arrays of order events and need to merge them into a single sorted output efficiently. Write the solution and analyze its time and space complexity.

Sample answer outline

The optimal solution uses a min-heap of size k, initialized with the first element from each array. Each extraction from the heap takes O(log k) and there are N total elements, giving O(N log k) time and O(k) space. The candidate should compare this to the naive approach of concatenating and sorting (O(N log N)) and explain why the heap wins when k is small relative to N. For streaming data, they should mention that each region's stream can be a generator rather than a full array in memory.

Reference implementation (python)

import heapq

def merge_k_sorted(streams):
    heap = []
    for i, stream in enumerate(streams):
        if stream:
            heapq.heappush(heap, (stream[0].timestamp, i, 0, stream))
    result = []
    while heap:
        ts, stream_idx, elem_idx, stream = heapq.heappop(heap)
        result.append(stream[elem_idx])
        if elem_idx + 1 < len(stream):
            next_elem = stream[elem_idx + 1]
            heapq.heappush(heap, (next_elem.timestamp, stream_idx, elem_idx + 1, stream))
    return result

Expect these follow-ups

• How does your approach change if event timestamps are not perfectly monotonic due to clock drift?
• How would you parallelize this merge across multiple machines?

As asked

You are building a DoorDash dashboard that shows the top 10 restaurants by order count in the last 60 minutes, updating every 30 seconds. There are 500,000 restaurants and millions of orders per hour. How would you compute this efficiently, and what data structure or system backs it?

Sample answer outline

A strong answer uses a sliding window backed by a Redis sorted set (ZADD with order timestamp, ZREMRANGEBYSCORE to expire old entries, ZREVRANGE to get top K). For the sliding window at scale they mention summarizing into 1-minute count buckets per restaurant to reduce cardinality, merging the last 60 buckets per query rather than tracking every individual order event. The candidate should compare this to a stream-processing approach (Flink or Kafka Streams with tumbling or sliding windows) for higher throughput and fault tolerance. They should also note that a min-heap of size K can extract the top K from the full sorted structure in O(K log N) rather than sorting all 500,000 restaurants.

Expect these follow-ups

• How do you ensure the dashboard update at 30 second intervals does not cause a thundering herd against Redis?
• How does this design change if you need the top K per cuisine category, not globally?

As asked

You have a stream of LinkedIn profile skill lists, one list per member. Implement a function that returns the top K skills by frequency across all profiles seen so far. The stream is too large to fit in memory all at once.

Sample answer outline

A complete answer covers a hash map for exact counts combined with a min-heap of size K for the top-K tracking, giving O(n log K) time overall. For the true streaming case, the candidate should mention Count-Min Sketch for approximate frequency with bounded memory, or a divide-and-conquer partition approach. They should discuss the tradeoff between exactness and memory.

Reference implementation (python)

import heapq
from collections import defaultdict

def top_k_skills(profiles: list[list[str]], k: int) -> list[str]:
    counts = defaultdict(int)
    for profile in profiles:
        for skill in profile:
            counts[skill] += 1
    # min-heap of (count, skill) of size k
    heap = []
    for skill, count in counts.items():
        heapq.heappush(heap, (count, skill))
        if len(heap) > k:
            heapq.heappop(heap)
    return [skill for _, skill in sorted(heap, reverse=True)]

Expect these follow-ups

• How would you parallelize this across 100 machines if the stream is partitioned?
• How does your approach change if you only want top-K skills for members in a specific region?

As asked

Given a stream of title IDs representing user plays, return the K most frequently played titles at any point in time. The stream is too large to sort. What data structure do you use, and what is the time complexity per insertion and per query?

Sample answer outline

A strong answer uses a hash map for counts plus a min-heap of size K. Each insertion updates the count in O(1) and conditionally updates the heap in O(log K). Querying returns the K elements in O(K log K) to sort them. The candidate should compare this to a sorted bucket approach, explain why a full sort of all elements is O(n log n) versus O(n log K) for the heap approach, and discuss how this changes if K is very large relative to the number of unique titles.

Expect these follow-ups

• How would you extend this to find the top K over a sliding window of the last 24 hours instead of all time?
• If the stream is distributed across 100 nodes, how do you compute the global top K efficiently?

As asked

You receive a continuous stream of integers. At any point, a caller can ask for the current median. Implement a data structure that supports inserting a new number in O(log n) and returning the median in O(1). What is the space complexity, and how would you handle a stream so large it does not fit in memory?

Sample answer outline

The standard in-memory solution uses two heaps: a max-heap for the lower half and a min-heap for the upper half, balanced to differ by at most one element. Median is the top of the larger heap or the average of both tops. For streams that exceed memory, the candidate should describe approximate methods like reservoir sampling, a count-min sketch, or a B-tree-backed external sort with percentile estimation.

Reference implementation (python)

import heapq

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

    def add_num(self, num: int) -> None:
        heapq.heappush(self.lo, -num)
        heapq.heappush(self.hi, -heapq.heappop(self.lo))
        if len(self.hi) > len(self.lo):
            heapq.heappush(self.lo, -heapq.heappop(self.hi))

    def find_median(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

• What if the values are bounded integers in [0, 1000000]? Can you do better?
• How would you extend this to return the p95 percentile instead of the median?

As asked

You have a graph with roughly 10 million nodes and 100 million directed weighted edges. Edge weights change frequently based on real-time sensor data. You need to support point-to-point shortest-path queries with latency under 100 ms. Dijkstra on the raw graph is too slow. How do you design this system?

Sample answer outline

A strong answer covers precomputation strategies such as contraction hierarchies or landmark-based ALT algorithms, the trade-off between precomputation cost and query speed, and how frequent edge weight changes invalidate the preprocessing. The candidate should discuss delta updates, approximate methods for near-real-time weights, and partitioning the graph spatially or topologically. They should also address concurrency: how many parallel queries the system must serve.

Expect these follow-ups

• How would your approach change if 90% of queries are between the same 1000 high-traffic nodes?
• How do you handle an edge weight update that changes the shortest path between two nodes that are cached?

As asked

You have a 200 GB log file on disk. You need to find the 10 most frequently occurring words. You have 4 GB of RAM. Walk me through your approach step by step, and give me the time and space complexity.

Sample answer outline

Chunk the file and stream it through a hash map to accumulate counts; if the map grows too large, spill sorted runs to disk and merge them externally. Once counts are complete, use a min-heap of size K to track the top K entries. Time complexity is O(N log K) where N is total word count. The candidate should also mention hash partitioning across multiple passes as an alternative if the distinct word space is very large.

Expect these follow-ups

• What if the file is spread across 100 machines in HDFS? How does your approach change?
• How would you handle Unicode edge cases in word tokenisation?

As asked

Given a list of intervals representing time windows when sensors are active, return a list of merged intervals with no overlaps. The input is unsorted. Optimize for the case where the list is nearly sorted and updates arrive in near-real-time.

Sample answer outline

Sort by start time then do a linear scan, merging when the current interval overlaps the last merged one. For near-sorted streaming data, a balanced BST (like a sorted list with bisect) lets you insert and query in O(log n) rather than re-sorting each time. The candidate should handle edge cases: empty list, single interval, all intervals identical, and intervals that share only a boundary point.

Reference implementation (python)

def merge(intervals: list[list[int]]) -> list[list[int]]:
    if not intervals:
        return []
    intervals.sort(key=lambda x: x[0])
    merged = [intervals[0]]
    for start, end in intervals[1:]:
        if start <= merged[-1][1]:
            merged[-1][1] = max(merged[-1][1], end)
        else:
            merged.append([start, end])
    return merged

Expect these follow-ups

• How would you store the merged intervals if new intervals arrive at 10,000 per second?
• How does your answer change if intervals can have open versus closed endpoints?

As asked

An integer array was sorted in ascending order and then rotated at an unknown pivot. Given the array and a target, return the index of the target or -1 if it is not present. You must achieve O(log n) time. How does your answer change if the array can contain duplicates?

Sample answer outline

Modified binary search: at each step, determine which half is sorted by comparing mid to left or right boundary. Check if the target falls in the sorted half; if so, narrow there; otherwise search the other half. With duplicates, when nums[left] == nums[mid] == nums[right] you cannot determine which side is sorted, so you must shrink the window by one on each side, giving O(n) worst case. The candidate should handle all edge cases: single element, no rotation, target at pivot.

Reference implementation (python)

def search(nums: list[int], target: int) -> int:
    lo, hi = 0, len(nums) - 1
    while lo <= hi:
        mid = (lo + hi) // 2
        if nums[mid] == target:
            return mid
        # Left half is sorted
        if nums[lo] <= nums[mid]:
            if nums[lo] <= target < nums[mid]:
                hi = mid - 1
            else:
                lo = mid + 1
        else:  # Right half is sorted
            if nums[mid] < target <= nums[hi]:
                lo = mid + 1
            else:
                hi = mid - 1
    return -1

Expect these follow-ups

• How do you find the index of the pivot point itself in O(log n)?
• What if the array can be rotated multiple times?

As asked

Given an integer array and an integer K, find the maximum sum of a contiguous subarray where you are allowed to remove at most K elements from within the subarray (they do not count toward the sum, but the subarray remains contiguous around them). What is the time and space complexity of your solution?

Sample answer outline

This extends Kadane's algorithm with a DP dimension for removals: dp[i][j] is the maximum subarray sum ending at index i with j removals used. Transition: dp[i][j] = max(dp[i-1][j] + nums[i], dp[i-1][j-1]) where the second option skips nums[i] at the cost of one removal. Running max over all i and j gives the answer. Time is O(n * K), space is O(K) with a rolling array. The candidate should verify base cases and note that when K is large enough to cover the entire subarray, negative elements can always be removed and the answer degenerates to the sum of all positives.

Expect these follow-ups

• How would you recover the actual subarray indices, not just the sum?
• What if K can be as large as N? Is there a simpler solution in that case?

As asked

Snowflake's coding interviews often start with a classic warm-up to establish baseline problem-solving fluency. Given an array of integers and a target integer, return the indices of the two numbers that add up to the target. You may assume exactly one solution exists and you may not use the same element twice. What is the most efficient approach and what is its time and space complexity?

Sample answer outline

The optimal solution uses a hash map: iterate the array once, storing each value's index. For each element, check whether (target - element) exists in the map before inserting the current element. This gives O(n) time and O(n) space. The candidate should also describe the naive O(n^2) brute-force and explain why the hash map is better. Bonus: mention edge cases like negative numbers, zeros, and the single-element input.

Reference implementation (python)

def two_sum(nums: list[int], target: int) -> list[int]:
    seen = {}  # value -> index
    for i, num in enumerate(nums):
        complement = target - num
        if complement in seen:
            return [seen[complement], i]
        seen[num] = i
    return []

Expect these follow-ups

• How would you solve it if the array were sorted and you needed O(1) extra space?
• How does this generalize to finding three numbers that sum to zero (3Sum)?

As asked

In Snowflake engineering interviews the top-K problem appears in contexts like finding the most queried tables or the most frequent values in a column sample. Given an integer array and an integer k, return the k most frequent elements. You do not need to return them in any particular order. The solution should be faster than O(n log n) overall.

Sample answer outline

The optimal approach uses a frequency map (O(n)) combined with a min-heap of size k (O(n log k)) to track the top k elements, giving O(n log k) total. Alternatively, bucket sort: create an array of lists indexed by frequency (since max frequency is n), fill it from the frequency map, and scan from the end to collect k elements in O(n). The candidate should compare the two and know when bucket sort is faster (when k is close to n).

Reference implementation (python)

import heapq
from collections import Counter

def top_k_frequent(nums: list[int], k: int) -> list[int]:
    freq = Counter(nums)
    # min-heap of size k
    return heapq.nlargest(k, freq.keys(), key=lambda x: freq[x])

Expect these follow-ups

• How would you solve this if the array were a data stream where elements arrive one at a time and you can only use O(k) space?
• What changes if the problem asks for the kth most frequent single element rather than the top k?

As asked

You are given a stream of track IDs representing plays arriving in real time. At any point, return the K most-played tracks. The stream is unbounded and K is small, say 10. What data structure gives you the best time complexity per insertion, and how do you handle ties?

Sample answer outline

A strong answer uses a hash map to count plays per track and a min-heap of size K to maintain the top-K candidates. Each insertion is O(log K). The candidate explains why a max-heap over all tracks would use more memory and why sorting the entire count map is too slow for a streaming context. Ties can be broken by insertion order or alphabetically, and the candidate picks one and states why.

Reference implementation (python)

import heapq
from collections import defaultdict

def top_k_tracks(stream, k):
    counts = defaultdict(int)
    heap = []  # min-heap of (count, track_id)

    for track_id in stream:
        counts[track_id] += 1
        # maintain heap of size k
        # TODO

    return [track for _, track in sorted(heap, reverse=True)]

Expect these follow-ups

• How would your approach change if K were 1 million instead of 10?
• How would you compute the top K tracks within a rolling 24-hour window?

As asked

Given a continuous stream of charge events where each event has a merchant_id and an amount in cents, return the top K merchants by total volume at any point in time. The stream is unbounded. How do you do this efficiently in memory?

Sample answer outline

The standard approach maintains a hash map of merchant_id to cumulative volume and a min-heap of size K. When a merchant's updated volume exceeds the heap minimum, replace the minimum. The candidate should analyze time complexity per event: O(log K) for heap operations. For the approximate version on truly unbounded streams, the Space-Saving or Count-Min-Sketch approach trades accuracy for bounded memory and is worth mentioning.

Reference implementation (python)

# Python sketch
import heapq
from collections import defaultdict

def top_k_merchants(stream, k):
    totals = defaultdict(int)
    heap = []  # (volume, merchant_id), min-heap

    for merchant_id, amount in stream:
        totals[merchant_id] += amount
        # maintain heap of size k
        heapq.heappush(heap, (totals[merchant_id], merchant_id))
        if len(heap) > k:
            heapq.heappop(heap)

    return sorted(heap, reverse=True)

Expect these follow-ups

• How does your answer change if K is 1 million and the number of distinct merchants is 10 million?
• What if you needed the top-K over a sliding 24-hour window instead of all time?

As asked

Tesla's telemetry pipeline continuously receives sensor readings from the fleet, and on-call engineers need the real-time median of a signal (such as battery temperature) to detect fleet-wide anomalies without waiting for a batch job. Design a class that continuously ingests a stream of integers and, at any point, returns the median of all integers seen so far. Both addNum(int num) and findMedian() must be as fast as possible.

Sample answer outline

The solution uses two heaps: a max-heap for the lower half and a min-heap for the upper half. After each insertion, the heaps are rebalanced so they differ in size by at most one element. findMedian is O(1); addNum is O(log n). The candidate should explain why a sorted array or BST are inferior alternatives and mention that an augmented order-statistic tree would allow arbitrary percentile queries, which is relevant to Tesla's telemetry use case.

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)
        heapq.heappush(self.hi, -heapq.heappop(self.lo))
        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 does this change if you only need the median of a sliding window of the last 1000 values?
• What if the data stream contains floating-point sensor readings with duplicates?

As asked

You are processing a live stream of numeric engagement scores (likes, retweets). Implement a data structure that supports adding a new score in O(log n) and returning the current median in O(1) at any point in the stream.

Sample answer outline

A strong answer maintains two heaps: a max-heap for the lower half and a min-heap for the upper half, keeping them balanced within 1 element of each other. On each insert, the candidate should correctly route the new element and rebalance if sizes diverge. Median retrieval is the top of the larger heap for odd total, or the average of both tops for even total.

Reference implementation (python)

import heapq

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

    def addNum(self, num: int) -> None:
        heapq.heappush(self.lo, -num)
        heapq.heappush(self.hi, -heapq.heappop(self.lo))
        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

• If scores can only be integers in the range 0 to 100, can you do better than two heaps?
• How does your solution change if you need the median only over a sliding window of the last 10,000 observations?

As asked

Given a stream of tweets, implement a function that returns the number of times a specific word appeared in the last 5 minutes. Tweets arrive at roughly 10,000 per second and each tweet can contain multiple words. The count must be accurate to within 1 second of the actual 5-minute window.

Sample answer outline

A strong answer uses a circular buffer of 300 one-second buckets (5 min x 60 sec), incrementing the current second's bucket on each match and summing all 300 on a query. The candidate should handle the edge case where multiple seconds elapse between updates (reset stale buckets), discuss the memory footprint per tracked word, and compare this approach to a sorted deque for exact sliding windows.

Expect these follow-ups

• You now need to track not one word but the top 100 words simultaneously. How does your data structure scale?
• What is the maximum error in your count and when does it occur?