Microsoft Interview Question for Software Engineer / Developers


Country: United States




Comment hidden because of low score. Click to expand.
8
of 8 vote

//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.

//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;
}

- Saurabh Kr Vats December 09, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
8
of 8 vote

# 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

- Saurabh Kr Vats December 09, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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?

- Andy2000 December 10, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

The answer is not correct because there could be pure circles in the array. For example, given an input like 1, 2, 2, 3. The algorithm will give 3 instead of 2.

- Walainlord December 12, 2012 | Flag
Comment hidden because of low score. Click to expand.
4
of 8 vote

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

- bgabbasov December 10, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
1
of 1 vote

N could be as maximum as largest possible value of int data type.In such a case we cannot find sum1 and sum2.

- Ravi December 11, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- bgabbasov December 11, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

What to do with a and b now? Which is the required answer?

- Anonymous January 02, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

The system of equations if followed from:
sum from k = 1 to n (k) - a + b = Sum from k = 1 to n (A[k])
and
sum from k = 1 to n (k^2) - a^2 + b^2 = Sum from k = 1 to n (A[k]^2)

a is a missing value, and b is a duplicate

- bgabbasov January 02, 2013 | Flag
Comment hidden because of low score. Click to expand.
2
of 2 vote

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.

- Grr1967 December 09, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
2
of 2 vote

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;
}

- lwh20053276@163.com December 10, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

I am not sure what you intent to do? How this will find duplicate numbers? This array is not sorted.

- Andy2000 December 10, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

The array is sorted by this way:
array[0]=1,array[1]=2...array[9]=10
After sorted, you will find the array with one duplicate number and one mussing one. Of course the sorting process can be stopped when the duplicate number is found.

- lwh20053276@163.com December 10, 2012 | Flag
Comment hidden because of low score. Click to expand.
2
of 2 vote

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];

}}

- Ben December 10, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

ben..i am not able to understand ur logic...can u please explain with example..thanks!

- Anonymous December 10, 2012 | Flag
Comment hidden because of low score. Click to expand.
2
of 4 vote

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.

- Yogesh M Joshi January 20, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

n(N+1)/2 - (sum of elements in given array ) = ANSWER

- smashit December 14, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

10 + 6 + 3 + 4 + 7 + 5 + 2 + 4 + 9 + 1 = 51

Where did you learn to count?

- Dash December 23, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

N could be large. So this algorithm is inferior to Ben's

- CptSudoku May 11, 2015 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

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

- Andi December 09, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

one could also find the duplicate by adding the numbers in the set. one by one. if the element already exist, it returns false.

- D.A. December 09, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

what about space complexity?

- Andi December 09, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

worst case, o(n)

- Anonymous December 09, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

my sol is just space complexity is constant space

- Andi December 09, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

where you will hold this P & S? Long Long ? N could be pretty large.

- Geek December 09, 2012 | Flag
Comment hidden because of low score. Click to expand.
1
of 5 vote

add the elements, one by one, into the set, for the duplicate element, you would get false.

- D.A. December 09, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Hey,
N is very big. You could not use a set to store all these numbers because we have limited memory.

- Kevin March 02, 2013 | Flag
Comment hidden because of low score. Click to expand.
1
of 3 vote

This comment has been deleted.

- Administrator December 09, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
1
of 1 vote

int duplicate(int A[], int n)
{
for(int i = 0; i < n; i++)
{
while(A[i] - i != 1)
{
if(A[i] == A[A[i] - 1])
return A[i];
else
swap(A[i], A[A[i] - 1]);
}
}
}

- Walainlord December 12, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 2 vote

elements = []
for ele in A:
  if ele in elements:
    print ele
  else:
    elements.append(ele)

- lexo.charles December 09, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
6
of 6 votes

so true!

- Saurabh Kr Vats December 09, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

Why not sort the array first and then compare the elements...whichever is found to be equal to its last element is duplicate !

- puchkii December 09, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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.

- Curious December 09, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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;
}

- Just an Intern December 10, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- M.Zimmerman6 December 10, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- anonymouse December 10, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Does that code returns the missing element? I think it returns the duplicate element.

- Chryssa August 07, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

Apply heap sort on input array and scan the array linealy to find duplicate
complexity : o(nlogn)(heap sort) + o(n)(linear scan)

- Anonymous December 10, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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.

- Ashar December 10, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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.

- RS December 11, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

def findduplicate(a_list):
	countlist=list(map(a_list.count, a_list))
	i=0
	for i in range(len(countlist)):
		if countlist[i] > 1:
			return a_list[i]

- mailming December 10, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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;
	}
}

- eThomus December 12, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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!!!

- sonu December 12, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

We can use a HashSet instead...i will utilize extra space like BST but will give us a better search performance of O(1) compared to O(log n) for BST.

- Anonymous December 24, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

Algo
Use a bit vector to identify the range of number BitArray myBA1 = new BitArray( N);
4 billion integers represented at the Ith location in the Array will only consume around 512 mbz
Scan through the Array and previously modified bit in the scan is your resultant answer

- Anonymous December 19, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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 :)

- ngoc December 26, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

As he said only one element is duplicated,
XOR all the elements of the array the remaining element after the Xor is the required duplicated element..!! :)

- Tejasvi Nuthalapati January 24, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- Anonymous February 21, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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.
	}

- Jason.WengPengfei March 27, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

#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;

}

- tGone August 19, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

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

- Imon December 10, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

This is the best answer if only 1 to n-1 values are allowed and n integers are there in the array

- dinnu.k December 10, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

unfortunately that is not the case

- The Artist December 10, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

There could be some missing integer as well, apart from one duplicate, then this solution will not hold.

- aps December 11, 2012 | Flag
Comment hidden because of low score. Click to expand.


Add a Comment
Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

Learn More

Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.

Learn More

Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

Learn More

Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.

Learn More