Google Interview Question for Software Engineer in Tests


Country: United States




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

Keep an array and a map. Map will contain a mapping of value in array to index in the array. Since, ordering of elements doesnt matter, when we want to delete an element, find its index in the map, and at that index, swap the last element present in the array and update its index in the map. Also, decrease the count of elements present in the array. So, it provides random access as these are present in a normal array, insert, delete using map and array (assuming unordered_map in c++)

- codeinfinity November 19, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
3
of 3 vote

Use 2 maps. Use first map (A) for map operations, i.e. key to elements. Use map B to map the array indices to keys int map A. As a result, array operations cost 2 times constant time which is still asymtotically constant.

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

how would you delete by key in this case?

- emb November 15, 2015 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

@emb, good question. The value part of each KVP in map A should also saves the array index. 2 maps should be linked in both directions.

- cdhsiung November 15, 2015 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

An elegant solution !

- Shivam Maharshi January 25, 2016 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

Both, Array and Map provides constant time access to the underline elements.
Truly speaking, a Map may very well be replace of an array at anytime, with index being the keys of the map.

However, if the focus is on exploring the data structures than we can use Tries.
Although, Tries works pretty much like a Map, it has a limitation that keys can only be Strings, which in this case should not be the problem as indices can easily be parsed into Strings.

- coolguy November 14, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

In java there is a data structure called LinkedHashMap which has properties of both map and list.. not sure what the interviewer was looking for..

- rajat.shrivastava.aw November 16, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

A list is not an array. It does not provide constant read time. The LinkedHashMap is an extension of the HashMap class with the added feature of maintaining the order of objects as they are added. It still lacks indexing.

- bpaunescu November 17, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

SBT, AVL and Skip List are the data structures which suitable for this scenario.

- Inapt November 18, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

A HashMap and Binary Search Tree. Each hash map entry will have a key which is a hash value (integer) and the corresponding value will be the associated BST node. "Access" operations (Checking if an element exists or getting an existing element) will be O(1). Modification operations (deletion of an existing element, changing its attribute, insertion) will be O(logN) provided that the tree is balanced, otherwise it can take upto O(N) time where N is the number of elements stored.

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

double mod(double x){
	if(x > 0)
		return x;
	else
		return -1*x;
}

double cubeRoot(double x1, double x2, int x) {
	double epsilon = 0.0001;
	double root = (x1 + x2) / 2;
	double numEstimate = pow(root,3);

	if(mod(numEstimate - x) < epsilon) 
		return root;
	else if(numEstimate > x)
		return cubeRoot(x1, root, x);
	else
		return cubeRoot(root, x2, x);	
}

double computeCubeRoot(int x){
	return cubeRoot(0, x, x);
}

- Anonymous November 14, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

You posted on the wrong question.

- Ray November 15, 2015 | Flag


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