Interview Question
Software DevelopersCountry: United States
I like this answer. My small improvement suggestion would be to handle zero by adding n instead of negation.
I think this approach is good, but if we consider the case {1, 2, 3, 3, 1}, the negation approach will give 3 as answer as first duplicate.
The naive n^2 approach will give 1 as the answer because, in first iteration of comparison in array, it will find 1 as repeated element and break there.
I guess what the interviewer means by first repeating element should be clarified during the course of the interview as technically 3 is the one that gets repeated first and 1 is the first of the elements that is repeated.
So I guess that's perception based, in any case I think the same solution could be extended to cover both requirements with a few changes.
Using negation means you have to have an extra "sign" bit, but the original input array only contains non-negative numbers, so it would have unsigned integers, which don't have a sign bit.
The extra sign bit you require represent an additional O(N) memory space requirement.
Somehow you assume that the input array already contains this unused sign bit, which you can just use, but like I said, this is highly unlikely.
@gen-x-s A sign bit is present in all integer data types. A sign bit is the very first bit (MSB) i.e the leftmost.
There is no way one can introduce an extra bit in a given integer. Negation implies only making the sign bit which is 0 for positive numbers to 1 indicating a negative number. So, this algorithm is definitely O(1) when we talk of space :-)
private static int FindDupl(int[] arr)
{
int i = 0;
while(i < arr.Length)
{
// if array index equals to value then mark as processed and increase index on one
if(arr[i] == i)
{
arr[i] = -1;
i++;
continue;
}
// get value from the array at current index
var n = arr[i];
// check if we processed this array index
if(arr[n] == -1)
{
// return duplicate value
return n;
}
// swap values and mark array element at index n as processed
arr[i] = arr[n];
arr[n] = -1;
}
// no duplicates
return -1;
}
I have one doubt in this code
See below
import java.util.ArrayList;
public class Career {
static int[] raga = new int[] {6,10,11,1,2,3,5,2,1,5,6,7,9,8,0};
/**
* @param args
*/
public static void main(String[] args) {
int i = 0;
printarray();
System.out.println();
while(i < raga.length) {
if(raga[i] == i) {
raga[i] = -1;
i++;
continue;
}
int n = raga[i];
if(n == -1)
continue;
if(raga[n] == -1) {
System.out.println("Found "+ n);
break;
}
raga[i] = raga[n];
raga[n] = -1;
printarray();
System.out.println();
}
}
private static void printarray() {
for(int i = 0 ; i < raga.length; i++){
System.out.print(raga[i]+ " ");
}
}
}
Out put
6 10 11 1 2 3 5 2 1 5 6 7 9 8 0
5 10 11 1 2 3 -1 2 1 5 6 7 9 8 0
3 10 11 1 2 -1 -1 2 1 5 6 7 9 8 0
1 10 11 -1 2 -1 -1 2 1 5 6 7 9 8 0
10 -1 11 -1 2 -1 -1 2 1 5 6 7 9 8 0
6 -1 11 -1 2 -1 -1 2 1 5 -1 7 9 8 0
Found 6
here answer shud be 5 but its 6.
Python 2, O(1) space, O(n) time, not changing input array.
def find_duplicate(arr):
"""arr - contains N elements in range [0, N - 2]
returns: duplicate element"""
N = len(arr)
assert all(0 <= elem <= N - 2 for elem in arr)
fast = slow = arr[-1]
while True:
fast = arr[arr[fast]]
slow = arr[slow]
if fast == slow:
return fast
assert find_duplicate([2,0,2,1]) == 2
assert find_duplicate([0,0]) == 0
assert find_duplicate([0,1,2,3,4,2,5,6,7]) == 2
assert find_duplicate([0,1,2,3,4,4,4,4,4]) == 4
void sortedInsert(node *&head, node *newnode)
{
node *temp = head;
if(head == NULL || head->data >= newnode->data)
{
newnode->next = head;
head = newnode;
}
else
{
while(head->next != NULL && head->next->data < newnode->data)
{
head = head->next;
}
newnode->next = head->next;
head->next = newnode;
}
}
Build a HashMap and iterate over array, inserting each element in the HashMap,
if you happen to find an element that's already in the HashMap, return it since it's the 1st repeated one.
But hashmap will take additional space requirements which can range up to n elements. Hence, space complexity will be O(n) with this approach.
/*return fist duplicate in array A[0..N-1], A[i]>=0 && A[i]<=N-1 */
/* return -1 if no duplicate found */
int findFirstDuplicate (int A[], int N)
{
for (int i=0; i<N; i++) {
while (A[i]!=i) {
int t = A[i];
if (t == A[t]) {
return t;
}
A[i] = A[t];
A[t] = t;
}
}
//no duplicate found
return -1;
}
Possible approaches:
1. Use Hashmap / set - but the question says space complexity is o(1) hence this option is ruled out for this problem.
2. Use quick sort - time complexity is O(log n) + iterate the array for 2nd time to list the duplicate values which is O(1). Total time complexity is O(log n) + O(1) which is obviously lesser than O(n)
3. Naive solution: iterate through each element one by one and store the values in "duplicate array". time complexity is O(n-1) , because we have to iterate through n-1 times. however space complexity for the worst case scenario is O(log n) i.e 50% values in arrays are duplicated. Hence we may not achieve space complexity O(1) in this scenario
Use Negation.
Since the range is from 0 to n-1.
1) Iterate over the given array and go to the corresponding index of each value and change its sign to negative.
ex- For {1,2,3,0,3} since a[0]=1, we make a[a[0]] = -2 i.e a[1]=-2;
then a[a[1]] = -3
and so on.
2) When you encounter a value that is already negative after step 1 then that index is the repeated value.
I have a feeling the question should be for numbers from 1 to n-1, which will ensure there is one duplicate. So, the above solution is only for 1 to n-1.
- teli.vaibhav May 02, 2015However, 0 can be simply handled with a flag I suppose.