Find first non-repetitive char in a string I just had an interview for the C#.NET developer position and I was asked to find the first non repetitive char in a given string without using any library functions but just the basic constructs of the language such as fors and ifs.

I presented this solution considering the quick time constraint. I request evaluation of the solution of how truly it serves the question.

public static char findFirstNonRepetitiveChar(string input)
{
    char c = '0';

    for (int i = 0; i &lt; input.Length; i++)
    {
        bool isdistinct = true;
        for (int j = 0; j &lt; input.Length; j++)
        {
            if (input[i] == input[j] &amp;&amp; i!=j)
            {
                isdistinct = false;
                break;
            }
        }
        if (isdistinct)
        {
            c = input[i];
            break;
        }
    }
    return c;
}
Some of what constitutes a "good" solution here depends on how much value you place on (for example) CPU time vs. memory usage. Another point to take into account is what size of strings you expect to process, and whether you expect them to be mostly unique, mostly repeats, basically random, or exactly what.

As it stands, this uses almost no extra space, but uses \$O(N^2)\$ CPU time. If you expect the input strings to be long, this could be quite prohibitive.

If you didn't mind using extra space, you could (for example) walk through the string, and use a hash table to count the number of occurrences of each character. Then walk through the hash table, and find the characters in the string that only occur once. Mark those, then do a final walk through the string to find which occurred first. This requires two walks through the string, and one walk through a hash table the same size as the number of unique elements in the string, so it's basically 3N operations, or \$O(N)\$ (well, we expect linear complexity, anyway--in the true worst case, it's still \$O(N^2)\$). For a long string (say, a few million or even a few thousand characters) that could be a huge win (but at the expense of approximately doubling the memory usage. If you're concerned with worst case performance more than average, you might want to use a balanced tree instead of a hash table, so insertions are \$O(N log N)\$ (both expected, and worst case).

Which one is preferable will (mostly) come down to questions like those in the first paragraph. For typical short strings (less than 20 characters long is very common), either is likely to be fast enough that a more efficient algorithm won't make much real difference. On the other hand, if the input might be megabytes instead, the faster algorithm is likely to pay off--and even if it's several megabytes, allocating an extra several megabytes on a modern desktop (or server) machine rarely matters a whole lot.