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.
To satisfy the third requirement in the question, we need to implement FIFO. why do we need LRU. question does not speak anything about it. On Tue, Jul 6, 2010 at 8:22 PM, Ashish Goel <ashg...@gmail.com> wrote: > no FIFO here, > > the request can be random and hence if the array has say 1,2,3,4,5,6,7 with > 1 being least recently used and 7 got the timeslice junst now, if someone > requests for say 4, the list should become 1,2,4,5,6,7,4 and if the request > is for 8 then it would be 2,3,4,5,6,7,8 > > FIFO is a BAD chois, the average response time is very high > > when someone says that the three operations be in O(1), it is just not > possible, even in hashmap, that is not possible with linked list or array or > whatever implementation > > > > Best Regards > Ashish Goel > "Think positive and find fuel in failure" > +919985813081 > +919966006652 > > > On Tue, Jul 6, 2010 at 8:31 PM, Anand <anandut2...@gmail.com> wrote: > >> @Ashish: why do we need to shift array element when we are using FIFO >> queue. With array also could easily implement FIFO queue with out the >> overhead of shifting the elements. >> >> >> >> On Tue, Jul 6, 2010 at 1:29 AM, Ashish Goel <ashg...@gmail.com> wrote: >> >>> 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<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.
