Google

  www.google.com
Work in HR? Unlock Free Profile

Google Software Engineer Interview Question (student candidate)

"Design a class to record a lot of ints, and make it efficient to retrieve the median."
Add Tags [?]
Answer

Part of a Software Engineer Interview Review - one of 3,031 Google Interview Reviews

Answers & Comments

0
of 2
votes
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
0
of 0
votes
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

To comment on this question, Sign In with Facebook or Sign Up

Tags are like keywords that help categorize interview questions that have something in common.