Google Interview Question for Senior Software Development Engineers


Country: United States
Interview Type: In-Person




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

i will use  2 maps and a queue.

map - I  :{key->(fieldName,fieldvalue),value->list(workerIds)};
map - II :{key->workerId,value->list((fieldName,fieldValue))};
queue is priority queue with key as count and value as list of (fieldName,fieldvalue)

for any query with filedName= fname and field value = fvalue

v  = Map.contains((fname,fvalue));
wobjects = list();
if(v){
foreach val in Map.get((fname,fvalue)){
wobjects.add(mapIII.get(val));
}
}
else{
make a db call get the worker objects .
foreach(workerObject){
if(queue is not full){
 if(worker object not in map 2){
add worker object to map 2 and add to queue with key 1.
}
else(worker object in map 2){
update worker object in queue with key  = key +1.
}

}
else(queue is full){
delete worker object from queue also from map 2 and also delete all field mappings from map 1 of the element 
push the new element  
}

}

}
}

- bhanu April 18, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
1
of 1 vote

I would use the following:

I created a 2 level Map for type id search and id, with a List of workers inside. The server can only result all possible values of id, so it's not possible to do some "not in" search.

In that way, the cache process just check if there is a Workers list from some previous search and if don't, search in server and store results on server.

package com.test.carerrcup;

import java.util.HashMap;
import java.util.List;
import java.util.Map;

public class Worker {
	
	private enum IndexTypes{
		UNIT_ID,
		DEPTH_ID
	}
	
	private Map<IndexTypes, Map<Integer, List<WorkerObj>>> cache;
	
	public Worker(){
		cache = new HashMap<>();
	}
	
	
	public List<WorkerObj> getWorkersByKey(IndexTypes indexType, Integer id){
		
		List<WorkerObj> results = null;
		Map<Integer, List<WorkerObj>> workersMap = cache.get(indexType);
		
		if(cache.containsKey(indexType) && cache.get(indexType).containsKey(id)){
			results = workersMap.get(id);
		}
		else{
			
			results = getServerWorkers(indexType, id);
			
			if(!cache.containsKey(indexType)){
				cache.put(indexType, new HashMap<>());
			}
			
			if(!cache.get(indexType).containsKey(id)){
				cache.get(indexType).put(id, results);
			}
		}
		
		return results;
	}
	
	
	
	private List<WorkerObj> getServerWorkers(IndexTypes indexType, Integer id){
		
		//return a lot of workers
		
		return null;
	}
}


class WorkerObj{
	
	int workerId;
	
	int deptId;
	
	int unitId;
	
	String Name;
	
	String Surname;
	
	String Data;
}

- uebi.belli April 19, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

We can use LRU cache. I would use a 2 maps and 1 queue. The queue would be of size 100 and hold all the worker objects. The first map would have key -> unitId and value -> a list which stores the starting address of the first worker object in the queue and second value in the list would be the number of worker objects for same unitId.

Second Map : key -> deptId, value -> starting address and number of worker objects for that id.

If map contains the key then access the queue and iterate for n elements (say n is number of worker objects for that id). If all objects are present done else query the server get all objects and update the cache.

How to update the cache/queue : If a hit is found the return the worker objects then move all the worker objects which matched to start of the queue and update the address in the map. So in case we query for some id not in the queue/cache then we can add those new objects to start of the queue and remove equal number of objects from end of the queue since they were least recently used.

- nikanjgupta April 16, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

there is no issue of space here. we can store as many objects as we want just to keep the minimal server calls.
Your first map is storing unitId=>starting address of worker object + number of other Workers of same unit Id. What is the use of storing just the number of Worker Objects? How will you get the worker objects of those workers?

Also keeping separate cache for each Id => worker object does not seems efficient as it already said there could be 100 of such different fields by which user wants to query so in that case would you create 100 maps?

- CareerCupUser1 April 16, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

IN a scenario where we are storing all worker objects in cache (millions), adding a few keys corresponding to 100s of ids will not have a lot of adverse effect.

- Tej April 18, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

I would use the following:

public class HeapNode
{
int unit;
int rank;
}
public UnitDetail
{
int queueIdx;
ArrayList<WorkerId> workers;
}
1) HashMap<Integer,UnitDetail> unitWorkers//contains details on each unit (unit number is the key. the value is an object containing the heap node representing that unit along with the list of workers for the unit)
2) Queue<Integer> queue of unit numbers with the most recently queried unit number as the head.

Here's how it will work:
Step 1) If user queries a unit that is not in the map, fetch the workers from the server.
Create a new entry in the hash map for this unit.Otherwise, simply fetch the list corresponding to this key in the hashmap and return the list then proceed to step 2.

Step 2)
For a new entry in the hashmap: If the queue is full, create a new queue with the
new entry's unit number as the head and transfer to it all EXCEPT last element in the existing queue.Update the queueIdx attribute in the hashmap for each transferred unit.
For an existing entry int he hashmap: Take all elements before the queried unit in the queue(refer to queueIdx) and re-insert them into the queue so that they occurr after the queried unit. Update queueIdx values.

Use a similar approach for the Department based Queries.



The department details can also be set up similarly (using a separate max heap and HashMap).

- divm01986 April 18, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

I would use one map - with key WorkerId and Value WorkerObject and one multimap with key as keyType+DeptId/UnitId/any other lookup idEg. if the lookup is based on deptId 1234 then the key would be DEPT1234 and value is a collection of worker ids.

WorkerObkect Map : Key= WorkerId Value=WorkerObject
LookupMultiMap : Key=KeyType+KeyValue Value=Collection of workerIds.

1) When an Id is looked up in the multimap and is not found a new entry is added to the multimap and to the workerobject map.


2) When an id is looked up and found in the multimap , it returns a list of workerIds which are lookup in the workerobject map and the individual objects are returned.

- ming April 19, 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