The Three Questions That Tanked My Onsite
Three problems from a senior backend onsite I failed in 2024. A median-of-stream I overcomplicated, a string compression where I missed a case, and a queue-with-min I never finished. Plus what I should have written.
By @sanjayward
April 17, 2026
·
Updated August 11, 2026
783 views
21
4.4 (13)
Round 1: design a data structure that supports add(x) and median() on a stream of integers. I jumped to a balanced BST and ran out of time. The interviewer wanted two heaps.
What I actually wrote at the board
I started sketching an AVL tree with order statistics. Forty minutes in I had insertion working and no median; the interviewer politely moved on.
class MedianFinder:
def __init__(self):
self.data = []
def add(self, x):
self.data.append(x)
self.data.sort()
def median(self):
n = len(self.data)
if n == 0:
return None
if n % 2:
return self.data[n // 2]
return (self.data[n // 2 - 1] + self.data[n // 2]) / 2Round 3: run-length encode a string, but only return the encoded version if it is strictly shorter than the original. I missed the case where the encoding ties the original.
What I actually wrote at the board
I returned encoded when len(encoded) <= len(original) and lost three minutes when the interviewer typed aabb and my function returned a2b2 instead of aabb.
def compress(s):
if not s:
return s
out = []
count = 1
for i in range(1, len(s)):
if s[i] == s[i - 1]:
count += 1
else:
out.append(s[i - 1] + str(count))
count = 1
out.append(s[-1] + str(count))
encoded = "".join(out)
# Buggy: <= ties and returns the encoded form even when no shorter.
return encoded if len(encoded) <= len(s) else sRound 4: implement a queue with enqueue, dequeue, and get_min (the min of all currently-enqueued elements). All three must be O(1) amortized. I got partway and ran out of time on the dequeue side.
What I actually wrote at the board
I had a MinStack template in my head but blanked on translating it to a queue. The trick (two stacks) only landed for me on the train ride home.
from collections import deque
class MinQueue:
def __init__(self):
self.q = deque()
def enqueue(self, x):
self.q.append(x)
def dequeue(self):
return self.q.popleft()
def get_min(self):
return min(self.q) if self.q else None