Flipkart Interview Question
SDE-3sCountry: India
Interview Type: In-Person
Hey can't we maintain one heap and one linked list.Heap always contain top 100 purchases in recent time and Linked List has Just the purchases in which recent ones are at the head always.
@Klaus : If someone plans to use single linked list for purchases then, using a Heap needs some more care in order to do Increase-key operation efficiently because to perform Increase-key, one has to know the index of that node. But it can be done, I guess, efficiently by using some map-like data-structure.
Moreover, [ having many linked lists(each for a product) & not having main linked list ] or [ having a single list ] almost takes same space. So, we are not gaining much out of it.
1.) Create Products Object containing {PID,ProductName,List<Timestamp> purchases,LastPurchased}
2.) Maintain a hash/Dictionary with key as PID and value as LinkedListNode<Product> and also maintain a double linked list (like LRU cache) and move the product to the beginning on a purhcase.
So the start of linked list contains the latest purchased product always
3.) To find Top 100 products in last X minutes/X Hours , maintain a heap. Start from the starting of linked list ,go comparing last purhcased timestamp , find number of purchases in last X minutes , create a structure {ProductID, NumberOfPurchases} and insert in max heap with key as number of purchases . Now pick top 100 from heap by calling GetMax of max heap.
- Smarth July 07, 2015