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
  • 2
    \$\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 '13 at 18:51
  • \$\begingroup\$ it calculates the median for this challenge hackerrank.com/challenges/median \$\endgroup\$ May 2 '13 at 19:01
  • \$\begingroup\$ which is your goal time? \$\endgroup\$ May 2 '13 at 23:25
2
\$\begingroup\$

Besides of the pointed by Jesse, I'd like to comment 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'r just taking a few more extra method calls. But where I see you'r loosing 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(logn) and then your 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 '13 at 20:45
  • \$\begingroup\$ Also, make sure your array is sorted. BinarySearch() isn't efficient on unsorted arrays. \$\endgroup\$
    – Bobson
    May 2 '13 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 '13 at 14:41
  • \$\begingroup\$ I'm confused by this. Isn't RemoveAt O(N)? \$\endgroup\$ May 3 '13 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 '13 at 16:45
2
\$\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 '13 at 18:48
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 '13 at 14:45
0
\$\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 '13 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 '13 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 '13 at 15:30

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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