Interview Questions

  • View all interview questions
  • blank
  • Find all duplicates in an array in linear time (v1)
    This is a common interview question where you need to write a program to find all duplicates in an array where the numbers in the array are in the range of 0 to n-1 where n is the size of the array. For example: [1, 2, 3, 3] is okay but [1, 2, 6, 3] is not. In this version of the challenge there can be multiple duplicate numbers as well. The algorithm below is commented to explain what each piece of code does, but the general algorithm is: (1) Loop through the array (2) For each element, find array[absolute(array[i])] in the array and set its value to negative if positive (3) If in step 2 you encounter a negative number, then it means the element at index i in the array is a duplicate

    An example




    You need to be a premium member to see the rest of this question and code.

    Become a Premium Member

    With our large collection of challengs, tutorials, and solutions, we make it easy for you to become a better coder, prepare for interviews, and learn new skills from more experienced coders.

    “I love Coderbyte challenges! What an awesome way to work on your javascript and algorithm skills.“ ― Rob Rosario
    • 200+ Coding Challenges
    • Mock Interview Questions
    • 500,000+ Code Solutions
    • Algorithm Tutorials
    • Interview Prep Courses
    mrdaniel published this on 11/11/15 | duplicate, array, Amazon, Facebook, Microsoft
    Comments
  • +
  • 2
  • -
  • Since JavaScript has the concept of -0, the code can be significanlty simplified. The test for -0 is 1/x > 0. Evaluates to false if x is -0 and true if normal +0.
      var abs = (x) => Math.abs(arr[x]);
    
      for (var i = 0; i < arr.length; i++) {
    		
        // get element in array
        var el = arr[abs(i)];
        
        // element in array is positive so make it negative; handle -0
        if (el >= 0 && 1/el > 0)
        	arr[abs(i)] = -arr[abs(i)];
        
        // element is negative so it is a duplicate
        else
        	dups.push(Math.abs(arr[i]));
      }
  • +
  • 1
  • -
  • @numbergames Don't see how to edit, but need to update the test in my code -- don't need two tests, so
    if (el >= 0 && 1/el > 0)
    should be:
    if (1/el > 0)
  • +
  • 1
  • -
  • @karn09 This specific solution solves the challenges of finding duplicates in an array with numbers *only* in the range 0 to n-1 where n is the size of the array. So for [1,2,1,3,6, 5] it wouldn't work because the size of the array is 6 so the range must be 0 to 5, and there is a 6 in the array. Same goes for the second example. The v2 algorithm gives a solution for the more general challenge of finding duplicates in an array of any range of numbers.
  • +
  • 0
  • -
  • Sorry I just realized this was building up to using a hash table.
  • +
  • 0
  • -
  • I did this using a hash table in Python - seems to still run in O(n) time (and with less array manipulation), and works for any numbers:
    def get_dups(array):
        ht = {}
        dups = []
        for x in array:
            if x in ht:
                dups.append(x)
            else:
                ht[x] = x
        return list(set(dups))
    
  • +
  • 0
  • -
  • Very good point. I will need to be more careful when reading over the cases. Thank you.
  • +
  • 0
  • -
  • There seems to be a problem with this solution. In certain cases it returns a duplicate multiple times and in others will return non-duplicated numbers. duplicates([1,2,1,3,6, 5]); => [1,0] duplicates([0,2,1,3,6, 6]); => [0,0] I think part of the issue is with setting the special case 0 to be equal to the length where arrays contain duplicates that are equal to the length.
    Login to submit a comment