Microsoft Interview Question
Software Engineer / DevelopersCountry: United States
# An algorithm for solving the following (classic) hard interview problem:
#
# "You are given an array of integers of length n, where each element ranges
# from 0 to n - 2, inclusive. Prove that at least one duplicate element must
# exist, and give an O(n)-time, O(1)-space algorithm for finding some
# duplicated element. You must not modify the array elements during this
# process."
#
# This problem (reportedly) took CS legend Don Knuth twenty-four hours to solve
# and I have only met one person (Keith Amling) who could solve it in less time
# than this.
#
# The first part of this problem - proving that at least one duplicate element
# must exist - is a straightforward application of the pigeonhole principle.
# If the values range from 0 to n - 2, inclusive, then there are only n - 1
# different values. If we have an array of n elements, one must necessarily be
# duplicated.
#
# The second part of this problem - finding the duplicated element subject to
# the given constraints - is much harder. To solve this, we're going to need a
# series of nonobvious insights that transform the problem into an instance of
# something entirely different.
#
# The main trick we need to use to solve this problem is to notice that because
# we have an array of n elements ranging from 0 to n - 2, we can think of the
# array as defining a function f from the set {0, 1, ..., n - 1} onto itself.
# This function is defined by f(i) = A[i]. Given this setup, a duplicated
# value corresponds to a pair of indices i != j such that f(i) = f(j). Our
# challenge, therefore, is to find this pair (i, j). Once we have it, we can
# easily find the duplicated value by just picking f(i) = A[i].
#
# But how are we to find this repeated value? It turns out that this is a
# well-studied problem in computer science called cycle detection. The general
# form of the problem is as follows. We are given a function f. Define the
# sequence x_i as
#
# x_0 = k (for some k)
# x_1 = f(x_0)
# x_2 = f(f(x_0))
# ...
# x_{n+1} = f(x_n)
#
# Assuming that f maps from a domain into itself, this function will have one
# of three forms. First, if the domain is infinite, then the sequence could be
# infinitely long and nonrepeating. For example, the function f(n) = n + 1 on
# the integers has this property - no number is ever duplicated. Second, the
# sequence could be a closed loop, which means that there is some i so that
# x_0 = x_i. In this case, the sequence cycles through some fixed set of
# values indefinitely. Finally, the sequence could be "rho-shaped." In this
# case, the sequence looks something like this:
#
# x_0 -> x_1 -> ... x_k -> x_{k+1} ... -> x_{k+j}
# ^ |
# | |
# +-----------------------+
#
# That is, the sequence begins with a chain of elements that enters a cycle,
# then cycles around indefinitely. We'll denote the first element of the cycle
# that is reached in the sequence the "entry" of the cycle.
#
# For our particular problem of finding a duplicated element in the array,
# consider the sequence formed by starting at position n - 1 and then
# repeatedly applying f. That is, we start at the last position in the array,
# then go to the indicated index, repeating this process. My claim is that
# this sequence is rho-shaped. To see this, note that it must contains a cycle
# because the array is finite and after visiting n elements, we necessarily
# must visit some element twice. This is true no matter where we start off in
# the array. Moreover, note that since the array elements range from 0 to
# n - 2 inclusive, there is no array index that contains n - 1 as a value.
# Consequently, when we leave index n - 1 after applying the function f one
# time, we can never get back there. This means that n - 1 can't be part of a
# cycle, but if we follow indices starting there we must eventually hit some
# other node twice. The concatenation of the chain starting at n - 1 with the
# cycle it hits must be rho-shaped.
#
# Moreover, think about the node we encounter that starts at the entry of the
# cycle. Since this node is at the entry of the cycle, there must be two
# inputs to the function f that both result in that index being generated. For
# this to be possible, it must be that there are indices i != j with
# f(i) = f(j), meaning that A[i] = A[j]. Thus the index of the entry of the
# cycle must be one of the values that is duplicated in the array.
#
# There is a famous algorithm due to Robert Floyd that, given a rho-shaped
# sequence, finds the entry point of the cycle in linear time and using only
# constant space. This algorithm is often referred to as the "tortoise and
# hare" algorithm, for reasons that will become clearer shortly.
#
# The idea behind the algorithm is to define two quantities. First, let c be
# the length of the chain that enters the cycle, and let l be the length of the
# cycle. Next, let l' be the smallest multiple of l that's larger than c.
# I claim that for any rho-shaped sequence l' defined above, that
#
# x_{l'} = x_{2l'}
#
# The proof is actually straightforward and very illustrative - it's one of my
# favorite proofs in computer science. The idea is that since l' is at least
# c, it must be contained in the cycle. Moreover, since l' is a multiple of
# the length of the loop, we can write it as ml for some constant m. If we
# start at position x_{l'}, which is inside the loop, then take l' more steps
# forward to get to x_{2l'}, then we will just walk around the loop m times,
# ending up right back where we started.
#
# One key trick of Floyd's algorithm is that even if we don't explicitly know l
# or c, we can still find the value l' in O(l') time. The idea is as follows.
# We begin by keeping track of two values "slow" and "fast," both starting at
# x_0. We then iteratively compute
#
# slow = f(slow)
# fast = f(f(fast))
#
# We repeat this process until we find that slow and fast are equal to one
# another. When this happens, we know that slow = x_j for some j, and
# fast = x_{2j} for that same j. Since x_j = x_{2j}, we know that j must be at
# least c, since it has to be contained in the cycle. Moreover, we know that j
# must be a multiple of l, since the fact that x_j = x_{2j} means that taking j
# steps while in the cycle ends up producing the same result. Finally, j must
# be the smallest multiple of l greater than c, since if there were a smaller
# multiple of l greater than c then we would have reached that multiple before
# we reached j. Consequently, we must have that j = l', meaning that we can
# find l' without knowing anything about the length or shape of the cycle!
#
# To complete the construction, we need to show how to use our information
# about l' to find the entry to the cycle (which is at position x_c). To do
# this, we start off one final variable, which we call "finder," at x_0. We
# then iteratively repeat the following:
#
# finder = f(finder)
# slow = f(slow)
#
# until finder = slow. We claim that (1) the two will eventually hit each
# other, and (2) they will hit each other at the entry to the cycle. To see
# this, we remark that since slow is at position x_{l'}, if we take c steps
# forward, then we have that slow will be at position x_{l' + c}. Since l' is
# a multiple of the loop length, this is equivalent to taking c steps forward,
# then walking around the loop some number of times back to where you started.
# In other words, x_{l' + c} = x_c. Moreover, consider the position of the
# finder variable after c steps. It starts at x_0, so after c steps it will be
# at position x_c. This proves both (1) and (2), since we've shown that the
# two must eventually hit each other, and when they do they hit at position x_c
# at the entry to the cycle.
#
# The beauty of this algorithm is that it uses only O(1) external memory to
# keep track of two different pointers - the slow pointer, and then the fast
# pointer (for the first half) and the finder pointer (for the second half).
# But on top of that, it runs in O(n) time. To see this, note that the time
# required for the slow pointer to hit the fast pointer is O(l'). Since l' is
# the smallest multiple of l greater than c, we have two cases to consider.
# First, if l > c, then this is l. Otherwise, if l < c, then we have that
# there must be some multiple of l between c and 2c. To see this, note that
# in the range c and 2c there are c different values, and since l < c at least
# one of them must be equal to 0 mod l. Finally, the time required to find the
# start of the cycle from this point is O(c). This gives a total runtime of at
# most O(c + max{l, 2c}). All of these values are at most n, so this algorithm
# runs in time O(n).
def findArrayDuplicate(array):
assert len(array) > 0
# The "tortoise and hare" step. We start at the end of the array and try
# to find an intersection point in the cycle.
slow = len(array) - 1
fast = len(array) - 1
# Keep advancing 'slow' by one step and 'fast' by two steps until they
# meet inside the loop.
while True:
slow = array[slow]
fast = array[array[fast]]
if slow == fast:
break
# Start up another pointer from the end of the array and march it forward
# until it hits the pointer inside the array.
finder = len(array) - 1
while True:
slow = array[slow]
finder = array[finder]
# If the two hit, the intersection index is the duplicate element.
if slow == finder:
return slow
Frank,
I am still not sure how slow and Fast Pointer will meet to find duplicate. This seems to be true in case of detecting cycle in Linked List but in case of array where even numbers are not sorted, this wont be able to find the duplicate until and unless you want to read all elements of a given array and draw a Linked List? Do you intend to draw a Linked List first?
input: array A[1..n]
The idea is to use the sum of inegers from 1 to n and the sum of squares of integers from 1 to n:
sum1 = sum from k = 1 to n (k) = n(n+1)2
sum2 = sum from k = 1 to n (k^2) = n(2n+1)(n+1)/6
Then we are calculating
s1 = sum1 - sum from k=1 to n (A[k])
s2 = sum2 - sum from k=1 to n (A[k]^2)
Now we have the system of equations:
a-b = s1
a^2-b^2 = s2
where a is missing value and b is duplicate.
The solution is:
a = (s2 + s1^2)/(2 s1)
b = (s2 - s1^2)/(2 s1)
The complexity of the algorith is O(n).
The code:
void f(int n)
{
int sum1 = n*(n+1)/2;
int sum2 = n*(2*n+1)*(n+1)/6;
for(int i=0; i<n; i++)
{
int next = readnext(); // get next value
sum1 -= next;
sum2 -= next*next;
}
int a = (sum2+sum1*sum1)/(2*sum1);
int b = (sum2-sum1*sum1)/(2*sum1);
printf("Missing: %d\nDuplicate: %d\n", a, b);
}
N could be as maximum as largest possible value of int data type.In such a case we cannot find sum1 and sum2.
To store number N we need log N bits. To store sum2 we need about 3 * log N bits. So memory complexity is O(log N).
If possible to allocate another array.
Initialize the additional array (call it B) with zeros.
Traverse the original array A, element by element, with index i=1..N
if B[ A[i] ] != 0
found duplicate number
else
B[A[i]] = 1
In-place algorithm
for (i=1..N)
{
idx = abs(A[i])
if (A[idx] < 0)
the duplicate number is idx
else
A[idx] *= -1
}
Example:
A={5,4,2,3,2}
i=1, a[5] = -2
i=2, a[4] = -3
i=3, a[2] = -4
i=4, a[3] = -2
at this stage array looks like this:
A= {5,-4,-2,-3, 2}
Now i=5
idx = abs(A[5]) = 2
Checking if a[idx] is negative => A[2] is indeed negative, 2 is the duplicate number.
Since the value in the array is restricted to 1--N, the array can be easily sort in the way:
array[tmp-1] = tmp. For example, array[5]=6, array[9]=10...
During sorting the array, the duplicate number can be checked if array[tmp-1]==tmp. If so, that means these two element array[i] and array[tmp-1] own the same value.
/*
* DuplicateNumber.cpp
*
* Created on: Dec 10, 2012
* Author: ewailli
*/
#include <cstdio>
#include <iostream>
using namespace std;
// Time o(N) Space o(1)
int main()
{
int array[]={10,6,3,4,7,5,2,7,9,1};
int tmp,i=0;
while(true)
{
tmp = array[i];
if(tmp == i+1)
{
i++;
continue;
}
if(i >=10)
{
return 0;
}
if(array[tmp-1]==tmp)
{
cout<<"duplicate number is "<<tmp;
return 0;
}
array[i]=array[tmp-1];
array[tmp-1]=tmp;
}
return 0;
}
I am not sure what you intent to do? How this will find duplicate numbers? This array is not sorted.
The below may solve this problem in good time/space/elegance.
{{
sum = 0;
sum_normal=N*(N+1)/2;
xored = -1;
for(int i = 0; i < N; i++){
if(!i) xored = A[i];
else xored ^= A[i];
xored^=(i+1);
sum+=A[i];
}
int offset = sum-sum_normal;
for(int i = 0; i < N; i++)
//note: xored = duplicated_item ^ missed_item; at this point
if(xored^(A[i]+offset) == A[i]) return A[i];
}}
1. Sum all elements in array
10 + 6 + 3 + 4 + 7 + 5 + 2 + 4 + 9 + 1 = 59
2. Sum all numbers from 1 to N here N is 10 = 55
3. Subtract 59-55 = 4
So 4 is duplicate number in array.
Sa - m + r = S, [where S = summation of all the numbers and Sa = n(n+1)/2]
r = S-Sa+m - eq 1
Pa*r/m = P, [where P = product of all numbers and Pa = n!]
m = Pa*r/P - eq 2
two equations, two unknowns,,,solve it
O(n) time complexity
one could also find the duplicate by adding the numbers in the set. one by one. if the element already exist, it returns false.
add the elements, one by one, into the set, for the duplicate element, you would get false.
Andi's Solution is good and O(n) but can be optimized.
This solution will change order of elements in array.
Use value of an element as index in array. Number 5 should be stored in index-1 ie 5-1. We need to subtract 1 as array is 0-based.
If there is a duplicate, we will try to put number and its duplicate in the same location.
If all elements are unique, we will be able to find one location in array for each number in array and no conflict.
1. Start with index i = 0;
2. Use value a[i] at index i to look up location a[a[i]-1]. If number is same, we found duplicate. if not, read a[a[i]] in tmp and store a[i] in a[a[i]] and now repeat for tmp in array untill we find a[i] again.
3. increment i and repeat step 2.
e.g.
0,1,2,3,4,5,6,7,8,9
10,6,3,4,7,5,2,4,9,1
- Start with i = 0. Since a[0] =10, look up a[10-1] which is 1, so tmp =1 and a[9] =10.
tmp = i so stop and increment i to 1.
- i=1: a[1] is 6; tmp = 5 and a[5] = 6, ,
tmp = 7 and a[4] = 5,
tmp = 2 and a[6] = 7,
i -1 == tmp so stop and increment i = 2.
...
...
- i= 7 and a[7] is 4. When access a[3] , we find a[3] already have 4. Duplicate found.
Easy... O(n) time:
int getDuplicate(int arr[]) {
int v[] = new int[arr.length];
for(int i=0; i<arr.length; i++) {
if(v[arr[i]-1]++ > 0)
return arr[i];
}
return -1;
}
The issue with this code, while it may be fast, if the input array is large, you are basically doubling the amount of memory needed. In a case where there are a few thousand elements, it is not a big deal, but if you have several million or billion elements, it could end up being a problem
1. If length of array = n, ActualSum = n*(n+1)/2 ; ActualProd = n!
2. We can obtain sum and prod of given array in linear time
3. We have two unknowns to solve: (1) the repeating element, (2) the missing element
4. We have two equations to solve
The following code returns the missing element:
public static int missingElem(int[] A)
{
int len= A.length;
int sumArray = 0;
int prodArray = 1;
int actualSum = 0;
int actualProd = 0;
int elem=0;
for (int i = 0; i < A.length; i++) {
sumArray+=A[i];
prodArray*=A[i];
}
actualSum = (len*(len+1))/2;
actualProd = factorial(len);
elem = (actualProd * (sumArray-actualSum))/(prodArray - actualProd);
return elem;
}
public static int factorial(int num)
{
if(num==0)
return 1;
return num*factorial(num-1);
}
I think a solution exists such that if we Xor each item with its (index+1)
eg.4,5,1,2,3,4
dupElement=0;
(((
for(i=0;i<n;i++)
{
duplicateElement ^=(a[i]^(i+1));
}
}}}
should return 4.
If I'm reading this right, this solution gives you the XOR of the duplicate value and the missing value. So if we restrict ourselves to values of 1 through N-1 in the array, this approach will work since we can just XOR with N at the end to get the duplicate value since we know the missing value is N. But since the original problem states that values of 1 through N are permissible, this approach unfortunately will not work.
You may use one bit to represent the occurrence of a value. This requires to additional info, which we all have
1. minimum or maximum of possible value,
2. size of the subject array,
the LO bit of the int pointed by the bit field pointer will represent the occurrence of 1
#include<stdio.h>
#include<stdlib.h>
#include<limits.h>
void f(unsigned *ary_p, unsigned n){
if(n<1) {
printf("invalid array\n");
exit(EXIT_FAILURE);
}
unsigned * bitfield=calloc((n-1)/(sizeof(int)*CHAR_BIT)+1,sizeof(int));
unsigned i,temp,int_offset,bit_offset,m;
for(i=0;i<n;i++){
temp=ary_p[i];
int_offset=(temp-1)/(sizeof(int)*CHAR_BIT);
bit_offset=(temp-1)%(sizeof(int)*CHAR_BIT);
m=1<<bit_offset;
if(bitfield[int_offset]&m){ /*if the accoding bit is set-->>found duplicate*/
printf("duplicate %u found at index:%u\n",temp,i);
exit(EXIT_SUCCESS);
}
else
bitfield[int_offset]|=m;
}
}
Create the binary search tree and during creation we can identify the duplicate elements in the array.
Time complexity will be O(nlogn).
any suggestions are welcomed!!!
I think that we can use the principles of quicksort in this case.
In the first round, we select a value = N/2. We go through the whole array, put all elements < N/2 in the left, all elements > N/2 in the right, and can check if N/2 is the one duplicated. Now we sum all elements in the left and see if the summed value is what we expect. Otherwise, there is a duplicate in the left. If it's not the case, the duplicate is in the right. It takes N for this round.
In the second round, repeat the same procedure for the part with the found duplicate. It takes N/2 for this round.
So finally we can find the duplicate with N + N/2 + N/4 +... = 2N. So it takes O(n) for time, and O(1) for space.
Hope it's correct :)
I guess this question is similar to find first missing number in a array.
If (data[index] != index)
swap (data, index, data[index]);
Do this swap from 0 to len - 1. If index[A] is already occupied by number A, then A is the duplicate.
The following is a implementation in Java.
{
public int findDuplicate(int[] data){
int len = data.length;
for (int index = 0; index < len; index++){
while(index != data[index]){
if (index != data[index] && data[index] != data[data[index]])
swap(data, index, data[index]);
else if (data[index] == data[data[index]])
return data[index];
}
}
return -1;
}
private void swap(int[] data, int src, int dest){
int tmp = data[src];
data[src] = data[dest];
data[dest] = tmp;
}
}
Comment me if I got wrong, please
I don't know if anyone will read this very late solution, but I think I have a very interesting one. : )
The basic idea is to mark the number we have found. If we find m, we will modify a[m-1].
BUT BUT, I don't modify the value of a[m-1], I change the signal (positive or negative).
If we find m, then point to a[m-1], but we find a[m-1] < 0 (I don't care the value in a[m-1], just the signal), then m is the duplicate!
Only assumption is that all numbers are positive, which is guaranteed by the description. Here is the code:
public static int findDuplicates(int[] a)
{
for (int i=0; i<a.length; i++)
{
int index = Math.abs(a[i]);
if (a[index-1] < 0)
return index;
else
a[index-1] = -a[index-1];
}
return -1; //which won't happen, but in case.
}
#include<iostream>
using namespace std;
int func(int sourceArray[], const int& length){
if(sourceArray == NULL || length <= 0)
return -1;
int target = -1;
for(int i = 0; target == -1 && i < length; i++){
while(sourceArray[i] != i+1){
int temp = sourceArray[i];
if(sourceArray[temp-1] == temp){
target = temp;
break;
}else{
sourceArray[i] = sourceArray[temp-1];
sourceArray[temp-1] = temp;
}
}
}
return target;
}
int main(int argc, char* args[]){
int sourceArray[] = {10,6,3,4,7,5,2,4,9,1}, length = 10;
cout << func(sourceArray, length) << endl;
return 0;
}
If n integers range from 1 to n-1 then:
take sum of n-1 integers: (n-1)n/2...O(1)
take sum of the elements in the array: S....O(n)
the duplicate = S - (n-1)n/2
example: 7 9 8 1 4 3 5 6 8 2.........in this 9 elements array 8 is repeated
so basically we have 9 unique elements with sum 9*10/2 = 45
sum of array S = 53
repeated = 53 - 45 = 8
This is the best answer if only 1 to n-1 values are allowed and n integers are there in the array
//The important advantage of this algo is that the "array is restored back to its original" although it is modified.
- Saurabh Kr Vats December 09, 2012//It also places the elements where it belongs i.e initial sublist is sorted.
//Run Time Complexity: 0(n)
//Space Somplexity: 0(1)
//The important advantage of this algo is that the "array is restored back to its original" although it is modified.
//It also places the elements where it belongs i.e initial sublist is sorted.
//It also handles 0 case
#include <stdio.h>
void swap(int *p,int *q)
{
int temp;
temp=*p;
*p=*q;
*q=temp;
}
void printRepeating(int arr[], int size)
{
int i,j;
for(i=0;i<size;i++)
while(arr[i]!=i)
if(arr[i]!=arr[arr[i]])
swap(&arr[i],&arr[arr[i]]);
else
break;
//Initial sublist is sorted
for(i=0;i<size-1&&arr[i]<arr[i+1];i++,j=i) ;
if(i==size-1)
{
printf("There are no repeating elements\n");
return;
}
else
printf("The repeating elements are: ");
//Printing duplicates
for(i=i+1;i<size;i++)
{
if(arr[i]!=i && arr[arr[i]]>=0 && arr[i]==arr[arr[i]])
{
printf("%d ",arr[i]);
arr[arr[i]]=-1;
}
}
//Restoring to oirginal
for(i=0;i<=j;i++)
if(arr[i] == -1) arr[i]=i;
}
void printArray(int a[],int size)
{
int i;
for(i=0;i<size;i++)
printf("%d ",a[i]);
printf("\n");
}
int main()
{
int arr[] = {1, 2, 3, 1, 3, 0, 6};
int arr_size = sizeof(arr)/sizeof(arr[0]);
printRepeating(arr, arr_size);
printf("\nIt also places the elements where it belongs i.e initial sublist is sorted\n");
printArray(arr,arr_size);
getchar();
return 0;
}