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\$
  • 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\$ – Luis Tellez May 2 '13 at 19:01
  • \$\begingroup\$ which is your goal time? \$\endgroup\$ – Enrique Medina 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));
//...
}
| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ Hey thanks, that looks like could help, i will test it later. \$\endgroup\$ – Luis Tellez 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\$ – Luis Tellez May 3 '13 at 14:41
  • \$\begingroup\$ I'm confused by this. Isn't RemoveAt O(N)? \$\endgroup\$ – Winston Ewert 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\$ – Winston Ewert 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;
       }

    }
}
| improve this answer | |
\$\endgroup\$
  • \$\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\$ – Luis Tellez 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.

| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ The HashSet contains no duplicate elements, and whose elements are in no particular order, so it does not work for this problem. \$\endgroup\$ – Luis Tellez 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.

| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ Not storing the values in the array did not provide any improvement, and what data structure would you recommend? \$\endgroup\$ – Luis Tellez 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\$ – Winston Ewert 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\$ – Luis Tellez 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.