@anand very true... i also realized after writing it. Only a hashtable would do.
but i have another qs in mind...perfect hash functions are built on an expected probability of collition. Even if we do rehashing, that also does not give an upper bound on the number of times we need to rehash. But this hashtable also has a property like a FIFO queue which says 1st element will go out when the n+1th one comes in. Can we utilize that to give an amortized O(1) worst case bound? 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. > -- Topo. There are days when solitude is a heady wine that intoxicates you with freedom, others when it is a bitter tonic, and still others when it is a poison that makes you beat your head against the wall. ~Colette -- 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.
