Reverse lookup hash table to find the smallest key

Question

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

My approach was to sort the hash table by key and repeat it to find the key corresponding to the found 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 that you can, if you can guarantee that what you are testing, and the type of your keys Number.

. O (n log (n)), - O (n), 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 BiMap, ; .

.

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

, ( Number, Number Comparable). , .