C# code is too inefficient, causing timeout on hackerrank

Question

1.00/5 (2 votes)

See more:

Hey Guys,

I had some extra time to spare, so I was doing the coding challenge by HackerRank and on Day 8 of the challenge no matter how hard I tried I cant make the code run more efficiently as some of the test cases always "TimeOut".

If you guys could spare 2 minutes looking at my code and seeing where it is inefficient please let me know :)

Basically, in the first for loop I am reading in Key Value Pairs, in the second for loop I am reading in potential keys, if they have a value then output key=value, else output "Not found". the variable "n" tells me how many key value pairs i am reading in and how many potential keys I am reading in as well.

using System;
using System.Collections.Generic;
using System.IO;
using System.Linq;
using System.Collections;

class Solution {
    static void Main(String[] args) {
        /* Enter your code here. Read input from STDIN. Print output to STDOUT. Your class should be named Solution */
        int n = int.Parse(Console.ReadLine());
        string Word1 = "";
        Dictionary<string, int> list = new Dictionary<string, int>();
        
        for(int i = 0; i <n; i++)
        {
            Word1 = Console.ReadLine();
            string[] array = Word1.Split(null);
            list.Add(array[0], int.Parse(array[1]));
        }
        for(int i = 0; i<n; i++)
        {
            Word1 = Console.ReadLine();
            if(list.ContainsKey(Word1))
            {
                var keyValuePair = list.Single(x => x.Key == Word1);
                Console.WriteLine(Word1 + "=" + keyValuePair.Value);
            }
            else
            {
                Console.WriteLine("Not found");
            }
        }
        
        
    }
}

What I have tried:

This solution is definitely more efficient than my first one where I was using foreach loops... but I dont know of anything in this case that would be faster than LINQ

Posted 6-Feb-17 5:21am

Member 11169882

Updated 6-Feb-17 15:26pm

Add a Solution

Comments

[no name] 6-Feb-17 11:22am

LINQ != faster

Patrice T 6-Feb-17 13:06pm

"the coding challenge by HackerRank" is not obvious to everyone as not everyone is registered on this site.
Can you tell us what is the requirement?

Member 11169882 6-Feb-17 13:23pm

Basically, you have to write code based on certain inputs and expected outputs. The problem is that some of the test cases are huge with 100's of inputs. Therefore even though some of the test cases pass, not all can because in the larger test cases the timeout occurs

Patrice T 6-Feb-17 14:24pm

Can you copy exact requirement.
I am sure details count.

6 solutions

Solution 5

When it comes to speed optimization, the tool of choice is the profiler.
the profiler is there to tell you how much time you spend in each part of your code and to detect bottlenecks.
Profiling (computer programming) - Wikipedia[^]

Posted 6-Feb-17 12:05pm

Patrice T

Solution 6

A line like

C#

list.Single(x => x.Key == Word1);

is inefficient because Linq-to-object has no way to understand that it is searching a dictionary with its key. So it will essentially enumerate all items in the dictionary until it find a match.

On the other hand, TryGetValue is specifically written to do an efficient search on the dictionary.

For such operations, container methods would be faster.

Linq-to-Entities or Linq-to-SQL are different as SQL code is generated by analysing the expression themselves.

Also using `Single` imply that you would check all elements to ensure that a single one exists. On average using `First` would be twice as fast and since a dictionary cannot contains duplicate keys anyway, it would give the same result.

Posted 6-Feb-17 15:26pm

Philippe Mori

Comments

Member 11169882 6-Feb-17 22:19pm

Yes, I realised that after I saw solution 4. And thank you for your helpful insight, tips like this really do help me become a better developer. At the time I was trying different things and TryGetValue wasn't liked by the compiler for some reason (when I was trying it) i was probably using it incorrectly. I am still not the best at using linq but it is very very useful in .NET from my uses of it so far. Again your input is greatly appreciated, have a great day!

Solution 2

Why don't you get a list of words from the user, store them in a list, and THEN perform your loops using the words from the list.

Posted 6-Feb-17 7:26am

#realJSOP

Comments

Member 11169882 6-Feb-17 14:24pm

See solution 4, thank you for your answer, really appreciate your time!

Solution 3

Maybe a more pure LINQ implementation to get away from the for loops and move to iterations?

Avoid the Dictionary<string, int> boxing and keep the LINQ array as a collection of anonymous objects.

Also, use SingeOrDefault and check if the value is null. You can combine this in your message string operation and (hopefully) put that all on the same cycle.

Let me know if this improves the efficiency at all:

C#

