Median Finder Class
Programming Interview
Hard
5 views
Problem Description
You will receive q commands: ADD x or MEDIAN. Create MedianFinder class using two heaps. For MEDIAN output lower median (floor for even count).
Input Format
First line q. Next q lines commands.
Output Format
Outputs for MEDIAN.
Sample Test Case
Input:
7
ADD 5
ADD 2
MEDIAN
ADD 10
ADD 1
MEDIAN
MEDIAN
Official Solution
import sys,heapq
lines=sys.stdin.read().splitlines()
if not lines: sys.exit(0)
q=int(lines[0].strip())
class MedianFinder:
def __init__(self):
self.lo=[]
self.hi=[]
def add(self,x):
if not self.lo or x<=-self.lo[0]:
heapq.heappush(self.lo,-x)
else:
heapq.heappush(self.hi,x)
if len(self.lo)>len(self.hi)+1:
heapq.heappush(self.hi,-heapq.heappop(self.lo))
elif len(self.hi)>len(self.lo):
heapq.heappush(self.lo,-heapq.heappop(self.hi))
def median(self):
return -self.lo[0] if self.lo else None
mf=MedianFinder()
out=[]
for i in range(1,1+q):
parts=(lines[i] if i<len(lines) else '').split()
if not parts: continue
if parts[0]=='ADD':
mf.add(int(parts[1]))
else:
v=mf.median()
out.append(str(v) if v is not None else 'EMPTY')
sys.stdout.write('\
'.join(out))
Solutions (0)
No solutions submitted yet. Be the first!
No comments yet. Start the discussion!