Interpolation search

Interpolation search (sometimes referred to as extrapolation search) is an algorithm for searching for a given key value in an indexed array that has been ordered by the values of the key. It parallels how humans search through a telephone book for a particular name.

On average the interpolation search makes about log(log(n)) comparisons. In the worst case it can make up to O(n).

In each search step it calculates where in the remaining search space the sought item might be, based on the key values at the bounds of the search space and the value of the sought key, usually via a linear interpolation.

CODE

public int interpolationSearch(int[] Array, int key){

int low = 0;
int high = Array.length – 1;
int mid;

while (Array [low] <= key && Array [high] >= key) {

mid = low + (high – low) / (Array[high] – Array[low]) *( key – Array[low]);

if (Array [mid] < key)
low = mid + 1;
else if (Array [mid] > key)
high = mid – 1;
else
return mid;
}

if (Array [low] == key)
return low;
else
return -1; // Not found
}

Semaphore

It is a variable or abstract data type that is used for controlling access, by multiple processes, to a common resource in a parallel programming or a multi user environment.

Semaphores are a useful tool in the prevention of race conditions.

Semaphores which allow an arbitrary resource count are called counting semaphores, while semaphores which are restricted to the values 0 and 1 (or locked/unlocked, unavailable/available) are called binary semaphores.

Runnable

The Runnable interface should be implemented by any class whose instances are intended to be executed by a thread.

A class that implements Runnable can run without subclassing Thread by instantiating a Thread instance and passing itself in as the target.

CODE

class RunnableDemo implements Runnable {
   private Thread t;
   private String threadName;

   RunnableDemo( String name){
       threadName = name;
       System.out.println("Creating " + threadName );
   }
   public void run() {
     System.out.println("Running " + threadName );
     try {
         for(int i = 4; i > 0; i--) {
           System.out.println("Thread: " + threadName + ", " + i);

           // Let the thread sleep for a while.
           Thread.sleep(50);
         }
     } catch (InterruptedException e) {
         System.out.println("Thread " + threadName + " interrupted.");
     }
     System.out.println("Thread " + threadName + " exiting.");
   } 
   public void start ()
   {
     System.out.println("Starting " + threadName );
     if (t == null)
     {
         t = new Thread (this, threadName);
         t.start ();
     }
   }
} 
public class TestThread {
   public static void main(String args[]) {
     RunnableDemo R1 = new RunnableDemo( "Thread-1");
     R1.start();

     RunnableDemo R2 = new RunnableDemo( "Thread-2");
     R2.start();
   }  
}

----------------------------------------------------------------------------------------------

class ThreadDemo extends Thread {
   private Thread t;
   private String threadName;

   ThreadDemo( String name){
       threadName = name;
       System.out.println("Creating " +  threadName );
   }
   public void run() {
      System.out.println("Running " +  threadName );
      try {
         for(int i = 4; i > 0; i--) {
            System.out.println("Thread: " + threadName + ", " + i);
            // Let the thread sleep for a while.
            Thread.sleep(50);
         }
     } catch (InterruptedException e) {
         System.out.println("Thread " +  threadName + " interrupted.");
     }
     System.out.println("Thread " +  threadName + " exiting.");
   }

   public void start ()
   {
      System.out.println("Starting " +  threadName );
      if (t == null)
      {
         t = new Thread (this, threadName);
         t.start ();
      }
   }

}

public class TestThread {
   public static void main(String args[]) {
      ThreadDemo T1 = new ThreadDemo( "Thread-1");
      T1.start(); 

      ThreadDemo T2 = new ThreadDemo( "Thread-2");
      T2.start();
   }   
}

 

What happens when you open a website in a browser

1. browser checks cache; if requested object is in cache and is fresh, skip to #9
2. browser asks OS for server’s IP address
3. OS makes a DNS lookup and replies the IP address to the browser
4. browser opens a TCP connection to server (this step is much more complex with HTTPS)
5. browser sends the HTTP request through TCP connection
6. browser receives HTTP response and may close the TCP connection, or reuse it for another request
7. browser checks if the response is a redirect (3xx result status codes), authorization request (401), error (4xx and 5xx), etc.; these are handled differently from normal responses (2xx)
8. if cacheable, response is stored in cache
9. browser decodes response (e.g. if it’s gzipped)
10. browser determines what to do with response (e.g. is it a HTML page, is it an image, is it a sound clip?)
11. browser renders response, or offers a download dialog for unrecognized types

Structure vs Class

Structure	Class
Structures are value types	Classes are reference types
Structure couldn’t be null	Class can be null
Structure couldn’t have a destructor	Class have destructor
Structure can’t be abstract	Class can be abstract