xyz Interview Question
Java DevelopersCountry: India
Interview Type: In-Person
1. Take a HashSet
2. Keep putting the value until you find a value that already exists.
3. Will be done in one scan only
static int findDuplicate(int[] input) {
HashSet<Integer> hashSet = new HashSet<>();
for(int item : input) {
if(hashSet.contains(item)) {
return item;
}
hashSet.add(item);
}
throw new NoSuchElementException("No duplicate found");
}
1) MergeSort.
- zr.roman November 29, 20152) in one scan compare arr[ i ] and arr[ i+1 ] elements.
Total complexity O(n*log n + n), i.e. O(2n*(log n + 1)). Roughly O(n*log n).