Hash table reverse lookup to find smallest key

Question

I had an interview question to search a hash table for a value and return the smallest key.

My approach was to sort the hash table by key and iterate through it to find the key corresponding to searched value.

I wrote this function in Python:

def smallestKey(x):
    my_dict = {10:20, 5:30, -2:25, 1:20}
    for key in sorted(dict.iterkeys()):
        if (my_dict[key] == x):
            print key

Is there a better approach? How can I do the same in Java?

Answer 1

I'm willing to bet you can, if you can guarantee that what you're checking against, as well as what type your keys are, is Number.

Here's a code sample. Sorting costs O(n log(n)), and the linear search is O(n), so the performance of this is about O(n log(n)).

public <K extends Number & Comparable<K>, V extends Number> K findSmallestKey(Map<K, V> values, V searchItem) {
    // Grab the key set, and sort it.
    List<K> keys = new ArrayList<>(values.keySet());
    Collections.sort(keys);
    for(K key : keys) {
        if(values.get(key).doubleValue() == searchItem.doubleValue()) {
            return key;
        }
    }
    return null;
}

Guava offers BiMap, which may be a more usable real-world case; however, it won't allow for duplicate values to be present without overwriting them.

Here's an example of that.

public <K extends Number, V extends Number> K findSmallestKeyWithBimap(BiMap<K, V> values, V searchItem) {
    return values.inverse().get(searchItem);
}

It's a great deal more terse, and doesn't need the same kind of generics as the previous one did (this one only needs to be a Number, not both a Number and Comparable). It's also a lot less flexible, and due to its nature, you're explicitly guaranteed to have a one to one mapping between keys and values.