Median Finder Class (OOP)

Median Finder Class (OOP)

Hard Programming Interview OOP 28 views
Explanation Complexity

Problem Statement

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.

Example

7
ADD 5
ADD 2
MEDIAN
ADD 10
ADD 1
MEDIAN
MEDIAN
2
2
2

Constraints

q

Input / Output Format

Input Format
First line q. Next q lines commands.
Output Format
Outputs for MEDIAN.
Constraints
q

Examples

Input:
7 ADD 5 ADD 2 MEDIAN ADD 10 ADD 1 MEDIAN MEDIAN
Output:
2 2 2

Example Solution (Public)

Programming Interview 
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))

Official Solution Code

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))
Please login to submit solutions.
Editor
Output

                                        

                                    

                                    

                                        

                                                                                    
Please login to submit solutions.