Interviewstreet Median Challenge Part 2 Solution C++

InterviewStreet Median Challenge 

Problem Statement

The median of M numbers is defined as the middle number after sorting them in order, if M is odd or the average number of the middle 2 numbers (again after sorting) if M is even. Given an empty number list at first. Then you can add or remove some number from the list. For each add or remove operation, output the median of numbers in the list.

Example : For a set of m = 7 numbers, { 9, 2, 8, 4, 1, 3, 10 } the median is the third number in sorted set { 1, 2, 3, 4, 8, 9, 10 } which is 4. Similarly for set of m = 4, { 4, 1, 10, 3 }, the median is the average of second and the third element in the sorted set { 1, 3, 4, 10 } which is (3+4)/2 = 3.5  

Input: The first line contains n, the number of operations. The next n lines is either "a x" or "r x" which indicates the operation is add or remove.

Output: For each operation: output the median after doing the operation. If the operation is remove and the number x is not in the list, output "Wrong!" in a single line. If the result is an integer DO NOT output decimal point. And if the result is a double number, DO NOT output trailing 0s.

Other conditions:   0 < n <= 100,000 and for each "a x" or "r x" , x will fit in 32-bit integer.

Input:

7

r 1

a 2

a 3

a 2

r 2

r 3

r 2

Output:

Wrong!

2

2.5

2

2.5

2

Wrong!

Note: As evident from the last line of the input, if after remove operation the list becomes empty you have to print "Wrong!" ( quotes are for clarity ).

Algorithm

1) Use two multisets - first one will keep small n/2 numbers, minset and other one will keep next n/2 numbers, maxset.
2) For insert operation:
     if the number is greater than max of minset, add it to maxset
     else add it to minset
3) For remove operation:
     if the number is in minset, remove it
     else if number is in maxset, remove it
     else do nothing
4) After every insert/remove operation, adjust size of both sets i.e. make it n/2
     if(size-of-maxset > size-of-minset) remove first element from maxset and insert it in minset
     if(size-of-minset > size-of-maxset + 1) remove last element from minset and insert it in maxset
5) Calculate Median as..
     if(size of both minset and maxset is zero) No median
     else if (size of minset > size of maxset) max of minset is median
     else if (size of minset = size of maxset) avg of max of minset and min of maxset is median

If you have a different approach in mind, please share it in comments section for our readers. 

Solution

// All test cased passed.

#include<iostream>
#include<set>

using namespace std;

int main()
{
int n;
cin>>n;
multiset<int> s1,s2;
int b; char c;
int flag = 0;
long long int median=0;
multiset<int>::iterator it;
for(int i=0;i<n;i++) {
    flag = 0;
    cin >> c >> b;
    if(c=='a') {
       if(s1.size() == 0) s1.insert(b);
       else {
          it = s1.end(); it--;
          int max = *it;
          if(b > max) s2.insert(b);
          else s1.insert(b);
       }
    }
    else if (c == 'r') {
       it = s1.find(b);
       if(it!=s1.end() && *it == b) s1.erase(it);
       else {
          it = s2.find(b);
          if(it!=s2.end() && *it == b) s2.erase(it);
          else flag = 1;
       }
    }
 
    // adjust size(make it n/2) of both two sets
    if(s2.size() > s1.size()) {
       it = s2.begin();
       s1.insert(*it);
       s2.erase(it);  
    }
    if(s1.size() > s2.size()+1) {
       it = s1.end();it--;
       s2.insert(*it);
       s1.erase(it);
    }
  
    // finding median
    if(flag == 1 || (s1.size() == 0 && s2.size() == 0))
      cout << "Wrong!\n";
    else if(s1.size() != s2.size()) {
       if(s1.size() > 0) {
         it = s1.end(); it--;
         cout << *it << endl;
       }
       else if(s2.size() > 0) {
         // program might not enter here
         it = s2.begin();
         cout << *it << endl;
       }
    }
    else if(s1.size()== s2.size()){
       it = s1.end(); it--;
       median = *it;
       it = s2.begin();
       median += *it;
       if(median%2==0)
              printf("%.0lf\n", median/2.);
       else
              printf("%.1lf\n", median/2.);
    }
    else cout << "Wrong!\n";
}


} 

Time Complexity:

Insertion : O(logn)
Deletion : O(logn)
Median : O(1)



View another algorithm for Median problem here:
justprogrammng.blogspot.in/2012/06/interviewstreet-median-challenge.html