12
\$\begingroup\$

Problem statement:

Given an array of unknown size and containing only integers between 0 to 30 (inclusive), write an algorithm to find which numbers are duplicated, if any

My solution in C#:

public IEnumerable<int> Duplicates(int[] sequence)
{
    var targets = new Dictionary<int, int>();
    foreach (var n in sequence)
        if (targets.ContainsKey(n))
            targets[n]++;
        else
            targets.Add(n, 1);
    return targets.Where(kv => kv.Value > 1).Select(kv => kv.Key);   
}

I would welcome any potential flaws or improvements.

\$\endgroup\$
  • 2
    \$\begingroup\$ Are you after clarity or performance? \$\endgroup\$ – Joey Mar 16 '15 at 17:11
  • \$\begingroup\$ @Joey, I'm looking for performance. Clarity would be an added bonus. This is the kind of complexity I think is expected in an interview coding on paper/whiteboard scenario. But I am curious as to how much more efficient it can be (as a function of the input sequence). \$\endgroup\$ – chosenbreed37 Mar 17 '15 at 9:34
12
\$\begingroup\$

I would do something along these lines. I'm not that sharp on C# but anyway...

The main idea here is to use an int array instead of a Dictionary. This uses the fact that all values are between 0 and 30 (inclusive)

public List<int> Duplicates(int[] sequence)
{
    int[] countArr = new int[31];
    for (int i in sequence)
    {
        countArr[i]++;
    }

    List<int> resultList = new List<int>();

    for (int i in countArr)
    {
        if (countArr[i] > 1)
        {
            resultList.Add(i);
        }
    }

    return resultList;
}

It's dangerously close to what you did, except i'm not using a dictionary or any other fancy C# features. ;)

|improve this answer|||||
\$\endgroup\$
  • \$\begingroup\$ Nice answer! Two small fixes: first loop should be foreach instead of for, second loop should be for (var i = 0; i < countArr.Length; i++). \$\endgroup\$ – mjolka Mar 15 '15 at 22:09
  • \$\begingroup\$ Instead of an int[31], the 32 bits of an Int32 would suffice. \$\endgroup\$ – 200_success Mar 16 '15 at 11:41
  • 2
    \$\begingroup\$ @200_success How do you determine if a symbol is seen once, more than once, or never seen with only 1 bit of information per symbol? \$\endgroup\$ – twohundredping Mar 16 '15 at 21:57
  • \$\begingroup\$ You just need two bits for each possibility instead of 1. \$\endgroup\$ – Snowbody Mar 17 '15 at 16:28
  • \$\begingroup\$ @Snowbody and there goes using the 32 bits of an Int32? \$\endgroup\$ – NetMage Jul 5 '18 at 18:58
9
\$\begingroup\$

Let's ignore the range constraint for a minute.

Seeing as you're already using Linq you could take it a step further. Use IEnumerable<int> instead of int[] and make it an extension method:

public static class EnumerableExtensions
{
    public static IEnumerable<int> Duplicates(this IEnumerable<int> sequence)
    {
        var targets = new Dictionary<int, int>();
        foreach (var n in sequence)
        {
            if (targets.ContainsKey(n))
            {
                targets[n]++;
            }
            else
            {
                targets.Add(n, 1);
            }
        }
        return targets.Where(kv => kv.Value > 1).Select(kv => kv.Key);
    }
}

Now the argument name matches the type even better. Then drop all the dictionary stuff and use Linq instead:

public static class EnumerableExtensions
{
    public static IEnumerable<int> Duplicates(this IEnumerable<int> sequence)
    {
        return sequence.GroupBy(value => value)
                       .Where(group => group.Count() > 1)
                       .Select(group => group.Key);
    }
}

Using it:

var values = new[] {1, 2, 3, 4, 5, 6, 7, 8, 9, 1, 5, 6};
var duplicates = values.Duplicates(); //1, 5, 6

Then make it generic and add a bit more utility:

public static class EnumerableExtensions
{
    public static IEnumerable<TSource> Duplicates<TSource>(this IEnumerable<TSource> sequence)
    {
        return sequence.GroupBy(value => value)
                       .Where(group => group.Count() > 1)
                       .Select(group => group.Key);
    }

    public static IEnumerable<TKey> DuplicatesBy<TSource, TKey>(this IEnumerable<TSource> sequence, Func<TSource, TKey> keySelector)
    {
        return sequence.GroupBy(value => keySelector(value))
                       .Where(group => group.Count() > 1)
                       .Select(group => group.Key);
    }

    public static IEnumerable<TResult> DuplicatesBy<TSource, TKey, TResult>(this IEnumerable<TSource> sequence, Func<TSource, TKey> keySelector, Func<TSource, TResult> resultSelector)
    {
        return sequence.ToLookup(value => keySelector(value), value => resultSelector(value))
                       .Where(group => group.Count() > 1)
                       .SelectMany(group => group);
    }
}

And using it:

