MGL MGL - 22 days ago 8
C# Question

How to make the most effective search in array

I had a question in a job interview: find first unique name in array.

public static void Main(string[] args)
{
Console.WriteLine(FirstUniqueName(new string[] { "Abbi", "Adeline", "Abbi", "Adalia" }));
Console.Read();
}


In this example function should return Adeline. I wrote function:

public static string FirstUniqueName(string[] names)
{
return names.FirstOrDefault(f => names.Count(c => c == f) == 1);
}


That calculate correct values, but System threw validation error "the execution time is too long". I believe that it happened because it wasn't the most effective way and it should be only with one loop.
I glanced over different ways of implementation of search on stackoverflow, but all these suggestions were similar to mine (2 or more loops).
Does someone know what should be the answer?

Answer

You could always group them.

public static string FirstUniqueName(string[] names)
{
    var group = names.GroupBy(n => n)
                     .FirstOrDefault(g => g.Count() == 1);

    return group == null ? "" : group.Key;
}

This would be faster than the solution you presented in the question because you're iterating back through the array for each and every item in the array. That will be a severe performance loss. Also, this is more readable than yours as the lambdas are more concise.

I don't know exactly how the .NET team implemented .GroupBy(), however those engineers worked long and hard to optimize the crap out of it. If they do find a better solution, they test and would replace the internal workings on the next version.

UPDATE

MetroSmurf had suggested the alternative lambda:

.FirstOrDefault(g => g.Skip(1).Any() == false)

Under some circumstances, this would be marginally faster. However, StriplingWarrior commented that Group is defined as an IList. If you check the source code for IEnumerable<T>.Count(), you will see that the method casts the enumerable to an ICollection<T>.

If the casting succeeds (which a Group will), then it will call that .Count property, which does not need to iterate through the entire collection, making that call faster than doing the .Skip().