Google Interview Question
Software EngineersCountry: United States
TreeMap<Integer, RoutingRange> map = new TreeMap<>();
String findRoutingNumber(int routingNumber) {
Map.Entry<Integer, RoutingRange> entry = map.floorEntry(routingNumber);
RoutingRange range = entry.getValue();
if (range.end >= routingNumber) {
return range.bank;
}
return null;
}
public void addRange(int start, int end, String bank) {
map.put(start, new RoutingRange(end, bank));
}
We can use binary search to process multiple queries efficiently i.e O(logn). But before that, we ll sort the ranges based on starting element. For a given number, we ll check if that number is greater than the middle range last element or lesser than middle range's first element. We ll recure that way. If it is in the mid range then we simply return the range value.
These are ranges that don't overlap. we can do a binary search, range check, post sorting.
- nooooob June 08, 2019