2
\$\begingroup\$

I'm trying to compete on HackerRank and my answer got accepted, but the times are not so good. I have a friend who sent the answer in C# too but somehow made it a lot faster. I'm wondering what can I do to improve it.

using System;
using System.Collections.Generic;
using System.IO;
using System.Text;
class Solution {

   static void Main(String[] args) {
      int N;
      StringBuilder st= new StringBuilder();

      N = Convert.ToInt32(Console.ReadLine());
      int[] x = new int[N];
       List<double> a= new List<double>();
      string[] s = new string[N];

      for(int i=0; i<N ;i++){

         string tmp = Console.ReadLine(); 
         string[] split = tmp.Split(new Char[] {' ', '\t', '\n'});

         s[i] = split[0].Trim();
         x[i] = Convert.ToInt32(split[1].Trim());
          bool r=true;

          if(s[i]=="r"){
              int index= a.BinarySearch(x[i]);
              if(index>=0){
                  a.RemoveAt(a.LastIndexOf(x[i]));    
              }
              else{
              r=false;
              }

          }else{
              var index = a.BinarySearch(x[i]);
                if (index < 0) index = ~index;
                  a.Insert(index,x[i]);
          }
          if(!r || a.Count==0){
              st.AppendLine("Wrong!");

          }
          else{
          st.AppendLine(calcularModa(a).ToString());
          }
      }      
       Console.WriteLine(st.ToString());

   }
   static double calcularModa(List<double> a){

   int i= a.Count/2;
       if(a.Count % 2 !=0){
           return a[i];
       }else{
           return ((a[i - 1] + a[i]))/2;
       }

    }
}
\$\endgroup\$
3
  • 3
    \$\begingroup\$ What's this supposed to do? I can't make any sense of it. You should use descriptive variable names. \$\endgroup\$
    – Bobson
    May 2, 2013 at 18:51
  • \$\begingroup\$ it calculates the median for this challenge hackerrank.com/challenges/median \$\endgroup\$ May 2, 2013 at 19:01
  • \$\begingroup\$ which is your goal time? \$\endgroup\$ May 2, 2013 at 23:25

4 Answers 4

3
\$\begingroup\$

Besides of the pointed by Jesse, I'd like to comment on a couple of things that might improve your code. First, since all that you are parsing is a string, you don't need to call Convert.ToInt32(str), just int.Parse(str). This is what's really going on, you're just taking a few more extra method calls. But where I see you're losing most of your time is in the following:

int index= a.BinarySearch(x[i]);
if(index>=0){
    a.RemoveAt(a.LastIndexOf(x[i]));
    //...
}

Notice that you are looking for the index with Binary Search O(log n) and then you are again looking for the index, but not only once more, but this time in O(n). Instead, you should:

int index= a.BinarySearch(x[i]);
if(index>=0){
    a.RemoveAt(index));
//...
}
\$\endgroup\$
6
  • \$\begingroup\$ Hey thanks, that looks like could help, i will test it later. \$\endgroup\$ May 2, 2013 at 20:45
  • \$\begingroup\$ Also, make sure your array is sorted. BinarySearch() isn't efficient on unsorted arrays. \$\endgroup\$
    – Bobson
    May 2, 2013 at 21:40
  • \$\begingroup\$ Yes its sorted, and it improved a lot my time, at hardest test cases it went from 3.5 seconds to 0.6 \$\endgroup\$ May 3, 2013 at 14:41
  • \$\begingroup\$ I'm confused by this. Isn't RemoveAt O(N)? \$\endgroup\$ May 3, 2013 at 15:19
  • 1
    \$\begingroup\$ @EnriqueMedina, I get that. I'm just surprised it made as much of a difference as Luis is reporting. \$\endgroup\$ May 3, 2013 at 16:45
3
\$\begingroup\$

