Google Interview Question: Design a cache with O(1) sear... |

Interview Question

Software Engineer Interview

Design a cache with O(1) search time and delete time.


Interview Answer

2 Answers


Hash table has O(1) search time but it has O(n) delete time.

Interview Candidate on 10 Apr 2014

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 28 Jul 2014

Add Answers or Comments

To comment on this, Sign In or Sign Up.