4

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?

Ramya
  • 284
  • 2
  • 5
  • 18
  • 2
    You'd be better to do a linear search through all keys and recording the max without sorting, since sorting will take `Theta(nlogn)`. – C.B. Mar 14 '14 at 03:11
  • 1
    [It seems like][1] you would need an external library to do it in Java. [1]: https://stackoverflow.com/questions/1670038/does-java-have-a-hashmap-with-reverse-lookup?rq=1 – Acapulco Mar 14 '14 at 03:12
  • @C.B. has a point there. – Acapulco Mar 14 '14 at 03:13
  • @Acapulco, Thanks! What if I cannot use an external library? – Ramya Mar 14 '14 at 03:19
  • 1
    @Ramya check the answer of GETah, from Oct 20, 2011. It's a simple implementation of a bidirectional map, which you can see as a structure that has two maps inside, with the keys and values mirrored. So basically use k1 and v1 as key and value in map1, and in map2 use v1 as key and k1 and value. Thus you can query the map both ways. – Acapulco Mar 14 '14 at 03:36
  • The question is self-contradictory. Searching for a value returns a value. Returning the smallest key returns a key. Clarification is required: also an explanation of why a hash table is being used at all when key ordering is required. – user207421 Jun 27 '15 at 04:01
  • @EJP, as I pointed out in my question, this was an interview question. There is a hash map and you need to implement search by value (and return corresponding key), instead of the normal search by key (and return corresponding value). I'm not sure what's confusing to you. I did not choose a hash map for this operation, the requirement states so. My question was whether there is better approach than ordering keys. – Ramya Jun 28 '15 at 05:36

1 Answers1

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.

Makoto
  • 104,088
  • 27
  • 192
  • 230
  • Wouldn't the search item be the smallest key? If this is the case then there's no need for searchItem. Just return the first element in your sorted array (if you sorted smallest to biggest evidently), no? On the other hand, if you do need to search for a specific item, binary search would be faster, after all it's already sorted. – Acapulco Mar 14 '14 at 03:39
  • Not necessarily. If you're not using `BiMap`, and you have two values that are the same, you need to find the key of the first occurrence. That doesn't always guarantee that it's the first element; if my search item is 300, and its key numbering turns out to be 127, and 133, then 127 is the correct answer. – Makoto Mar 14 '14 at 03:45
  • That is true. But how about using binary search instead of a linear one? – Acapulco Mar 14 '14 at 03:47
  • Well...I couldn't use binary search, because I'm looking for a value to relate to a key, not the other way around. The only thing I've sorted is the key set. With just that, I have no knowledge of the values contained in the map - which is what I need to be searching on. – Makoto Mar 14 '14 at 03:49