search

interview-preparation / what-we-do

0 stars 8 forks source link

[Hard] interview questions #20 #173

Open rygh4775 opened 4 years ago

rygh4775 commented 4 years ago

Continuous Median: Numbers are randomly generated and passed to a method. Write a program to find and maintain the median value as new values are generated.

btakeya commented 4 years ago
  1. make numbers generated into two groups by heap: smaller(max-heap) and bigger(min-heap).
  2. when new number comes, add number into appropriate group 2-1. no number: bigger group 2-2. single number: smaller group 2-3. bigger > smaller: sort [pop from smaller group (biggest), pop from bigger group (smallest), new value], add biggest into bigger group, add smaller 2 into small group 2-4. bigger == smaller: sort [pop from smaller group (biggest), pop from bigger group (smallest), new value], add smallest into smaller group, add bigger 2 into bigger group
  3. when all numbers are 3-1. even -> peek from max heap 3-2. odd -> peek from min heap 
    
import heapq

max_heap_buf = [] min_heap_buf = []

def size_maxheap(): return len(max_heap_buf)

def size_minheap(): return len(min_heap_buf)

def push_maxheap(value): heapq.heappush(max_heap_buf, (-value, value))

def pop_maxheap(): return heapq.heappop(max_heap_buf)[1]

def peek_maxheap(): return max_heap_buf[0][1] if len(max_heap_buf) > 0 else None

def push_minheap(value): heapq.heappush(min_heap_buf, value)

def pop_minheap(): return heapq.heappop(min_heap_buf)

def peek_minheap(): return min_heap_buf[0] if len(min_heap_buf) > 0 else None

if name == 'main': while True: v = int(input()) if peek_minheap() == None: push_minheap(v) print('{} / {} / {}'.format(peek_minheap(), max_heap_buf, min_heap_buf)) elif peek_maxheap() == None: t = pop_minheap() push_minheap(v if v > t else t) push_maxheap(t if v > t else v) print('{} / {} / {}'.format(peek_maxheap(), max_heap_buf, min_heap_buf)) elif size_minheap() > size_maxheap(): tmp = [v, pop_maxheap(), pop_minheap()] tmp.sort() push_maxheap(tmp[0]) push_maxheap(tmp[1]) push_minheap(tmp[2]) print('{} / {} / {}'.format(peek_maxheap(), max_heap_buf, min_heap_buf)) else: # size_minheap() == size_maxheap(), should not be happen 'size_minheap() < size_maxheap()' case tmp = [v, pop_maxheap(), pop_minheap()] tmp.sort() push_maxheap(tmp[0]) push_minheap(tmp[1]) push_minheap(tmp[2]) print('{} / {} / {}'.format(peek_minheap(), max_heap_buf, min_heap_buf))