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
  • 2
    \$\begingroup\$ Are you after clarity or performance? \$\endgroup\$
    – Joey
    Commented Mar 16, 2015 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\$ Commented Mar 17, 2015 at 9:34

5 Answers 5

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. ;)

\$\endgroup\$
5
  • \$\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
    Commented Mar 15, 2015 at 22:09
  • \$\begingroup\$ Instead of an int[31], the 32 bits of an Int32 would suffice. \$\endgroup\$ Commented Mar 16, 2015 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\$ Commented Mar 16, 2015 at 21:57
  • \$\begingroup\$ You just need two bits for each possibility instead of 1. \$\endgroup\$
    – Snowbody
    Commented Mar 17, 2015 at 16:28
  • \$\begingroup\$ @Snowbody and there goes using the 32 bits of an Int32? \$\endgroup\$
    – NetMage
    Commented Jul 5, 2018 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)
\$\endgroup\$
1
  • \$\begingroup\$ Really neat implementation using just linq. Thanks! \$\endgroup\$ Commented Mar 17, 2015 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!

\$\endgroup\$
3
  • 1
    \$\begingroup\$ Fair point. Do you think it is a good solution to the problem? \$\endgroup\$ Commented Mar 15, 2015 at 19:29
  • \$\begingroup\$ I'm not a C# expert. Can't say. \$\endgroup\$
    – nhgrif
    Commented Mar 15, 2015 at 20:13
  • \$\begingroup\$ Save the bits - don't put in uneccessary braces! \$\endgroup\$
    – NetMage
    Commented Jul 5, 2018 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);
    }
}
\$\endgroup\$
2
  • \$\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\$ Commented Mar 18, 2015 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
    Commented Mar 18, 2015 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);
            }
        }
    }
}
\$\endgroup\$
1
  • \$\begingroup\$ Hello, downvoting faery. How could I improve my answer? \$\endgroup\$
    – ANeves
    Commented Oct 23, 2019 at 13:13

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.