LFU Cache

http://dhruvbird.com/lfu.pdf
http://javaopensourcecode.blogspot.in/2012/06/lfu-cache.html

search element in sorted rotated array

http://www.geeksforgeeks.org/search-an-element-in-a-sorted-and-pivoted-array/

Leetcode:z

int rotatedBinarySearch(int A[], int N, int key) {
 int L = 0;
 int R = N - 1;

 while (L <= R) {
  int M = L + ((R - L) / 2);
  if (A[M] == key)
   return M;

  if (A[L] <= A[M]) {
   if (A[L] <= key && key < A[M])
    R = M - 1;
   else
    L = M + 1;
  }
  else {
   if (A[M] < key && key <= A[R])
    L = M + 1;
   else
    R = M - 1;
  }
 }
 return -1;
}

Check whether array is in sorted order with recursion.

int isArrayInSortedOrder(int A[], int n, int index){
if(n == 1){
return 1;
}

if(index == n -2){  //for last 2 elements example: 6 elements, index = 4;=> 4==(6-2)=>true; A[4]<A[5]; 
return A[index] < A[index + 1];
}

if(A[index] > A[index + 1]){
return 0;
}

return isArrayInSortedOrder(A, n, index + 1);
}

Time Complexity: O(n)
Space Complexity: O(n) for stack space



Otherway:

int isArrayInSortedOrder(int A[],int N){
if(N == 1)return 1;
return (A[N-1]<A[N-2])?0:isArrayInSortedOrder(A,N-1);

}

Concating 2 numbers without using java libraries

public static long concatenateNumbers(long x, long y) {
        long temp = y;
        do {
            temp = temp / 10;
            x = x * 10;
        } while (temp > 0);
        return (x + y);
    }

Example: 230, 400 => 230400


How does this work?
x = 230; y =400
temp  = y; => 400
case 1: temp = 400/10 = 40 ; x = 230*10 = 2300

case 2: temp =40> 0; 40/10=4; x = 2300*10 = 23000

case 3: temp =4> 0; 4/10=0; x = 23000*10 = 230000

case 2: temp =0> 0 ; //false.
x + y =>  230000+400= 230400



Why do.. while ? why can't while..do ??
Example: 230, 0= > 2300
If i use while(temp> 0) // here itself it will fail, since temp = 0;

How do with java libraries ?

public static long concatenateNumbers(long x, long y) {
            retrun Long.parseLong( Long.toString(x)+Long.toString(y));
    }

Search in a row wise and column wise sorted matrix

Given an n x n matrix, where every row and column is sorted in increasing order. Given a number x, how to decide whether this x is in the matrix. The designed algorithm should have linear time complexity.

1) Start with top right element
2) Loop: compare this element e with x
….i) if they are equal then return its position
…ii) e < x then move it to down (if out of bound of matrix then break return false)
..iii) e > x then move it to left (if out of bound of matrix then break return false)
3) repeat the i), ii) and iii) till you find element or returned false

Implementation:

/* Searches the element x in mat[][]. If the element is found,     then prints its position and returns true, otherwise prints     "not found" and returns false */ boolean search(int mat[4][4], int n, int x) {    int i = 0, j = n-1;  //set indexes for top right element //here n=4; j=3(n-1)    while ( i < n && j >= 0 ) //i=>row; j=> coloumn    {       if ( mat[i][j] == x )       {          System.out.printf("\n Found at %d, %d", i, j);          return true;       }       if ( mat[i][j] > x )         j--; //decrement column value       else //  if mat[i][j] < x         i++; //increment row value    }    System.out.printf("\n Element not found");    return false;  // if ( i==n || j== -1 ) } // driver program to test above function main() {   int mat[4][4] = { {10, 20, 30, 40},                     {15, 25, 35, 45},                     {27, 29, 37, 48},                     {32, 33, 39, 50},                   };   boolean isFound = search(mat, 4, 29);//want to find 29 in the matrix       }

Time Complexity: O(n)

The above approach will also work for m x n matrix (not only for n x n). Complexity would be O(m + n).

Why i have started with right most element ?
Imagine, if you start from left most, and we wanted to search for element '15', 15 is greater than current element '10, now which direction will go ? in the column also values are greater than 10 and row also values greater than 10.Confusion right ?
Now, let's start with right, when you start with element 40, based on the current value you can take exact call in which direction you can go, since below values, means, row values greater than 40 and columns towards from right to left are lesser than 40, this will save the no.of iterations. Isn't it?

Source: http://www.geeksforgeeks.org/search-in-row-wise-and-column-wise-sorted-matrix/