Microsoft Interview Question: Determine if an array from 1.... | Glassdoor

Interview Question

Software Development Engineer Intern Interview Seattle, WA

Determine if an array from 1..n has a duplicate in constant

  time and space.
Answer

Interview Answer

12 Answers

4

Correct answer is to place each value in the array in its corresponding index (i.e. if array[x] = 3, put 3 into array[3]). If an index already contains its corresponding value, there's a duplicate.

Interview Candidate on Aug 13, 2013
7

^^ Sorry, that's linear time *and* at best linear space, you fail.

Interview Candidate's Teacher on Aug 17, 2013
3

What are the properties of an array that affect time complexity? Usually we're talking about the size of the array, N, such that linear time operations, O(N), are those that perform an operation on each of the elements in the array. However, an important thing to consider is that you can evaluate N (the size of the array) itself in constant time.

The only way this can be done in constant time is if the input satisfies the precondition that "1..n" means there are no *missing* values in that range. In other words, such an array from "1..5" must contain at least one instance of the numbers 1, 2, 3, 4, and 5. With that precondition, you know that the length of the array will be 5 if no duplicates and greater than 5 if it does contain duplicates.

KR Fan on Aug 17, 2013
5

SUM(array) - (N(N+1)/2) = missing number.

Facebook Intern on Aug 23, 2013
0

@Facebook Intern: That wont help .. In case there are 2 duplicates this can be broken. {1, 1, 4, 4}

Someone on Sep 7, 2013
0

I attach pseudo code here:

FindDuplicate(A)
    i = A.length
    j = 1
    count = 0
    while j < i
         if A[--j] - j == 0
              j++
         else count++
return count

count holds the number of duplicated items

william on Sep 25, 2013
0

This cannot be done in linear time unless the data-structure used to hold the integers has a property that immediately flags duplicates upon insertion. For e.g. like in a Dictionary/HashMap.

Keith on Oct 12, 2013

This post has been removed.
Please see our Community Guidelines or Terms of Service for more information.

5

If an array has elements from 1 to n the size of the array will be n, thus if the size of the array is greater than n, there must exist a duplicate.

Anonymous on Nov 7, 2015
3

I think they are just asking to determine if there is any duplicate number ir not. Its not mentioned to find out which number it is. So that we can find out by using sum of n numbers

Saina on Jan 15, 2016
0

I think they are just asking to determine if there is any duplicate number ir not. Its not mentioned to find out which number it is. So that we can find out by using sum of n numbers

Saina on Jan 15, 2016
0

They asked for constant time. So checking sum will not work.
For zero indexed arrays,

Check if arr[len(arr)-1] == len(arr) - 1.

Anonymous on May 9, 2018

Add Answers or Comments

To comment on this, Sign In or Sign Up.