Interview Question
Country: India
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));
}
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)
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
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.
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
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
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)...
O(n)
public static void FindMissingElements(int[] a) {
HashSet<Integer> mySet = new HashSet<Integer>();
for (int i = 0; i < a.length; i++) {
mySet.add(a[i]);
}
int j = 0;
ArrayList<Integer> missingList = new ArrayList<Integer>();
for (int i = 1; i <= a.length; i++) {
if (a[j] != i) {
if (!mySet.contains(i))
missingList.add(i);
}
j++;
}
System.out.println(missingList);
}
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.
- Anonymous February 29, 2012