An array is rotated at an unknown position. Find minimum element in the array.

Given a sorted array of distinct elements

int MinimumRotatedArray(int A[], int l, int r)
{
    if( A[l] <= A[r] )
        return l;

while( l <= r )
{
if( l == r ) {return l;}

int mid = Math.floor((l + r) / 2);
if( A[mid] < A[r] )
r = mid;
else
l = mid+1;
}
return -1;
}

Find number of occurrences of input ‘key’ in log N time

Given a sorted array with possible duplicate elements

int first(int A[], int l, int r, int key)
{
    if(r >= l)
    {
        int mid = (l + r)/2;
        if( ( mid == 0 || key > A[mid-1]) && A[mid] == key)
             return mid;
        else if(key > A[mid])
              return first(A, (mid + 1), r, key);
         else
              return first(A, l, (mid -1), key);
     }
     return -1;
}
 
 int last(int A[], int l, int r, int key)
 {
     if(r – l >= 1)
     {
          int mid = (l + r)/2;
          int n = sizeof(A)/sizeof(A[0]);
          if(( mid == n-1 || key < A[mid+1]) && A[mid] == key )
               return mid;
           else if(key < A[mid])
                return last(A, l, (mid -1), key);
           else
                 return last(A, (mid + 1), r, key);      
        }
        return -1;
}

int count(int A[], int key)
{
    int i = first(A, 0, n-1, key);
    int j = last(A, i, n-1, key);  
   
     return j-i+1;       //gives number of occurences of 'key'
}

Given an array of N distinct integers, find floor and ceil value of input ‘key’

Say, A = {-1, 2, 3, 5, 6, 8, 9, 10} and key = 7, we should return 6 as floor value and 8 as ceil value.

For returning floor value

int binarySearch(int arr[], int l, int r, int x)
{
    while( r - l > 1 ){
        int mid = Math.floor((l + r) / 2);
        if (arr[mid] > x) return binarySearch(arr, l, mid, x);
        if (arr[mid] < x) return binarySearch(arr, mid, r, x);
     }
     return arr[l];    
}

For returning ceil value

return arr[r]; 

 

Binary search

Using Recursion

int binarySearch(int arr[], int l, int r, int x)
{
    if (l > r) {return -1;}
    int mid = Math.floor((l + r) / 2);
    if (arr[mid] > x) return binarySearch(arr, l, mid-1, x);
    if (arr[mid] < x) return binarySearch(arr, mid+1, r, x);
    return mid;
}

Using Iterative

int BinarySearch(int A[], int l, int r, int key)
{
    while( r - l > 1 )
    {
       int mid = Math.floor((l + r) / 2);
       if( A[mid] <= key )
            l = mid;
       else
            r = mid;
    }
    if( A[l] == key )
        return l;
    else
        return -1;
}

Leap year algo

function isLeapYear (year):
    if ((year % 4 == 0) && (year % 100 != 0)) || (year % 400 == 0)
        then true
    else false

Runtime concepts

Recurrence tree of T(n) = aT(n/b) + f(n),

• Work done at root is f(n)

• Work done at all leaves is    where c is

• Height of recurrence tree is 

Also note:

 

• O(1): If it doesn’t contain loop, recursion and call to any other non-constant time function

• O(n): If the loop variables is incremented / decremented by a constant amount

• O(n^c): Time complexity of nested loops is equal to the number of times the innermost statement is executed

• O(Logn): If the loop variables is divided / multiplied by a constant amount.

• O(LogLogn): If the loop variables is reduced / increased exponentially by a constant amount.

Master theorem

The master theorem concerns recurrence relations of the form:

• n is the size of the problem.

• a is the number of subproblems in the recursion.

• n/b is the size of each subproblem. (Here it is assumed that all subproblems are essentially the same size.)

• f (n) is the cost of the work done outside the recursive calls.

Case 1

If   

Where  

Then 

Case 2

If   k ≥ 0 and 

Where 

Then 

Case 3

If     where 

and    for some constant and sufficiently large n

Then 

Regex

Awesome site to test and code with regex

http://regex101.com/

Count the number of occurrences of each letter in string

const char *str = "The quick brown fox jumped over the lazy dog.";

int counts[256] = { 0 };
int i;
size_t len = strlen(str);

for (i = 0; i < len; i++) {
counts[(int)(str[i])]++;
}

for (i = 0; i < 256; i++) {
printf(“The %d. character has %d occurrences.\n”, i, counts[i]);
}

Connecting to Oracle using Java JDBC

public class OracleJdbcTest
{
    String driverClass = "oracle.jdbc.driver.OracleDriver";
 
    Connection con;
     
    public void init(FileInputStream fs) throws ClassNotFoundException, SQLException, FileNotFoundException, IOException
    {
        Properties props = new Properties();
        props.load(fs);
        String url = props.getProperty("db.url");
        String userName = props.getProperty("db.user");
        String password = props.getProperty("db.password");
        Class.forName(driverClass);
 
        con=DriverManager.getConnection(url, userName, password);
    }
     
    public void fetch() throws SQLException, IOException
    {
        PreparedStatement ps = con.prepareStatement("select SYSDATE from dual");
        ResultSet rs = ps.executeQuery();
         
        while (rs.next())
        {
            // do the thing you do
        }
        rs.close();
        ps.close();
    }
 
    public static void main(String[] args)
    {
        OracleJdbcTest test = new OracleJdbcTest();
        test.init();
        test.fetch();
    }
}