the linked lists has been used, but the key idea is to implement LRU algo so if you use associate a timestamp with each request, and use that for prioritising the the bucket queue, or use a simple front tail mechnism to remove from front and push at the end as soon as a request is made, that will work
implement it through arrays would imply that the element shifting would be cumbersome and time consuming(eg say 5 elements for a particular bucket and the middle one is accesses, now it should go at end, but with array implementation 4th and 5th will need to be pushed up and 3rd to be pushed down) so under such conditions, a DLL is the best Best Regards Ashish Goel "Think positive and find fuel in failure" +919985813081 +919966006652 On Tue, Jul 6, 2010 at 10:36 AM, Anand <anandut2...@gmail.com> wrote: > @topojoy. > > Why do we need linked list. We are use an array of struct which stores the > response and request information. > request identifier can be hashed to generate a key which can be used as an > index to the array of structures. > > We don't need linked list as we do not need to parse the request and > response. For indexing we are any way using hashing. > > > > On Sun, Jul 4, 2010 at 11:49 PM, Satya <satya...@gmail.com> wrote: > >> See below links. Most of web applications(facebook,classmates) use >> memcached to speed up their sites. >> memcached uses hashing. >> >> http://memcached.org/ >> http://www.facebook.com/note.php?note_id=39391378919 >> <http://memcached.org/>http://en.wikipedia.org/wiki/Memcached >> ......... >> Satya >> >> >> >> On Fri, Jul 2, 2010 at 11:46 PM, sharad <sharad20073...@gmail.com> wrote: >> >>> [1] Design a layer in front of a system which cache the last n >>> requests and the responses to them from the system. >>> what data structure would you use to implement the cache in the later >>> to support following operations. >>> [a] When a request comes look it up in the cache and if it hits then >>> return the response from here and do not pass the request to the >>> system >>> [b] If the request is not found in the cache then pass it on to the >>> system >>> [c] Since cache can only store the last n requests, Insert the n+1th >>> request in the cache and delete one of the older requests from the >>> cache >>> The objective is to achieve all the three operations in O(1). >>> >>> -- >>> You received this message because you are subscribed to the Google Groups >>> "Algorithm Geeks" group. >>> To post to this group, send email to algoge...@googlegroups.com. >>> To unsubscribe from this group, send email to >>> algogeeks+unsubscr...@googlegroups.com<algogeeks%2bunsubscr...@googlegroups.com> >>> . >>> For more options, visit this group at >>> http://groups.google.com/group/algogeeks?hl=en. >>> >>> >> -- >> You received this message because you are subscribed to the Google Groups >> "Algorithm Geeks" group. >> To post to this group, send email to algoge...@googlegroups.com. >> To unsubscribe from this group, send email to >> algogeeks+unsubscr...@googlegroups.com<algogeeks%2bunsubscr...@googlegroups.com> >> . >> For more options, visit this group at >> http://groups.google.com/group/algogeeks?hl=en. >> > > -- > You received this message because you are subscribed to the Google Groups > "Algorithm Geeks" group. > To post to this group, send email to algoge...@googlegroups.com. > To unsubscribe from this group, send email to > algogeeks+unsubscr...@googlegroups.com<algogeeks%2bunsubscr...@googlegroups.com> > . > For more options, visit this group at > http://groups.google.com/group/algogeeks?hl=en. > -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
