CareerCup

Create a class that maintains two HashMap members. One member is to store <K, V> pair and the other is for <V, K> pair.

Well we can have a single map and while inserting

Map.put(key,value)
Map.put(value,key)

The only constraint is all the keys and the values should b unique.

package Maps;

import java.util.HashMap;

public class BiDirMap<K,V> {
private HashMap<KeyValWrapper<K,V>, KeyValWrapper<K,V>> keyToValMap;
private HashMap<KeyValWrapper<K,V>, KeyValWrapper<K,V>> valToKeyMap;

enum keyOrVal {
KEY, VALUE
}

public BiDirMap (int initialCapacity) {
keyToValMap = new HashMap<KeyValWrapper<K,V>, KeyValWrapper<K,V>>();
valToKeyMap = new HashMap<KeyValWrapper<K,V>, KeyValWrapper<K,V>>();
}

public V getVal (K key) {
KeyValWrapper wrapper = new KeyValWrapper(key);
KeyValWrapper<K, V> retkey = keyToValMap.get(wrapper);
if (retkey != null) {
return retkey.getVal();
} else {
return null;
}
}

public K getKey (V val) {
KeyValWrapper wrapper = new KeyValWrapper(val);
KeyValWrapper<K, V> retKey = valToKeyMap.get(wrapper);
if (retKey != null) {
return retKey.getKey();
} else {
return null;
}
}

public void put (K key, V value) {
KeyValWrapper kWrapper = new KeyValWrapper(key);
kWrapper.setVal(value);
KeyValWrapper vWrapper = new KeyValWrapper(value);
vWrapper.setVal(key);
keyToValMap.put (kWrapper, kWrapper);
valToKeyMap.put (vWrapper, vWrapper);
}

private static class KeyValWrapper<K,V> {
K key;
V value;

public KeyValWrapper (K kv) {
this.key = kv;
}

public void setVal (V value) {
this.value = value;
}

public V getVal() {
return value;
}

public K getKey() {
return key;
}

public boolean equals (Object wrap) {
KeyValWrapper<K, V> wrapper = (KeyValWrapper<K, V>) wrap;
if (this.key.equals(wrapper.getKey())) {
return true;
} else {
return false;
}
}

public int hashCode () {
return key.hashCode();
}
}
}

class Mapp extends HashMap {

Vector arKey = new Vector();
Vector arval = new Vector();

@Override
public Object put(Object key,Object value){
arKey.add(key);
arval.add(value);
return super.put(key,value);
}


public Object getFromValue(Object key){
return arKey.get(arval.indexOf(key));
}

@Override
public Object get(Object key){
return super.get(key);
}
}

public class BiDirectionalHexMap<T, U> extends HashMap<T, U>
{

    private static final long serialVersionUID = 1L;
    private HashMap<U, List<T>> reverse = new HashMap<U, List<T>>();

    void populateReverse()
    {
        Set<T> kset = keySet();
        Iterator<T> itr = kset.iterator();
        while (itr.hasNext())
        {
            T key = itr.next();
            U val = get(key);
            if (reverse.containsKey(val))
            {
                reverse.get(val).add(key);
            }
            else
            {
                ArrayList<T> x = new ArrayList<T>();
                x.add(key);
                reverse.put(val, x);
            }
        }
    }
    
    public List<T> getKeys(U value)
    {
        populateReverse();
        return reverse.get(value);

    }

    public static void main(String[] args)
    {
        BiDirectionalHexMap<String, String> map = new BiDirectionalHexMap<String, String>();
        map.put("key1", "val");
        map.put("key2", "val");
        System.out.println(map.getKeys("val"));
        System.out.println(map.get("key1"));
    }
}

1.) If space is constraint: Use a 2D array to store the key-value pair.
2.) If time is constraint: Use a data structure which encapsulates 2 hashmaps <K,V> and <V,K>

Create two arrays and one hash function. One array stores the key, the other stores the value. When adding the pair to bihash, store the key in the same position of the array as the value. During query, use hash function to get the position of the array, and return the value from the value array if it's finding value to a key and vice versa.