Interview Question

Interview(Student Candidate)

Design a class to record a lot of ints, and make it

  efficient to retrieve the median.

Interview Answer

2 Answers


class EffMed { public: void add(int n) { vector<int>::iterator it = els.begin(); while(it != els.end() && *it < n) ++it; els.insert(it, n); } void remove(int index) { els.erase(els.begin() + index); } float median() { int medIndex = els.size() >> 1; if(medIndex << 1 == els.size()) return (els[medIndex - 1] + els[medIndex]) / 2.0; else return els[medIndex]; } private: vector<int> els; };

Asa on Jul 9, 2012

Use two heaps (min and max) and maintain equal number of elements in it (at most one more element). Median will be always on top of one of heap or average of two top elements. So request will be O(1) time and insertion will be O(logN)

Konstantin on Aug 14, 2012

Add Answers or Comments

To comment on this, Sign In or Sign Up.