Expedia Interview Question Software Engineer in Tests
Team: SDET
Country: India
Interview Type: Phone Interview
When I told to use hashmap she asked me that whether I am considering the numbers in range or not . She told me numbers are infinite .
Hi Zammer,
For the boolean array implementation, you could use the values stored in the data structure as indices into your boolean array. For example.
duplicate_arr[arr_size] = false //Initialize all entries of the boolean array to false.
insert_data:
if duplicate_arr[data] = false
data_structure.insert(data)
duplicate_arr[data] = true
else
print("Duplicate value!")
If you're trying to find duplicates in an infinite quantity of numbers with infinite range and you can only use a boolean array of finite size, you're going to have a hard time.
If you're allowed to have some small number of errors, I believe the traditional solution for this kind of problem is to use a Bloom filter.
public void getDupInt() {
Scanner sc = new Scanner(System.in);
System.out.println("Print a number");
int range = sc.nextInt();
HashMap<Integer, Integer> map = new HashMap<Integer, Integer>();
for (int i = 0; i < range; i++) {
if (map.containsKey(range)) {
map.put(i, map.get(i) + 1);
} else {
map.put(i, 1);
}
}
Set<Map.Entry<Integer, Integer>> entryset = map.entrySet();
for (Entry<Integer, Integer> entry : entryset) {
if (entry.getValue() == 1) {
System.out.println("unique element " + entry.getKey()
+ entry.getValue());
} else
System.out.println("duplicate element " + entry.getKey()
+ entry.getValue());
}
}
Assuming the range is limited and numbers are infinite:
1) Find min, max value inside the range
2) declare boolean array of length max-min+1
3) For each number set true in array in this way: arr[num-min] = true. If you the array has been already set then you have duplicate.
What do you mean by infinite range?
- abcd May 16, 2013Does that mean that numbers are infinite? or range is infinite?
Looking at the hint (How to implement using boolean array.?), it seems the interviewer implied that the numbers are infinite but range can be limited.
in that case, make a boolean array of length Integer.MAX_VALUE or if given range.
Whenever you receive a number, set that corresponding index to true.