Google Interview Question
Software Engineer in TestsCountry: United States
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.
@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.
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..
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.
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.
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);
}
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