LRU Cache

Now a days this is most favorite interview question .

1) First try to understand time complexity calculation
     for(int i=0; i < n; i++) {
     }
   
     Time complexity: Big 0(n), you need to go all n elements

2)  for(int i=0 ; i < n; i++ ) {
         for(int j=0;  j < n; j++ ) {
         }
    }

    Time Complexity: each elements n times, then n elements n times
    Big O(n2)
 
     My theory simple : how many nested loops that many square n elements

3) for(int i=0; i < n; i++ ) {
        for(int j=0; j < n; j++) {
          for(int k=0; k < n; k++) {
          }
        }
    }

    how many loops: 3 then Time Complexity: n * n * n = Big O(n3)


LRU Cache is tricky question. Here Time complexity is very important.

In the cache fixed num of slots are assume: 4

1) Initial we will fill the slots with numbers , Assume: 4, 3,2,1
2) Now any one search for 5, 5 is not in the list then it will evict the 1 slot, add the element at top means now 5,4,3,2

   Search for Number in the slot: O(1)
   Deletion of the slot : O(1)
   Insertion of the Slot : O(1)

In the above scenario - deletion at last, addition at front

So double linked list best it will take O(1), if we know the position then it will take O(1) for deletion and insertion

Search : O(1) - HashMap only have that feature

Now we need to combine both datastructures here.



Refer below for good explanation.
https://medium.com/@krishankantsinghal/my-first-blog-on-medium-583159139237