View All num of num See all Photos Google www.google.com Engaged Employer Overview Reviews Salaries Interviews Jobs Photos Benefits 3.2k Reviews 11k Salaries 3.9k Interviews Follow Add Review or Salary Follow Add Review or Salary Interview Question Software Engineer Interview Google Design a cache with O(1) search time and delete time. Tags: See more , See less 8 Answer Add Tags Answer Interview Answer 2 Answers ▲ 1 ▼ Hash table has O(1) search time but it has O(n) delete time. Interview Candidate on Apr 10, 2014 ▲ 0 ▼ 1. keep two arrays - one for status and other for the hashtable2. set all elements of status array to false3. 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 Interviews > Software Engineer > Google Add Answers or Comments To comment on this, Sign In or Sign Up.