Interview street Median challenge [closed]

Question

I was trying to solve the Median challenge at Interviewstreet.com.

I wasn't able to pass most of the test cases. But according to my understanding my code should work fine.

Here is the question: https://www.interviewstreet.com/challenges/dashboard/#problem/4fcf919f11817

Here is my code:

    /* Sample program illustrating input and output */

    import java.util.*;

    class Solution{
public static void main( String args[] ){

     // helpers for input/output        

    Scanner in = new Scanner(System.in);

    int N;
    N = in.nextInt();

    String s[] = new String[N];
    int x[] = new int[N];
    ArrayList<Integer> items=new ArrayList<Integer>();
    float result[]=new float[N];
    //int itemindex=-1;
    for(int i=0; i<N; i++){
        s[i] = in.next();
        x[i] = in.nextInt();

        switch(s[i].charAt(0))
        {

        case 'r':
            if(items.size()<=1)
            {
                result[i]=-1;

            }
            else
            {
                items.remove((Integer)x[i]);
                int itemindex=items.size();
                Collections.sort(items);
                if((itemindex)%2==0)
                {
                    result[i]=(float)         ((items.get((itemindex/2))+items.get(((itemindex)/2)-1))/2.0);


                }
                else
                {
                    result[i]=items.get((itemindex-1)/2);
                }

            }
            break;

        case 'a':
            items.add(x[i]);
            int itemindex=items.size();
            Collections.sort(items);
            if((itemindex)%2==0)
            {
                result[i]=(float)((items.get((itemindex/2))+items.get(((itemindex)/2)-1))/2.0);


            }
            else
            {
                result[i]=items.get((itemindex-1)/2);
            }

            break;



        }

    }

    for(int j=0;j<N;j++)
    {
        if(result[j]==-1)
        {
            System.out.println("Wrong!");
        }
        else
        {
            if((result[j]*10)%10==0)
            {
            System.out.println((int)(result[j]));
            }
            else
            {
                System.out.println(result[j]);
            }
        }

    }





}
    }

I would highly appreciate if someone could help me find out the test cases which will fail for my code.

Thanks.

Answer 1

An additional point to the ones mentioned by @palacsint is the check for the object removal: according to the challenge:

If the operation is remove and the number x is not in the list, output "Wrong!" in a single line

your code does not check for that: here is what you have:

if(items.size()<=1)
            {
              result[i]=-1;
            }
else .....

You are marking wrong when the list has a single item or is empty. Obviously this is not what the challenge requires. Therefore, you should discard this "if" block and only check the return value from the remove on the list:

boolean ok= items.remove((Integer)x[i]);
if (!ok){
  result[i]=-1;
}

Answer 2

1. The following is duplicated, you could extract it out a method:

   int itemindex = items.size();
   Collections.sort(items);
   if (itemindex %2 == 0) {
       result[i]=(float)((items.get((itemindex/2))+items.get(((itemindex)/2)-1))/2.0);
   } else {
       result[i]=items.get((itemindex-1)/2);
   }
   

2. ArrayList<...> reference types should be simply List<...>. See: Effective Java, 2nd edition, Item 52: Refer to objects by their interfaces

   List<Integer> items = new ArrayList<Integer>();
   

Three bugs:

1. Input:

   2
   a 214748367
   a 214748365
   

   Output:

   2.14748368E8
   2.14748368E8
   

2. Input:

   2
   a 2147483647
   a 2147483645
   

   Output:

   2147483647
   -2
   

3. Processing the output of the following code takes more than the allowed 5 seconds:

   for (int i = 100000; i > 0; i--) {
       System.out.println("a " + i);
   }
   

Some useful reading:

• Why not use Double or Float to represent currency?
• Effective Java, 2nd Edition, Item 48: Avoid float and double if exact answers are required