var values = new[] {Tuple.Create(1,1), 
                    Tuple.Create(1,1), 
                    Tuple.Create(4,20), 
                    Tuple.Create(10,20), 
                    Tuple.Create(7,11)};
var duplicates = values.Duplicates(); //(1,1)
var duplicateItem2s = values.DuplicatesBy(t => t.Item2); //1, 20
var duplicatesOnItem2 = values.DuplicatesBy(t => t.Item2, t => t);//(1,1), (1,1), (4,20), (10,20)
|improve this answer|||||
\$\endgroup\$
  • \$\begingroup\$ Really neat implementation using just linq. Thanks! \$\endgroup\$ – chosenbreed37 Mar 17 '15 at 9:39
7
\$\begingroup\$

BRACKETS! WHERE ARE YOUR BRACKETS!?!?

Brackets save lives. Let's not omit them!

foreach (var n in sequence)
{
    if (targets.ContainsKey(n))
    {
        ++targets[n];
    }
    else
    {
        targets.Add(n, 1);
    }
}

Omitting brackets doesn't really do a whole lot for us. Putting them in can make the code more readable and will definitely prevent some possible bugs in the future when we go to alter the code. It's just easier to see what's going on with the brackets there. And it's a form of self-documentation--yes this code is doing exactly what we wrote it to do!

|improve this answer|||||
\$\endgroup\$
  • 1
    \$\begingroup\$ Fair point. Do you think it is a good solution to the problem? \$\endgroup\$ – chosenbreed37 Mar 15 '15 at 19:29
  • \$\begingroup\$ I'm not a C# expert. Can't say. \$\endgroup\$ – nhgrif Mar 15 '15 at 20:13
  • \$\begingroup\$ Save the bits - don't put in uneccessary braces! \$\endgroup\$ – NetMage Jul 5 '18 at 18:59
1
\$\begingroup\$

Not efficient but neat:

return sequence.Where(n => sequence.Count(n2 => n2 == n) > 1).Distinct();

If performance is what you are after I would go for an approach like André's but using an int with bitwise operators and shifts.

Edit

If performance is all you are interested in, then something like this would be quick:

public IEnumerable<int> Duplicates(IEnumerable<int> sequence)
{
    var seenInts = 0;
    var dupeInts = 0;
    var duplicates = new List<int>(31);
    foreach (var n in sequence)
    {
        // Get the bit mask for this int, e.g. 0 is 0001, 1 is 0010, 2 is 0100...
        var thisBit = 1<<n;

        // If we've seen this int precisely once before...
        if ((seenInts & thisBit) > 0 && (dupeInts & thisBit) == 0)
        {   
            // ...add it to our output...       
            duplicates.Add(n);

            // ...and remember that we've seen it twice
            dupeInts |= thisBit;
        }       

        // Record that we've seen this int
        seenInts |= thisBit;
    }   

    return duplicates;
}

...or if you want to guarantee the returned ints are in ascending order drop the if section (keeping dupeInts |= thisBit) and do this at the end:

for (int i = 1, j = 0; j<31; i = i << 1, j++)
{
    if ((i & dupeInts) > 0)
    {
        duplicates.Add(j);
    }
}
|improve this answer|||||
\$\endgroup\$
  • \$\begingroup\$ Okay. Neat implementation. Heuristically (or hypothetically) speaking would you be able to quantify the improvement in performance? Given that most of the solutions presented here will complete in linear time are we then splitting hairs with this kind of optimisation? \$\endgroup\$ – chosenbreed37 Mar 18 '15 at 10:52
  • \$\begingroup\$ I think a test is in order, I don't have time now but when I do I'll try to profile a few of the answers for you. You are right that it does nothing for the complexity of the algorithm, it just reduces the multiplier on n \$\endgroup\$ – Joey Mar 18 '15 at 13:18
0
\$\begingroup\$

Suggestions

  • Braces!!
  • Instead of incrementing a Dictionary, you could keep a HashSet of duplicates;
  • If you feel it could be useful for sequences of other data types, you could make the method generic.

Proposal:

public static class EnumerableHelpers
{
    public static IEnumerable<T> FindDuplicates<T>(this IEnumerable<T> sequence)
    {
        return DuplicatesIn(sequence);
    }
    public static IEnumerable<T> DuplicatesIn<T>(IEnumerable<T> sequence)
    {
        var duplicates = new HashSet<T>();
        var uniques = new HashSet<T>();
        foreach (var number in sequence)
        {
            if (duplicates.Contains(number))
            {
                // Repeated duplicate.
                continue;
            }
            if (uniques.Contains(number))
            {
                duplicates.Add(number);
                yield return number;
            }
            else
            {
                uniques.Add(number);
            }
        }
    }
}
|improve this answer|||||
\$\endgroup\$
  • \$\begingroup\$ Hello, downvoting faery. How could I improve my answer? \$\endgroup\$ – ANeves Oct 23 '19 at 13:13

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.