let me put it this way, say for last n times you made the same request, how should the cache look like?
Does the browser keep history as a stack only? simplest design is to use stack and then parse most commonly used sites, but you would like this to be preprocessed rather than finding at run time Best Regards Ashish Goel "Think positive and find fuel in failure" +919985813081 +919966006652 On Wed, Jul 7, 2010 at 9:54 AM, Anand <[email protected]> wrote: > 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 <[email protected]> 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 <[email protected]> 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 <[email protected]> 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 <[email protected]> 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 <[email protected]> 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 <[email protected]>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 [email protected]. >>>>>>> To unsubscribe from this group, send email to >>>>>>> [email protected]<algogeeks%[email protected]> >>>>>>> . >>>>>>> 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 [email protected]. >>>>>> To unsubscribe from this group, send email to >>>>>> [email protected]<algogeeks%[email protected]> >>>>>> . >>>>>> 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 [email protected]. >>>>> To unsubscribe from this group, send email to >>>>> [email protected]<algogeeks%[email protected]> >>>>> . >>>>> 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 [email protected]. >>>> To unsubscribe from this group, send email to >>>> [email protected]<algogeeks%[email protected]> >>>> . >>>> 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 [email protected]. >>> To unsubscribe from this group, send email to >>> [email protected]<algogeeks%[email protected]> >>> . >>> 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 [email protected]. >> To unsubscribe from this group, send email to >> [email protected]<algogeeks%[email protected]> >> . >> 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 [email protected]. > To unsubscribe from this group, send email to > [email protected]<algogeeks%[email protected]> > . > 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 [email protected]. To unsubscribe from this group, send email to [email protected]. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
