Google

  www.google.com
Work in HR? Unlock Free Profile

Google Software Engineer Interview Question

"Design a cache with O(1) search time and delete time."
Add Tags [?]
Answer

Part of a Software Engineer Interview Review - one of 3,037 Google Interview Reviews

Answers & Comments

1
of 1
vote
Hash table has O(1) search time but it has O(n) delete time.
- Interview Candidate on Apr 10, 2014
0
of 0
votes
1. keep two arrays - one for status and other for the hashtable
2. set all elements of status array to false
3. while adding elements, first check if status array for same element's hash is true or false. If false, add the element to hashtable array at element's hash. If true, add 1 to element's hash and add the element to hashtable array at this new index.
4. when delete, set hashtable[element's hash] = 0 and status[element's hash] = false;

search O(1) and delete O(1)
- Anonymous on Jul 28, 2014

To comment on this question, Sign In with Facebook or Sign Up

Tags are like keywords that help categorize interview questions that have something in common.