LRU implementation : ~~~~~~~~~~~~~~~~ -Maintain a double linked list which stores LRU items(say 50). -Keep one head and tail pointers of the linked list. -Maintain a hash table which has value of the linked list as key and memory location of that node as value. - When ever hash table doesn't contain the element and # of elements in linked list is less than 50, add that element at head of the linked list and make this new node as head of the linked list. - When the element is hit in hash table, move that element to head of the linked list. - When a new element has come and linked list is full, then move the element at tail end to head and change the value of that node to new element's value and change the key in hash table to this new'y added element's value.
I hope I covered all the cases in LRU. give comments if any. On Thu, Oct 25, 2012 at 3:06 AM, Dave <[email protected]> wrote: > @Ujjwal: Here's an algorithm for problem 2: > > Given a number n, form the prime number factorization of n: > > n = p1^k1 * p2^k2 * ... * pm^km, where the pi are distinct primes and ^ > represents exponentiation. > > If any ki = 1, terminate the factorization and report that n is not a > Trojan number. > > Then calculate gcd(k1,k2,...,km), e.g., by repeated applications of > Euclid's Algorithm. > > Finally, n is a Trojan number if and only if gcd(k1,k2,...,km) = 1. > > Dave > > On Wednesday, October 24, 2012 3:37:28 AM UTC-5, Ujjwal Arora wrote: > >> We had to code 2 questions in 1.30 hr on codechef only. the questions are >> as follow : >> >> 1.) Implement Least Recently Used (LRU) algorithm - a well known >> algorithm of operating systems. >> >> 2.) Find if a given number is Trojan Number. A Trojan number is a number >> which is strong but not a perfect power (m^k). A Strong number is a number >> which has a prime number 'p' its factor and also divisible by p^2 i.e >> divisible by a prime and also by its square. >> Hence, Trojan number is a strong number , which can't be represented as >> m^k. >> > -- > You received this message because you are subscribed to the Google Groups > "Algorithm Geeks" group. > To view this discussion on the web visit > https://groups.google.com/d/msg/algogeeks/-/p3FnJGZAMD4J. > > 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. > -- 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.
