Uber Interview Question
Software EngineersTeam: Mobile
Country: United States
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;
}
}
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:
BinarySearchTree<K, V>{
.......... // balanced binary search tree with K as key and V as the value
}
TimeStampHashMap<K, V>{
Map<K, BinarySearchTree<Float, V>> keyToBSTMap;
V get(K k, Float time){
return keyToBSTMap.get(k).binarySearch(time).getValue();
}
void put(K k , Float time, V value){
keyToBSTMap.get(k).insert(time, value);
}
}
I am not sure how the Java Map data structure works, but can it map one key to two separate values? Thanks.
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
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)
- hawkap January 23, 2016