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));
    }