class Solution
{
	static void Main(String[] args)
	{
		/* Enter your code here. Read input from STDIN. Print output to STDOUT. Your class should be named Solution */
		int n = int.Parse(Console.ReadLine());
		int[] Range = Enumerable.Range(0, n).ToArray();
		var list = Range.Select(e =>
		{
			string[] array = Console.ReadLine().Split(null);
			return new { key = array[0], val = int.Parse(array[1]) };
		});

		foreach (var r in Range)
		{
			var found = list.SingleOrDefault(l => l.key == Console.ReadLine());
			string msg = found == null ? "Not Found" : $"{found.key}={found.val}";
			Console.WriteLine(msg);
		}
	}
}

Posted 6-Feb-17 7:32am

AFell2

Comments

Member 11169882 6-Feb-17 14:21pm

Although your solution didnt work for me, I want to thank you for your time and help :) I learned something from your implementation as well! See solution 4 for what worked for me.
Thanks

Add a Solution

This content, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)

User 7407470 · Accepted Answer · 2017-02-06T07:48:00

Solution 4

You are looking up 'Word1' in an inefficient way, try this ('the standard way'):

C#

for(int i = 0; i < n; i++)
{
    int val;

    Word1 = Console.ReadLine();
    if (list.TryGetValue(Word1, out val))
    {
        Console.WriteLine(Word1 + " = " + val);
    }
    else
    {
        Console.WriteLine(Word1 + " not found");
    }
}

or in short:

C#

for(int i = 0; i < n; i++)
{
    int val;

    Word1 = Console.ReadLine();
    Console.WriteLine(Word1 + (list.TryGetValue(Word1, out val) ? " = " + val : " not found"));
}

Posted 6-Feb-17 7:48am

User 7407470

Updated 6-Feb-17 7:52am

v2

Comments

Member 11169882 6-Feb-17 14:19pm

Thank you!! TryGetValue is definitely more efficient.
Since I have to output in a specific way to pass the test cases, this ended up working for me:

for(int i = 0; i < n; i++)
{
int val;
Word1 = Console.ReadLine();
if(list.TryGetValue(Word1, out val))
{
Console.WriteLine(Word1 + "=" + val);
}
else
{
Console.WriteLine("Not found");
}
}

Member 11169882 6-Feb-17 14:23pm

I believe the lookup would work better the way i did it if i wasn't inside of a loop, however since I am looping for each item, a tryget is much more efficient. The issue was that earlier I was using a keyValuePair, and not a dictionary and the compiler wasn't accepting "TryGetValue" but now it was working as i made a few tweaks using your solution.
Thanks again!

[no name] 6-Feb-17 14:27pm

Very nice! Thanks for your reply.
Kind regards, Peter

OriginalGriff · Accepted Answer · 2017-02-06T05:33:00

Solution 1

As NotPoliticallyCorrect says, Linq is not automatically faster - it can appear faster because it normally defers execution until the results are needed, but it isn't necessarily faster at all.

Instead of trying to get us to improve it, start doing basic optimisations: use the Stopwatch class to monitor your code and find out where it is spending the most time. You can then work on improving that specific segment of the code.
And you need to know where it is timing out, and after how long: it may be that the data set you are testing against is causing it to freeze waiting for input that never comes and that's why it times out. If for example there are n-1 lines in the second loop, it will wait for the final line until it is killed.

Posted 6-Feb-17 5:33am

OriginalGriff

Comments

Member 11169882 6-Feb-17 11:56am

I didnt necessarily ask anyone to improve or rewrite the code, I had only asked in this case where could the inefficiency be in the way I had written it but I see what you mean. I value the time of the community and therefore didn't ask for much.

Also, for the second for loop I tried using a while loop as follows
while((Word1 = Console.ReadLine())!= null)
{
.....
}
I am still getting the same result (TimeOut occurs). For now I've moved onto the next challenge. If i don't get any other solutions within the next day I will accept your solution

[no name] 6-Feb-17 14:15pm

Just guessing, but my primary suspect is this line:

list.ContainsKey(Word1)

If the list is large and the search algorithm does not fit well, searching may take a lot of needless time. Sorting the list after reading it may help a little. Try both ascending and descending order.

Member 11169882 6-Feb-17 14:49pm

see Solution 4, thanks for your reply!

C# code is too inefficient, causing timeout on hackerrank

6 solutions

Solution 4

Solution 5

Solution 6

Solution 1

Solution 2

Solution 3

Add your solution here

Preview 0

C# code is too inefficient, causing timeout on hackerrank

6 solutions

Solution 4

Solution 5

Solution 6

Solution 1

Solution 2

Solution 3

Add your solution here

Preview 0

Existing Members

...or Join us