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 only for clarity and not to be printed).
Algorithm
Idea is to use previous median value and pointer to find new median value instead of recalculating at every add or remove operation.
1) Use multiset which always keep elements in order and allow duplicates. In other words maintain sorted list somehow.
2) Let 'prev' pointer point to previous median value for odd size-of-set or 2nd element used to calculate average in case of even size-of-set and Let b be the element that will be inserted/deleted
from the set.
2) If the operation is add
2.1) Insert this element into set and then calculate the median
2.2) if the size of set is 1 then first element will be the median
2.3) else if b >= *prev and size-of-set is even now, increment prev to point to 2nd element for
this median
2.4) else if b < *prev and size-of-set is odd now, decrement prev to point to new median.
3) If the operation is remove
3.1) First calculate the new median then remove the element.
3.2) If the size of set is 0 can't remove.
3.3) else if the element doesn't exist in set then also can not remove.
3.4) else if b = *prev and size of set is odd increment the pointer to point to 2nd element
for new median else if size is even and previous to prev and prev are both same element
then do nothing else decrement the pointer to point to new median.
3.5) else if b>=*prev && s.size()%2 == 0 decrement the prev pointer.
3.6) else if b<=*prev && s.size()%2 != 0 increment the prev pointer.
3.6) Now you can remove the element.
Solution
This solution is correct now. All test cases passed.
You can also have a look at another blog in which I have posted another good approach to solve this problem using two multisets unlike using one multiset as in this solution. Have a look here
http://justprogrammng.blogspot.com/2012/06/interviewstreet-median-challenge-part-2.html.
// All test cases passed
#include<iostream>
#include<set>
using namespace std;
int main()
{
int n;
cin>>n;
multiset<int> s;
int b; char c;
long long median=0;
static multiset<int>::iterator it, prev,temp;
for(int i=0;i<n;i++) {
cin >> c >> b;
if(c=='a') {
s.insert(b);
if(s.size()==1) prev = s.begin();
else if(b >= *prev && s.size()%2 == 0) prev++;
else if(b < *prev && s.size()%2 != 0) prev--;
}
else if(c=='r' && s.size() > 0) {
it = s.find(b);
if(it == s.end() || *it != b) { cout << "Wrong!\n"; continue;}
else if(*prev == b) {
if(s.size()%2 != 0) prev++;
else {
temp = prev; temp--;
if(*temp != b) prev--;
}
}
else if(b>=*prev && s.size()%2 == 0) prev--;
else if(b<=*prev && s.size()%2 != 0) prev++;
s.erase(it);
}
// to print median
if(s.size()==0) cout << "Wrong!\n";
else if(s.size()%2!=0) cout << *prev << endl;
else {
median = *prev;
prev--;
median = (median+*prev);
if(median%2==0)
printf("%.0lf\n", median/2.);
else
printf("%.1lf\n", median/2.);
prev++;
}
}
}
Time Complexity
Insertion - O(logn)
Deletion - O(logn)
Median - O(1)
n number of inputs each either add or remove x, in multiset(c++) for insertion/remove O(logn) and O(1) to calculate new median. So total time complexity O(n*logn) where n is no of inputs plus max possible element in set also.
Another better way to do the same problem using 2 multisets....which will also work for all test cases.....
http://justprogrammng.blogspot.com/2012/06/interviewstreet-median-challenge-part-2.html.
