Uber Interview Question for Software Engineers


Team: Mobile
Country: United States




Comment hidden because of low score. Click to expand.
1
of 1 vote

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;
		}
	}

- Ajak6 November 02, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
1
of 1 vote

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));
  }
}

- hawkap January 23, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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);
	}

}

- mrsurajpoudel.wordpress.com May 04, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- Arindam September 18, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

My knowledge on Java Map is limited, but can it map one key to multiple values?

- Arindam September 18, 2015 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

But if we are to design HashMap, shouldn't it guarantee o(1) time complexity (Amortized)? Your solution is o(logn) in every case. I think the data structure we use should be something like:

Map<Integer, Map<Integer, V>>

map.

- Anonymous February 01, 2016 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- Vishal Chougule August 05, 2016 | Flag Reply


Add a Comment
Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

Learn More

Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.

Learn More

Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

Learn More

Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.

Learn More