Tuesday 12 June 2012

Interviewstreet Median Challenge 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 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.

6 comments:

  1. This comment has been removed by the author.

    ReplyDelete
    Replies
    1. This comment has been removed by the author.

      Delete
  2. sir could u plz tell for what case my code is giving wrong answer...i am getting correct answer for 1st and 10th case and wrong answer for 8 cases in between.Here is my code,plz reply

    https://www.friendpaste.com/1PXcleQ4KGI69Zc7saVDCu

    ReplyDelete
    Replies
    1. gaurav, i would advise you to re-think of solving this problem using other any data structure(not array). During insertion, it takes o(n) time to shift elements according to your code, which is not feasible.
      Even if you will correct your code, it will not pass all test cases because of time limit error.

      I think one of the reasons you are getting wrong answers is because trailing zeroes will be printed as per your code.

      Share your views.

      Delete
  3. hi sachin,
    i used arralist for this solution...for insertion and deletion complexity is o(log n)and for retriving the median it is 0(1). but only first test case got passed..for other test cases it is giving wrong answer. can u please have a look?.



    import java.util.ArrayList;
    import java.util.Collections;
    import java.util.List;
    import java.util.Scanner;


    public class Solution {

    List l=new ArrayList();

    /**
    * this function add function in sorted order
    * @param number
    */
    public void add(int number){
    int index=Collections.binarySearch(l, number);
    if(index >= 0){
    l.add(index+1,number);
    }else{
    l.add(Math.abs(index)-1,number);
    }
    }

    /**
    * this function remove the specified element
    * @param number
    * @return
    */
    public int remove(int number){
    int index=Collections.binarySearch(l, number);
    if(index>=0){
    l.remove(index);
    return index;
    }else{
    return -1;
    }
    }

    public void PrintMedian(int i){
    if(l.size()==0){
    System.out.println("Wrong!");
    }
    else if(i==-1){
    System.out.println("Wrong!");
    }else{
    int size=l.size();
    if(size%2==1){
    int index=size/2;
    System.out.println(l.get(index));
    }else{
    int index=size/2;
    double median=((double)((l.get(index) + l.get(index-1))))/2;
    System.out.println(median);
    }
    }
    }
    public static void main(String[] args) {
    Solution s=new Solution();
    Scanner sc=new Scanner(System.in);
    int total_number=sc.nextInt();
    sc.nextLine();
    while(total_number>0){
    total_number--;
    String input=sc.nextLine();
    //System.out.println("input string::" + input);
    String[] split=input.split(" ");
    //System.out.println("sirst character::" + split[0] + "second character::" + split[1]);
    if(split[0].equals("a")){
    s.add(Integer.parseInt(split[1]));
    s.PrintMedian(0);
    }
    if(split[0].equals("r")){
    int index=s.remove(Integer.parseInt(split[1]));
    s.PrintMedian(index);
    }
    //System.out.println("next line");
    }


    }
    }

    ReplyDelete
  4. C++ vector with lower_bound, insert and erase can be used directly to solve this problem efficiently. The catch is overflow bits :) Watch out.

    ReplyDelete