Amazon Interview Question
Software Engineer / DevelopersCountry: CANADA
Interview Type: In-Person
Like kr.neerav said, a Stack would be a good fit I suppose, so long as you decide that you'll keep N items, and make sure that N doesn't grow beyond N. Specifically, when a product is accessed, you would add it to the stack, and then remove the last element to keep the size in check.
A database is really what seems appropriate. Have a last accessed time for each product, and then you can quickly query that information.
What would be bad with the stack approach, is that you'd blow it out really fast. In other words, if you are hitting this millions of times per second, you'll probably end up thrashing the mutex.
So, if you had a big enough min-heap, you could store everything in that, with a HashMap as a lookup data structure, and use the time-accessed as your heap comparison. Then just pull off the N min values when you need the information.
Lots of approaches you can talk about here, and the tradeoffs between them all. Database would utilize existing data structures and capabilities. The information would already be cached from the database or disk since they were presented to the user, so data locality is good.
How is a stack a good solution? Isn't a Stack LIFO? If we are adding the most recently accessed product on top of the stack, how can we remove the least accessed element from the bottom of the stack in O(1) time? What happens if the customer is accessing a product that is already in the stack?(do we add the product again?). I must be missing some detail
Say, Rest api is like /user/recent_items?userid=[id]
I would keep the hash table of items that were checked out by all users.
Due to the memory constraint, this hash table only keeps certain number of items. To make sure the hash table would keep most recently check items by users, I would like the LRU list to keep the item ids.
This will make sure only most recently view items would stay in the cache.
I guess the data structure stack fits this requirement well.
- kr.neerav April 08, 2014