Index

1. Linked List implementation in Java
2. Other Linked List Problems
     a. Reverse a Linked List
     b. Get Nth element from the end of a linked list.
     c. Check if a linked list is a palindrome  
3. Queue implementation in Java using Linked List.
4. Stack implementation in Java using Linked List.
5. Binary Search Tree implementation in Java
6. Other Binary Tree Problems
    a. Compare two binary trees
    b. Convert a binary tree to a doubly linked list
    c. Build binary tree from preorder traversal and inorder traversal
    d. Build NL tree from preorder traversal
    e. Convert each level of a binary tree into a linked list
    f. Non recursive tree traversal using stack
    g. Descending order traversal of binary search tree
7. Hash Table implementation using separate chaining 
8. Other Problems
    a. Multiple Producer Consumer Problem
    b. Pattern Matching
    c. Find if a number is divisible by 3
    d. Calculate x^m in O(log m) time
    e. De duplicate array in O(n) time
    f. Reverse factorial
   g. Shuffle a pack of 52 cards
   h. Find the intersection of 2 arrays
   i. Find duplicate elements in a array
  j. Set bit count

Largest Sum contiguous subarray

 Problem . 

 An array can contains negative and positive numbers. You have to find the sub-array where the sum of all numbers in the sub array is maximum.

In the above example the largest sum in a sub-array is 14.



Solution.


The crux of the logic is the fact that, as you read from left, if a subset sums up to a -ve number, you can discard it. It won't be able to contribute anything to the numbers following it.

You need to keep track of two sums. First, the largest sum found so far from beginning (maxSoFar ) and another sum  for the sub-array currently being considered (currentSubArrayMax ). Whenever
sum of the current sub-array is more than the global max assign maxSoFar = currentSubArrayMax.


public static int maxSumSubArray (int[] numbers)
{


int currentSubArrayMax = 0;
int maxSoFar = 0;

for (int i = 0; i < numbers.length; i++)
{
currentSubArrayMax += numbers[i];



//if a subset adds up to a -ve number, discard it
if (currentSubArrayMax  < 0)
currentSubArrayMax = 0;

//set the new maximum
if (maxSoFar < currentSubArrayMax)
maxSoFar = currentSubArrayMax;
}

return maxSoFar ;
}

Remove consecutive same character substring repeatedly

Problem: This program doesn't like consecutive characters in a string. If it find consecutive characters them it bombs them and generate a substring. The largest consecutive character substring is bombed first.

For example, the input "abcccddbcaab" will be bombed in each step to get he following substrings

Input: abcccddbcaab
Step 1: abddbcaab
Step 2: abbcaab
Step 3: acaab
Step 4: acb





//To remove the largest consecutive same character substring repeatedly until there's no such substring

public class Bomber {

public static void main(String args[])
{
      String temp2;
               temp2="abcccddbcaab";
while(true)
{
    System.out.println(temp2);
   temp2=bomb(temp2);
 
   if(temp2==null)
    break;
}

}


//Returns the string after removing the largest consecutive same character substring
public static String bomb(String str)
{

int startMax=-1,endMax=-1;
int globalMax=0,localMax=0;

int start=0,end=0;
for(int i=0;i<=str.length()-2;)
{

if(str.charAt(i)==str.charAt(i+1))
{
start=i;localMax=0;
while(str.charAt(i)==str.charAt(i+1))
{
localMax++;
i++;

if(i==str.length()-1)
break;
}

end=start+localMax;
if(localMax>globalMax)
{
globalMax=localMax;
startMax=start;
endMax=end;
}

}
else
{
i++;
}
}

if(globalMax>0)
return str.substring(0,startMax) + str.substring(endMax+1,str.length());
else //No bombing happened in this method call. So we can stop bombing the string
return null;
}

}

Sort an array having 0,1,2 without counting

1.Use 3 pointers low,mid & hi.
2.low will point to first element from left which is not 0
3. hi will point to first element from right which is not 2
4.low will not point to 2, except when low==mid
5.mid will move from 0 to hi and if it is 2, moves it to hi
and if it is 1 moves it to low.


public int[] group012(int[]arr)
{
int low=0,mid=0,hi=arr.length-1,temp=0;

while(mid<=hi)
{


switch(arr[mid])
{
case 0:
arr[mid++]=arr[low];
arr[low++]=0;
break;
case 1:
mid++;
break;
case 2:
arr[mid]=arr[hi];
arr[hi--]=2;
}

}

return arr;
}

To find nth element from the end in a linked list

Use two pointers.
Start the second pointer when the first pointer reaches nth element.

Middle of a linked list in one traversal

Problem

       Find the middle element of a linked list, with just one traversal.


Solution.

Use 1 slow pointer and one fast pointer.
When the fast pointer reaches the end,
slow pointer will be at the middle

Sieve of Eratosthenes

To find all the prime numbers less than or equal to a given integer n:
1. Create a list of consecutive integers from two to n: (2, 3, 4, ..., n).
2. Initially, let p equal 2, the first prime number.
3. Starting from p, count up by p and cross out thus found numbers in the list (which will be 2p,
3p, 4p, etc.).
4. Find the first number not yet crossed out after p; let p now equal this number (which is the
next prime).
5. Repeat steps 3 and 4 until p is greater than n.
All the numbers in the list which are not crossed out are prime.