Google Interview Question for Software Engineers


Country: United States
Interview Type: Phone Interview




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

We can use hashing to support first 3 operations in Θ(1) time. How to do the 4th operation? The idea is to use a resizable array (ArrayList in Java, vector in C) together with hashing. Resizable arrays support insert in Θ(1) amortized time complexity. To implement getRandom(), we can simply pick a random number from 0 to size-1 (size is number of current elements) and return the element at that index. The hash map stores array values as keys and array indexes as values.

Following are detailed operations.

insert(x)
1) Check if x is already present by doing a hash map lookup.
2) If not present, then insert it at the end of the array.
3) Add in hash table also, x is added as key and last array index as index.

remove(x)
1) Check if x is present by doing a hash map lookup.
2) If present, then find its index and remove it from hash map.
3) Swap the last element with this element in array and remove the last element.
Swapping is done because the last element can be removed in O(1) time.
4) Update index of last element in hash map.

getRandom()
1) Generate a random number from 0 to last index.
2) Return the array element at the randomly generated index.

search(x)
Do a lookup for x in hash map.

- smarthbehl August 21, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
1
of 1 vote

Random access doesn't mean get a random element.. Random access means you can get any element no matter where it is in the strucure.. Like in an array you get the ith element with arr[i]. In a linked list you'd have to traverse the list until you get to the ith element..

- Anonymous August 22, 2015 | Flag
Comment hidden because of low score. Click to expand.
-2
of 2 votes

Which is exactly what the solution smarthbehi proposed does. It picks one element randomly where all the elements have equal probability to be picked.

- teli.vaibhav August 29, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

HashMap

- Anonymous August 21, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

What is the 4th operation?

- infinity August 22, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Insert, Delete, Random, Access
:)

- Joker October 01, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

This question is to general to give the most effective data structure, first we need to ask question like which scenario our data structure is going to be used, is going to be in constant change or is going to be used for search mostly, what about memory requirements (a LL or BST based DS could be more effective), features of the type of objects we are going to store in it.

But based only in the operations described in the question a simple HashMap solve the problem since the order in which the elements are inserted is not important to the rest of the operations, a DS with a re-sizable array solve the problem too since no time complexity was specified.

This is how I would've answered the question in a real interview.

- rchg1988 August 26, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

You need to define your desired operational time and space complexity requirements as there are many data structures (all set data structures) that provide these three fundamental of operations. I expect you were either expected to describe the pros and cons of a few and/or probe the interviewer to refine the requirements before jumping into an answer.

- Dave September 01, 2015 | 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