Data scientist data structures interview questions

As asked

Design a data structure that supports two operations: addNum(int num) adds a number to the data stream, and findMedian() returns the median of all numbers added so far. What is the time complexity of each operation?

Sample answer outline

The classic solution uses two heaps: a max-heap for the lower half and a min-heap for the upper half, keeping them balanced in size. addNum is O(log n) and findMedian is O(1). The candidate should explain the balancing logic: after each insert, if the heaps differ in size by more than 1, move the top element from the larger heap to the smaller. Edge cases: empty stream, single element, even versus odd total count.

Expect these follow-ups

• How would you find the median of a sliding window of the last k elements?
• How does your solution handle integer overflow if values can be very large?

As asked

Given a linked list, return the node where a cycle begins, or null if there is no cycle. Do it in O(n) time and O(1) space. Then explain how you would test this function, including all edge cases you would include.

Sample answer outline

Floyd's cycle detection: fast and slow pointers meet inside the cycle. Then reset one pointer to the head and advance both one step at a time; they meet at the cycle start. For testing, the candidate should cover: no cycle, cycle at the tail, cycle at the head (full circular list), cycle at an intermediate node, single node with self-loop, and a two-node list with and without a cycle.

Reference implementation (python)

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

def detectCycle(head: ListNode | None) -> ListNode | None:
    slow, fast = head, head
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
        if slow is fast:
            slow = head
            while slow is not fast:
                slow = slow.next
                fast = fast.next
            return slow
    return None

Expect these follow-ups

• Why do the two pointers meet exactly at the cycle start? Prove it mathematically.
• How would your approach change if the list were doubly linked?

As asked

Design a data structure that supports two operations: addNum(int num) adds a number to the data stream, and findMedian() returns the median of all numbers added so far. What is the time complexity of each operation?

Sample answer outline

The classic solution uses two heaps: a max-heap for the lower half and a min-heap for the upper half, keeping them balanced in size. addNum is O(log n) and findMedian is O(1). The candidate should explain the balancing logic: after each insert, if the heaps differ in size by more than 1, move the top element from the larger heap to the smaller. Edge cases: empty stream, single element, even versus odd total count.

Expect these follow-ups

• How would you find the median of a sliding window of the last k elements?
• How does your solution handle integer overflow if values can be very large?

As asked

Given a linked list, return the node where a cycle begins, or null if there is no cycle. Do it in O(n) time and O(1) space. Then explain how you would test this function, including all edge cases you would include.

Sample answer outline

Floyd's cycle detection: fast and slow pointers meet inside the cycle. Then reset one pointer to the head and advance both one step at a time; they meet at the cycle start. For testing, the candidate should cover: no cycle, cycle at the tail, cycle at the head (full circular list), cycle at an intermediate node, single node with self-loop, and a two-node list with and without a cycle.

Reference implementation (python)

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

def detectCycle(head: ListNode | None) -> ListNode | None:
    slow, fast = head, head
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
        if slow is fast:
            slow = head
            while slow is not fast:
                slow = slow.next
                fast = fast.next
            return slow
    return None

Expect these follow-ups

• Why do the two pointers meet exactly at the cycle start? Prove it mathematically.
• How would your approach change if the list were doubly linked?