Uber Interview Question for Software Engineers


Country: United States
Interview Type: In-Person




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

So, essentially,
when you use the put method, putIfAbsent method or clear operation, you would need your node to be added/updated to acquire a lock. e.g. : in Java, its done by synchronize(Node) block.

Constructor(int capacity) {
		//no threading required
	}
	public Object put() {
		//Calculate hash function
		//Traverse through the keys based on hash function
		//synchronize (Node) {
			//regular put procedure
		}
	}
        get (Key) {
		//Probably check if the lock is acquired
		//If yes, then wait for lock to be released
		//get as in a regular hashMap()
    	}
}

- pj.thegame June 14, 2018 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

ConcurrentHashMap has 2 primary goals.
1. Keeps a constant amount of buckets to store elements. For every put operation, hash identifies which bucket to copy data to and if the bucket is already full, it uses collision resolution technique like linear probing or separate chaining to find the next available bucket place.
2. The concurrent property signifies, put and get operations are thread safe. That is they acquire the lock before putting the element or reading the element, this ensures that the most recent read is always returned.

Below is the one possible implementation of ConcurrentHashMap. I am using linear probing to perform conflict resolution. If the bucket hashed is found to be occupied, I keep searching for next empty bucket by linearly looking for the bucket until the end of the bucket array.

Instead of locking a single object across all put/get, I lock at bucket level using another object array of the same size as the bucket.

public class ConcurrentHashTableUsingArray {
	
	private static final int HASH_SIZE = 128; // bucket size
	HashEntry[] table;
	Object[] locks;
	
	ConcurrentHashTableUsingArray(){
		table = new HashEntry[HASH_SIZE];
		locks = new Object[HASH_SIZE];
	}

	public void set(int key, int value) {
		//Step1: get the hash based on the key
		int hash = key % (HASH_SIZE) ;
		
		if(table[hash] == null) { // bucket is empty. Data can be inserted
			//Before setting the table with the key, lock the appropriate lock array element
			synchronized(locks[hash]) {
				System.out.println("set(): No Collision for key = " + key + " hash = " + hash);
				table[hash] = new HashEntry(key,  value);
				locks[hash].notifyAll(); //notify all waiting threads and release the lock
			}
		}
		//Else is the collision issue. In the linear probing, Keep checking next array locations
		else {
			boolean locationFound = false;
			for(int i=hash+1; i<HASH_SIZE; i++) {
				if(table[i] == null) {
					synchronized(locks[i]) {
						table[i] =  new HashEntry(key,  value);
						locationFound = true;
						locks[i].notifyAll();
					}
				}
			}
			
			if(!locationFound) {
				//There was no space from the hash location to the end of the array. Check
				// the begining of the array instead
				for(int i=0; i<hash; i++) {
					synchronized(locks[i]) {
						table[i] =  new HashEntry(key,  value);
						locationFound = true;
						locks[i].notifyAll();
					}
				}
				
				if(!locationFound) {
					System.out.println("HashMap is full, we can not store any more data thowing HashMapOverFlowException");
				}
			}
		}
	}
	
	public int get(int key) {
		//Step1: Generate the Hash from the key
		int hash = key % (HASH_SIZE) ;
		if(table[hash] != null) {
			//Check if this key matches the key stored in the object at this location
			HashEntry entry = table[hash];
			if(entry.getKey() == key) {
                                synchronized(locks[hash]) {
					//We can again check here to see the key is still same
					//correct entry found return this object
					System.out.println("get(): No Collision for key = " + key + " hash = " + hash);
					return entry.getValue();
				}
			}
			/*
			 * else we have a collision and wrong value is placed in this location due to linear probing. 
			 * So keep searching the array until we find the object with the matching key 
			 */
			else {
				System.out.println("get(): Collision detected for key = " + key + " hash = " + hash);
				for(int i=hash+1; i<HASH_SIZE; i++) {
					if(table[i] != null) {
						entry = table[i];
						if(entry.getKey() == key) {
							
System.out.println("get(): Linear probling key found at location = " + i + " for hash = " + hash);
							//correct entry found return this object
							return entry.getValue();
						}
					}
				}
				//We reached here that means, the key is not found from the hash location till the end of the array
				for(int i=0; i<hash; i++) {
					if(table[i] != null) {
						entry = table[i];
						if(entry.getKey() == key) {
							synchronized(locks[i]) {
								System.out.println("get(): Linear probling key found at location = " + i + " for hash = " + hash);
								//correct entry found return this object
								return entry.getValue();
							}
						}
					}
				}
				
				//Now if we reached here that means the element was never added to the hashmap. So just return the lowest integer
				return Integer.MIN_VALUE;
			}
		}
		else {
			//If the entry at that location is null that means there is no object in the array matching that key
			return Integer.MIN_VALUE;
		}
	}
	
	public static void main(String[] args) {
		HashTableUsingArray map = new HashTableUsingArray();
		
		map.set(5, 5);
		System.out.println("map.get(5) = " + map.get(5));
		
		map.set(128, 128);
		System.out.println("map.get(128) = " + map.get(128));
		map.set(0, 0);
		System.out.println("map.get(0) = " + map.get(0));
		
	}
}


Result 
=========
set(): No Collision for key = 5 hash = 5
get(): No Collision for key = 5 hash = 5
map.get(5) = 5
set(): No Collision for key = 128 hash = 0
get(): No Collision for key = 128 hash = 0
map.get(128) = 128
get(): Collision detected for key = 0 hash = 0
get(): Linear probling key found at location = 1 for hash = 0
map.get(0) = 0

- Saurabh August 15, 2018 | 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