Interview Question for Software Developers


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

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.

- teli.vaibhav May 02, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- Anonymous May 03, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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.

- AP May 03, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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.

- teli.vaibhav May 04, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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 May 05, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- teli.vaibhav May 07, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- SycophantEve June 14, 2015 | Flag
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;
}

- Eugene May 02, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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.

- Raghav Pai May 07, 2015 | Flag
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

- bobby May 02, 2015 | Flag Reply
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)
{
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;
}
}

- Raj May 02, 2015 | Flag Reply
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;
}

- malinbupt May 07, 2015 | Flag Reply
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.

- guilhebl May 02, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- AP May 02, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- YZ May 02, 2015 | Flag
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

- Raj May 02, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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)

- AP May 03, 2015 | Flag


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