## Interview Question for Software Developers

• 0

Country: United States

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

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=1, we make a[a] = -2 i.e a=-2;
then a[a] = -3
and so on.
2) When you encounter a value that is already negative after step 1 then that index is the repeated value.

``````public static int getRepeatedNumber(int[] a)
{
if(a==null || a.length==0)
return -1;
int currentIndex;

for(int i=0;i<a.length;i++)
{
currentIndex=Math.abs(a[i]);

if(a[currentIndex]<0)
return currentIndex;
else
a[currentIndex]*=-1;
}

return -1;
}``````

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.
However, 0 can be simply handled with a flag I suppose.

Comment hidden because of low score. Click to expand.
0

I like this answer. My small improvement suggestion would be to handle zero by adding n instead of negation.

Comment hidden because of low score. Click to expand.
0

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.

Comment hidden because of low score. Click to expand.
0

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.

Comment hidden because of low score. Click to expand.
0

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.

Comment hidden because of low score. Click to expand.
0

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

Comment hidden because of low score. Click to expand.
0

I would make sure to ask if the integers are unsigned or not. If they are then negating them would instead make them wrap around in certain languages and depending on this functionality would be unadvised. I would instead go with the first comment to add N and check if a number is >= N

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

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

Comment hidden because of low score. Click to expand.
0

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.

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

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

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

void sortedInsert(node *&head, node *newnode)
{

node *temp = head;

if(head == NULL || head->data >= newnode->data)
{
}
else
{
while(head->next != NULL && head->next->data < newnode->data)
{
}

}
}

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

``````int findFirstDuplicatedNumber(int A[], int n)
{
int i = 0;

while (i < n)
{
if (A[i] == i) ++i;

else
{
if (A[i] == A[A[i]]) return A[i];

else swap(A[i], A[A[i]]);
}
}

return -1;
}``````

Comment hidden because of low score. Click to expand.
-1
of 1 vote

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.

Comment hidden because of low score. Click to expand.
0

But hashmap will take additional space requirements which can range up to n elements. Hence, space complexity will be O(n) with this approach.

Comment hidden because of low score. Click to expand.
0

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

Comment hidden because of low score. Click to expand.
-1
of 1 vote

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

Comment hidden because of low score. Click to expand.
0

For 2nd approach Quick sort has time complexity O(n log n) not O(log n). Plus iteration of array to find duplicates has worst case complexity O(n)

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.

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