Interview Question


Country: India




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

Using in-place markers can solve it in two scans. Steps follows

1. In first scan, examine each element, say E, to see if arr[E] was negative. If not, negatate it, otherwise, E is a duplicate.

2. In the second scan, element by element to this: if arr[i] is negative, make it positive (restore the data to its original value) else if arr[i] is positive, then i + 1 is a missing value.

This algorithm works without limitation on how many numbers are duplicated or missing, and how many times a number are duplicated.

Here is the Java code.

public static void main(String[] args) {

		int[] arr = new int[] {5, 1, 2, 1, 3, 2, 4, 7, 2, 10};
		
		TreeSet<Integer> dup = new TreeSet<Integer>();
		TreeSet<Integer> mis = new TreeSet<Integer>();
		
		for (int i = 0; i < arr.length; ++i) {
			int temp = Math.abs(arr[i]) - 1;
			if (arr[temp] < 0) {
				dup.add(temp + 1);
			}
			else if (arr[temp] > 0) {
				arr[temp] = -arr[temp];
			}
		}
 		
		for (int i = 0; i < arr.length; ++i) {
			if (arr[i] < 0) {
				arr[i] = -arr[i];
			}
			else {
				mis.add(i+1);
			}
 		}
		
		System.out.println(String.format("Test data:\t%s", Arrays.toString(arr)));
		System.out.println(String.format("Duplicate:\t%s", dup.toString()));
		System.out.println(String.format("Missings:\t%s", mis.toString()));
	}

- Anonymous February 29, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Reformat for better viewing

public static void main(String[] args) {

		int[] arr = new int[] { 5, 1, 2, 1, 3, 2, 4, 7, 2, 10 };

		TreeSet<Integer> dup = new TreeSet<Integer>();
		TreeSet<Integer> mis = new TreeSet<Integer>();

		for (int i = 0; i < arr.length; ++i) {
			int temp = Math.abs(arr[i]) - 1;
			if (arr[temp] < 0) {
				dup.add(temp + 1);
			} else if (arr[temp] > 0) {
				arr[temp] = -arr[temp];
			}
		}

		for (int i = 0; i < arr.length; ++i) {
			if (arr[i] < 0) {
				arr[i] = -arr[i];
			} else {
				mis.add(i + 1);
			}
		}

		System.out.println(String.format("Test data:\t%s", Arrays.toString(arr)));
		System.out.println(String.format("Duplicate:\t%s", dup));
		System.out.println(String.format("Missings:\t%s", mis));
	}

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

doesnot give the missing number{1,2,2,3,3,6}

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

change mis.add(i+1) to mis.add(arr[i]+1) and it works.

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

wrong working

- dilip kasana May 18, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 2 vote

Use HashMap ...
Just iterate over hashMap n times ... on every iteration note the value of loop counter if the hashMap.containsValue(loopCounter)==false.
O(n)

- yogeshhan March 01, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

What if you had an array of size 5 {1,2,3,5,6} your solution wouldn't work then. When doing the HashMap.Contains you'll need to check whether array[i] <= array.length

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

No it will work.
We will have a for loop
for(i=1 ; i<=n ;i++)
check if map.containsValue(i);

- yogeshhan March 04, 2012 | Flag
Comment hidden because of low score. Click to expand.
-1
of 1 vote

1.In case of a unique element set.
Parse through the elements of the set, marking the presence into an index-array.
then parse through the given array to unmark the elements in index-array.
a. If element to be unmarked is already unmarked, then that element is redundant.
b. If after completion, the remaining unmarked elements are not in the given array.
2.In case of non-unique element set.
Parse through the elements of the set, incrementing the value of an index-array.
then parse through the given array to decrement the elements in index-array.
a.If after completion, any negative index is present then it is a repeated more number of times.
b.If after completion, any positive index remains , that element is less repeated then in the set.

- guru February 29, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Looking for optimized solutions with complexity less than O(n)

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

how about...as we know the range of number we can calculate total sum {1, n} by n*(n+1)/2 and now traverse the array and all the numbers whose occurence is atleast one and then subtract the sum from the total sum . the result is a + b = K.
this way a and b can easily be deduced

- JOA February 29, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

how about...as we know the range of number we can calculate total sum {1, n} by n*(n+1)/2 and now traverse the array and all the numbers whose occurence is atleast one and then subtract the sum from the total sum . the result is a + b = K.
this way a and b can easily be deduced

- JOA February 29, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Since the input is an array of ints, what about using a bit vector to flip the appropriate bit when we see a number (do nothing if it's a duplicate). We can then see which bits in the array are still 0's, and those will be the missing numbers.

Works for any n with any number of numbers missing.

This is O(n) since it does one pass over the whole array, but I'm not sure how it can be less than O(n) given the conditions (ie. it's unsorted and does not allow dupes)...

- M February 29, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Less than O(n) is impossible since the whole set must be scanned at least once.

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

Less than O(n) is impossible since the whole set must be scanned at least once.

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

Less than O(n) is impossible since the whole set must be scanned at least once.

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

Can someone post a better solution,if not O(n).

- Krupa March 06, 2012 | Flag
Comment hidden because of low score. Click to expand.
-1
of 1 vote

Build a bitmap with the numbers corresponding to bit positions. The only two 0s in this bitmap will be indicative of the numbers you're missing. This is O(n).

- Rajat Agarwal March 21, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

O(n)

public static void FindMissingElements(int[] a) {
    
    HashSet&lt;Integer&gt; mySet = new HashSet&lt;Integer&gt;();
    
    for (int i = 0; i &lt; a.length; i++) {
        mySet.add(a[i]);
    }
    
    int j = 0;
    ArrayList&lt;Integer&gt; missingList = new ArrayList&lt;Integer&gt;();
    for (int i = 1; i &lt;= a.length; i++) {
        
        if (a[j] != i) {
            if (!mySet.contains(i))
            missingList.add(i);
            
        }
        j++;
        
    }
    
    System.out.println(missingList);

}

- dandy August 26, 2012 | Flag Reply


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