## Uber Interview Question

Software Engineers**Team:**Mobile

**Country:**United States

I am not sure how the Java Map data structure works, but can it map one key to two separate values? Thanks.

```
public class ImprovedHashMap {
Map<Integer, TreeNode> map = new HashMap<Integer, TreeNode>();
public int get(int key, float t) {
TreeNode root = map.get(key);
int i = searchBST(root, t, root.value, root.t);
return i;
}
public int searchBST(TreeNode root, float t, int closestMatch, float closestT) {
if (root == null) {
return closestMatch;
}
if (root.t > t) {
return searchBST(root.left, t, closestMatch, t);
} else if (root.t < t) {
if (closestT > root.t) {
closestMatch = root.value;
closestT = root.t;
}
return searchBST(root.right, t, closestMatch, closestT);
} else {
return root.value;
}
}
public void put(int key, float t, int value) {
// TreeNode node = new TreeNode(value, key);
TreeNode n = new TreeNode(value, t);
TreeNode root = map.get(key);
if (root == null) {
map.put(key, n);
} else {
insert(root, n);
}
}
public static void insert(TreeNode root, TreeNode child) {
if ((root.t > child.t)) {
if (root.left == null) {
root.left = child;
} else {
insert(root.left, child);
}
} else if (root.t < child.t) {
if (root.right == null) {
root.right = child;
} else {
insert(root.right, child);
}
}
}
private static class TreeNode {
float t;
int value;
TreeNode left;
TreeNode right;
public TreeNode(int i, float t) {
this.value = i;
this.t = t;
}
}
```

Here is complete implementation:

and of cause you can implement any part of it manually like implementing your own BST or hashtable. This implementation uses standard java HashMap and TreeMap (which is standard java Red-Black tree implementation)

```
public class TimeHashMap<Key, Time, Value> {
private HashMap<Key, TreeMap<Time, Value>> map = new HashMap<Key, TreeMap<Time, Value>>();
public Value get(Key key, Time time) {
final TreeMap<Time, Value> redBlackBST = map.get(key);
if (redBlackBST == null) return null;
final Time floorKey = redBlackBST.floorKey(time);
return floorKey == null ? null : redBlackBST.get(floorKey);
}
public void put(Key key, Time time, Value value) {
if (!map.containsKey(key)) {
map.put(key, new TreeMap<Time, Value>());
}
map.get(key).put(time, value);
}
public static void main(String args[]){
TimeHashMap<String, Double, String> data = new TimeHashMap<String, Double, String>();
data.put("K",1.0,"K1");
data.put("K",2.0,"K2");
System.out.println(data.get("K",0.9));
System.out.println(data.get("K",1.0));
System.out.println(data.get("K",1.5));
System.out.println(data.get("K",2.0));
System.out.println(data.get("K",2.2));
}
}
```

1.For the "CustomHashMap" , the key objects should have public setter and getter for variable "t".

2.Store keys in "arrays" while put is called on hashmap - get next available index in array , put "Entry" in it , and call setT(int val) method passing index.

3.When calling get(K,t) -> 1)Get bucker , 2)Call getT() to get index 3)using index in array get "Entry(key-value) in constant time

Key maps to a binary search tree in HashMap. First the key is mapped to a binary search tree and then the time is searched in the binary search tree to find either the time or smallest time less than the searched time. The skeleton of the design is presented below:

- mrsurajpoudel.wordpress.com May 04, 2015