StartUp Interview Question
Software ArchitectsCountry: India
Interview Type: In-Person
There are 2 ways one implementing Stack and another way using TTL(Time To Live)
-> Using Stack: create a stack Array. let it be size 100. let there be a query which returns the results, then store the result into this Array. Results of diff queries will be stored. suppose if we get the same query, which has result already in Stack, return result from stack and move the Result to the bottom of the stack as it is recent used. So like wise all the reused query results will go to the bottom of stack. Results for the queries which haven't trigged recently , will stay at the top of stack, so can be easily sweeped out of back. But here headache is for each result lot of operations should be done on stack.
-> By using TTL , we will maintain time to each query result. If query again triggers , then we will again start the TTL. So, for every time interval we can flush out the queries whose TTL becomes zero.( means whose result TTL has not restarted.
You have not mentioned a mechanism by which you will search the stack efficiently. When you get a new query, how do you know whether it's already in the stack? If you search the whole stack every time you get a query, it will be O(n) to answer queries.
linkedlist is one way. the head stores the latest and the tail is the oldest. also keep a hashmap for all nodes in the linkedlist. whenever some new query happens, check whether it's in the hashmap, if yes, move it to the head , if not, remove the tail one and bring the new node to head. besides, update the hashmap every time.
We can have a class that contains 2 containers. One is a hash table and the other is a queue. The element in hash table can tell you where it is in queue. When a query is received search for it in hash table. If not found add it to the queue. If found in hash table, we know where it is in Queue. So we can easily remove from (the middle of) the queue and add to it again (at LRU end). This way whole operation is O(n). However it takes slightly more memory.
We can have a stack here.
- DashDash March 18, 2013Whenever we require an item we can search it fro,m the stack and then put it on the top of the stack which is the most recently used.
Least recently used will be the item which is at the bottom of the stack.