There are a lot of stylistic changes I'd normally suggest, but I'm going to forgo that to mention three very simple optimizations:

  • remove new Char[] { ' ', '\t', '\n' } from within the loop. No need to recreate this object every time as it's an invariant.
  • you know the maximum size of the a list, so create it with that capacity in mind to prevent resizing as it's being accessed: List<double> a= new List<double>(N);
  • Repeated code in both the if and else branches pulled out (no performance optimization, but basic tenet of DRY (Don't Repeat Yourself)): int index= a.BinarySearch(x[i]);

Resulting code looks like this:

using System;
using System.Collections.Generic;
using System.IO;
using System.Text;
class Solution {

   static void Main(String[] args) {
      int N;
      StringBuilder st= new StringBuilder();

      N = Convert.ToInt32(Console.ReadLine());
      int[] x = new int[N];
       List<double> a= new List<double>(N);
      string[] s = new string[N];

      Char[] splitChars = new Char[] { ' ', '\t', '\n' };

      for(int i=0; i<N ;i++){

         string tmp = Console.ReadLine(); 
         string[] split = tmp.Split(splitChars);

         s[i] = split[0].Trim();
         x[i] = Convert.ToInt32(split[1].Trim());
          bool r=true;

          int index= a.BinarySearch(x[i]);
          if(s[i]=="r"){
              if(index>=0){
                  a.RemoveAt(a.LastIndexOf(x[i]));    
              }
              else{
              r=false;
              }

          }else{
                if (index < 0) index = ~index;
                  a.Insert(index,x[i]);
          }
          if(!r || a.Count==0){
              st.AppendLine("Wrong!");

          }
          else{
          st.AppendLine(calcularModa(a).ToString());
          }
      }      
       Console.WriteLine(st.ToString());

   }
   static double calcularModa(List<double> a){

   int i= a.Count/2;
       if(a.Count % 2 !=0){
           return a[i];
       }else{
           return ((a[i - 1] + a[i]))/2;
       }

    }
}
\$\endgroup\$
1
  • \$\begingroup\$ It improved a little but still somehow a lot slower that the other implementation, i will try to get the other code to see why it could be faster, thanks for reviewing :) \$\endgroup\$ May 2, 2013 at 18:48
1
\$\begingroup\$
     s[i] = split[0].Trim();
     x[i] = Convert.ToInt32(split[1].Trim());

There's no point in storing these values in the array. You use them right away, just store them in locals.

The problem for speed is here:

              a.RemoveAt(a.LastIndexOf(x[i]));    

and here:

              a.Insert(index,x[i]);

But of those will have to shift over elements in memory. It will be O(n) where n is the number of elements in the list. So that's rather expensive. Basically, you can't use a list do this. What you need to think about is what datastructure gives you:

  1. Fast insertion
  2. Fast deletion by value
  3. Determination of the middle

The list gives you 3, but not 1 and 2.

\$\endgroup\$
3
  • \$\begingroup\$ Not storing the values in the array did not provide any improvement, and what data structure would you recommend? \$\endgroup\$ May 3, 2013 at 14:53
  • \$\begingroup\$ @LuisTellez, the point of the exercise is for you to think about and figure it out yourself. I've solved this problem, all I'm willing to give you is hints about it. \$\endgroup\$ May 3, 2013 at 14:59
  • \$\begingroup\$ I solved it before coming here, i just wanted tips to improve times, but its already accepted and with Enrique Medina improvement it did improve a lot my times. \$\endgroup\$ May 3, 2013 at 15:30
0
\$\begingroup\$

Maybe you can use a HashSet instead of a List since HashSet has a O(1) time complexity for lookups; this way you won't need a binary search O(log2N).

See for example this stackoverflow answer

Hope this is useful.

\$\endgroup\$
1
  • \$\begingroup\$ The HashSet contains no duplicate elements, and whose elements are in no particular order, so it does not work for this problem. \$\endgroup\$ May 3, 2013 at 14:45

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.