KodeSeeker

/*
Image URL for representation :http://www.darrensunny.me/wp-content/uploads/2014/04/Rain-Water-Trap.png

Algo: From  left  compute the max of the current element and the elements on the left. and store in array : maxLeft[]
From right move left and compute the max of current element and the element on right 
for each element and store in array: maxRight[].

The amount of water above each element is Min(maxleft[i],maxRight[i])-hist[i].

Assumption width of each histogram bar is 1.

KodeSeeker

/**
 * Find the minimum edit distance required to convert a string  s1 to string s2.
 **/
 
 //Approach -dynamic programming. 
 //Complexity O (n^2)
 
public class EditDistance{
 
 public static int[] [] memo;// to track the edit distance so far.

KodeSeeker

/**
 * Assume that the URL's shortened  by the service is limited by INT_MAX.
 * */
 


public class TinyURL
{
    public static int urlID=0; // max number of URL's  shortened by this service. is limited by INT_MAX 
    public static const int  URL_LENGTH=36;

KodeSeeker

/**

User ID  Page ID
A          1
A          2
A          3
B          2
B          3
C          1
B          4

KodeSeeker

/**
 * Idea is to use a bitfield to compactly represent each number
 * Ctci Pg 346.
 * 
 **/
 
 public int missingNumber()
 {
     long numofInts= INTEGER.MAX_VALUE+1;
     boolean[] bitField= new new boolean [numofInts/8];

KodeSeeker

/**
 * Sorting approach
 * Sort each letter from the input.Keep sorted word as the key with a list of strings that are anagrams.
 **/

public void groupAnagrams( String in)
{
    if (str==null)
        return;
    HashMap<String,List<String>> map = new HashMap<String,List<String>>();

KodeSeeker

/**
 * Given a text txt[0..n-1] and a pattern pat[0..m-1], write a function search(char pat[], char txt[]) 
 * that prints all occurrences of pat[] in txt[]. You may assume that n > m. 
 * E.g.
 * txt=  "THIS IS A TEST TEXT"
  *  pat = "TEST"
  Output : Pattern found at index 10
  */
  public int findPattern(String txt, String pat)
  {

KodeSeeker

/**
Algorithm 
Consider input 
in =[3,2,1,0,13,1,1]
min_avg=0;
avg=0;
min_avg_so_far=0;
int i=0;
count =2;
while(i<arr.length)

KodeSeeker

/**
Use Moore's  counting algorithm to find a candidate.
Then check if the  candidate occurs more than 50% of the time.
**/

public int findCandidate(int[] in)
{
  if(in==null)
    return -1;
  

KodeSeeker

/*
 Find median of a stream of running integers.
*/

 // maintain heaps according two rules
  // size of max heap can be 1 or more than size of min heap.
  // max heap = contains the ** smallest** elements in the stream so far.
  // min heap = contains the **largest** elements seen so far.
  /*
  If number of elements seen so far is odd. then the median is the root of the max heap.