Hello all, Just wanted to share my recent experience for google phone screen round

Time: 45 minutes
Question: i dont remember exact wording but the structure is as follows:

Q) Design a system/data structure to given the user Top N Most Recently Searched Items

My thought process:

1. After listening to TopN i said we can used Heap, they hinted/clarified it is "recently searched and not frequently"
2. So then i thought more and got the idea of ordered dictionary based on 146. LRU Cache

there is a max size n, and the user can search something

**for the search -> **

1. we have to return the top N elements from the dictionary

**for the insert -> **

1. you can update the key:value and move to one end for the frequency.
2. if it is a new key, check len + 1 > n size and if it goes oversize -> pop element and then insert new one (maintain the ordering)

was asked followups questions like

1. time and space complexity of approach 1
2. if you dont use ordered dict then how would you solve it?
   * i suggested -> dictionary + linked list [ with prev and next pointers], dictionary for key = search item and values for linked list node item
   * insert and one end
   * remove at other end
   * if duplicate key -> move to the insert end
   * all 3 requireing to play with prev and next pointers

hope this helps. I will try to answer questions in the comments as best possible.