Different program outputs when different capacity arguments are passed to List constructor, C#

Question

I'm implementing a slightly fancier version of counting sort in C#. The "slightly fancier" part is that I replace some elements in the sorted output with "-" rather than the original value. Here is a sample input/ output pair (the range of possible integer values are between 0 and 99):

IN

20
0 ab
6 cd
0 ef
6 gh
4 ij
0 ab
6 cd
0 ef
6 gh
0 ij
4 that
3 be
0 to
1 be
5 question
1 or
2 not
4 is
2 to
4 the

OUT

- - - - - to be or not to be - that is the question - - - -

And here is my implementation:

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

    static void Main(String[] args) 
    {
        int n = Convert.ToInt32(Console.ReadLine());
        List<List<string>> rsltLists = new List<List<string>>(100);
        for(int i=0; i<n; i++)
        {
            rsltLists.Add(new List<String>()); // PROBLEM IS HERE
        }

        for(int a0 = 0; a0 < n; a0++)
        {
            string[] tokens_x = Console.ReadLine().Split(' ');
            int x = Convert.ToInt32(tokens_x[0]);
            string s = tokens_x[1];
            if(a0 < n/2)
            {
                // Replace string with '-'
                rsltLists[x].Add("-");
            } 
            else 
            {               
                rsltLists[x].Add(s);
            }
        }

        foreach(List<string> rsltList in rsltLists)
        {
            foreach(string rslt in rsltList)
            {
                Console.Write(rslt + " ");
            }
        }
    }
}

I'm submitting my code as the solution to a problem on Hackerrank. The problem is that for the 5th test case, my solution times out (the test case contains an enormous number of lines so I'm not including it here). To speed my solution up, I replaced the //PROBLEM IS HERE line with rsltLists.Add(new List<String>(100)). This causes the 5th test case to fail rather than time out (test cases 1-4 still passed). When I replaced the problem line with rsltLists.Add(new List<String>(10000)) the 5th test case and several other test cases failed (though not all of the test cases failed). Why would changing the amount of space I reserve for each List<String> cause this inconsistent behavior? I would expected the fifth test case to fail (maybe), but I wouldn't have expected test cases that were passing previously to start failing.

Answer 1

Why are you creating n rsltLists? That is not the requirement. There are 100 possible values and array is better for that. You should NOT be using n here. x is 100.

for(int i=0; i<n; i++)  // no, problem is here
{
    rsltLists.Add(new List<String>()); // PROBLEM IS HERE
}

This should be pretty fast

public static string HackerSort()
{
    List<string> input = new List<string>() {"20"
                                            , "0 ab"
                                            , "6 cd"
                                            , "0 ef"
                                            , "6 gh"
                                            , "4 ij"
                                            , "0 ab"
                                            , "6 cd"
                                            , "0 ef"
                                            , "6 gh"
                                            , "0 ij"
                                            , "4 that"
                                            , "3 be"
                                            , "0 to"
                                            , "1 be"
                                            , "5 question"
                                            , "1 or"
                                            , "2 not"
                                            , "4 is"
                                            , "2 to"
                                            , "4 the" };
    List<string>[] wl = new List<string>[100];
    int n = int.Parse(input[0]);
    int half = n/2;
    char split = ' ';
    for (int i = 0; i < n; i++)
    {
        string s = input[i + 1];
        string[] ss = s.Split(split);
        //Debug.WriteLine(ss[0]);
        int row = int.Parse(ss[0]);
        if(wl[row] == null)
        {
            wl[row] = new List<string>((n / 100) + 1);
        }
        wl[row].Add(i  < half ? "-" : ss[1]);            
    }
    StringBuilder sb = new StringBuilder();
    foreach(List<string> ls in wl.Where(x => x != null))
    {
        sb.Append(string.Join(" ", ls) + ' ');
    }
    Debug.WriteLine(sb.ToString().TrimEnd());
    return sb.ToString().TrimEnd();
}

Answer 2

One way to solve the memory-hogging / long processing times would be to store the input in a SortedDictionary<int, List<string>> instead. The Key would be the integer portion of the input, and the Value would be a List<string> containing the other part of the input (one item per input that matches the key).

Then, when we have the dictionary populated, we can just output each List<string> of data in order (the SortedDictionary will already be sorted by Key).

In this way, we're only creating as many lists as we actually need, and each list is only as long as it needs to be (both of which I believe were causes for the errors in your original code, but I don't know where to find the actual test case code to verify).

private static void Main()
{
    var length = Convert.ToInt32(Console.ReadLine());
    var halfway = length / 2;
    var items = new SortedDictionary<int, List<string>>();

    for (int inputLine = 0; inputLine < length; inputLine++)
    {
        var input = Console.ReadLine().Split();
        var sortIndex = Convert.ToInt32(input[0]);
        var value = inputLine < halfway ? "-" : input[1];

        if (items.ContainsKey(sortIndex)
        {
            items[sortIndex].Add(value);
        }
        else
        {
            items.Add(sortIndex, new List<string> {value});
        }
    }

    Console.WriteLine(string.Join(" ", items.SelectMany(i => i.Value)));

    // Not submitted to website, but for local testing:
    Console.Write("\n\nPress any key to exit...");
    Console.ReadKey();
}

Output

Answer 3

The "inner" List will always have exactly two elements, one of which you want to treat as a number rather than a string. Better to use a small class or even a tuple here, rather than nested lists.

I'm at work with only VS2015 with no tuple support, so this code is unchecked and likely has a mistake or two:

static void Main(String[] args) 
{
    int n = int.Parse(Console.ReadLine());
    var data = new List<(int, string)>(n);

    for(int a0 = 0; a0 < n; a0++)
    {
        var tokens = Console.ReadLine().Split(' ');
        int x = int.Parse(tokens[0]);
        if(a0 < n/2) tokens[1] = "-";

       data.Add( (val: x, str: tokens[1]) )
    }

    foreach(var item in data.OrderBy(i => i.val))
    {
        Console.Write(item.str + " ");
    }
}

Answer 4

Couple thoughts on this:

• You're creating a list for each option... but many aren't used. How about only instantiating the lists that you'll actually use?
• Compounded with the one above, you're creating 100 lists, each with a capacity of 100... that's a lot of memory to set aside that you won't be using

One solution:

using System;
using System.Collections.Generic;
using System.IO;
using System.Linq;
using System.Text;
class Solution 
{
    static void Main(String[] args) 
    {
        int n = Convert.ToInt32(Console.ReadLine());
        int threshold = n / 2;
        List<string>[] stringMap = new List<string>[100];
        for(int a0 = 0; a0 < n; a0++){
            string[] tokens_x = Console.ReadLine().Split(' ');
            int x = Convert.ToInt32(tokens_x[0]);
            if(stringMap[x] == null)
            {
                stringMap[x] = new List<string>();
            }
            stringMap[x].Add((a0 >= threshold ? tokens_x[1] : "-"));
        }

        List<string> output = new List<string>();
        for(int i = 0; i < stringMap.Length; i++)
        {
            if(stringMap[i] == null)
            {
                continue;
            }

            output.AddRange(stringMap[i]);
        }

        Console.WriteLine(string.Join(" ", output));
    }
}