Data Structures and Algorithms

Sort an array having 0,1,2 without counting

2011-04-21T02:49:00.000-07:00

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

Width of a tree

2011-04-15T00:02:00.001-07:00

getMaxWidth(tree)
maxWdth = 0
for i = 1 to height(tree)
width = getWidth(tree, i);
if(width > maxWdth)
maxWdth = width
return width

/*Function to get width of a given level */
getWidth(tree, level)
if tree is NULL then return 0;
if level is 1, then return 1;
else if level greater than 1, then
return getWidth(tree->left, level-1) +
getWidth(tree->right, level-1);

To find nth element from the end in a linked list

2011-04-14T10:37:00.001-07:00

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

Middle of a linked list in one traversal

2011-04-14T10:36:00.001-07:00

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

2011-04-14T10:30:00.000-07:00

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.

Array Matching

2011-04-14T10:11:00.001-07:00

a. Given two integer arrays and the size of each array.
b. Determine if arrays match.
c. Order of elements does not matter.
d. Number of occurrences does matter.

Shortcut:
sum=sum of all elements in array1
prod=product of all elements in array1
If this matches with that of array2, the arrays are matching.
(0 can not be present in the array)

Selection Algorithm

2011-04-14T09:47:00.001-07:00

To find the kth smallest element

Nearest Points from origin

2011-04-14T09:36:00.000-07:00

Given set of n points (Xi, Yi), write a function to find k nearest points from origin.

Use the selection algorithm to find the kth minimum element ,this takes o(n) time. After finding the kth minimum element, iterate over the array to find all the elements less than the kth minimum element. Overall complexity is o(n).

Queue using Stack

2011-04-14T06:22:00.001-07:00

Enqueue():
Pop() all elements from StackA to StackB one by one - O(n)
Push() new element in StackA, so it stays at the bottom- O(1).
Pop() all elements from StackB back to StackA - O(n)
So, enqueue is O(n).

Dequeue():
Just Pop().
O(1)

Find the inorder successor of all nodes

2011-04-14T06:00:00.001-07:00

Store the nodes to an array.
For each element, tne next element is the inorder successor.

Find grand parent pointer for each node

2011-04-14T04:32:00.001-07:00

All possible bracket combinations

2011-04-14T04:20:00.001-07:00

How can we generate all possibilities on braces ?
N value has given to us and we have to generate all possibilities.
**Examples:**
1) if N == 1, then only one possibility () .
2) if N==2, then possibilities are (()), ()()
3) if N==3, then possibilities are ((())), (())(),()()(), ()(()) ...
Note: left and right braces should match. I mean )( is INVALID for the N==1

The below recursion tree shows the flow:

public static void allValidBrackets(int n, int open, int closed, String str) {

if (closed == n) {
System.out.println(str);
return;
}

if (open < n) {
allValidBrackets(n, open+1, closed, str + "{");
}

if (closed < open) {
allValidBrackets(n, open, closed+1, str + "}");
}
}

Cycle detection in a directed graph

2011-04-14T04:05:00.001-07:00

alternate merge two linked lists

2011-04-14T04:04:00.000-07:00

Recursive Solution:
Consider two lists a & b
Merge the list from a.next with b
Attach the merged list to a.

Rotate n elements in an array

2011-04-14T03:56:00.000-07:00

Sol:
1. Reverse 0..k
2. Reverse k+1 to N
3. Reverse the entire array.

//To reverse elements from i to j (0 to n-1)

public int[] reverseArray(int[]a, int i, int j)
{
int temp=0;
while(i<j)
{
temp=a[i];
a[i]=a[j];
a[j]=temp;
i++;
j--;
}
return a;

}

Repeating element

2011-04-14T03:05:00.000-07:00

In an array of size n, n/2 elements are unique and one element is repeated n/2 times. How to find the repeating number using least number of comparisons.

Solution:
Compare every element with the next element.
If at any point they are equal, return that element.
Compare 1st element with 3rd element
If they are equal, return that element
Compare 2nd and 4th element if they are equal, return that element.

Sum of elements

2011-04-14T02:56:00.001-07:00

Write a function that takes an array of five integers, each of which is between 1 and 10, and returns the number of combinations of those integers that sum to 15. For example, calling the function with the array [1, 2, 3, 4, 5] should return 1, while calling it with [5, 5, 10, 2, 3] should return 4 (5 + 10, 5 + 10, 5 + 5 + 2 + 3, 10 + 2 + 3). You may assume that the input has already been validated.

Path in a tree sums up to N

2011-04-14T02:28:00.001-07:00

you are given a bst where each node has a int value , parent pointer , and left and right pointers , write a function to find a path with a given sum value. Path can go from left subtree tree , include root and go to right tree as well . we need to find these paths also .

Next smaller in array

2011-04-14T02:17:00.000-07:00

For each number, find the next smaller number in the array. If next smaller number does not exists, put 0.
Eg.
Input: 1 5 7 6 3 1 6 2 9 2 7
Output: 0 3 6 3 1 0 2 0 2 0 0

Path in binary tree

2011-04-14T02:03:00.001-07:00

There is a binary tree(Not a BST) in which you are given three nodes x,y,z .Write a function which finds whether y lies in the path b/w x
and z.
Assume z is a descedant of x, then y need to satisfy two conditions:
(1) y need to be ancester of z
(2) y need to be descendant of x

Determine all non concentric palindromes in a String

2011-04-14T01:37:00.000-07:00

In m"ala"yalam is a non-concentric palindrome where as malayalam, alayala, aya are concentric palindromes.

Solution:
For each i in the string
Find the largest palindrome having i as the center

Fibonacci Series

2011-04-14T00:07:00.001-07:00

1. Recursive routine to return nth fibonacci number
2. Non recursive routine to print first n fibonacci numbers
3. Recursive routine to print first n fibonacci numbers

Solution 3.(Without using static variable)
void recursiveFibonacci(int count, int i, int j)
{
System.out.println(i);
recursiveFibonacci(count-1, j, i+j);
}

Finding pairs

2011-04-13T23:56:00.001-07:00

Two integer arrays, write a function to get pairs of number
Ex:
input: [2,5,6,8,10,2,3,5] & [4,7,3,5,2,10,2,4] output:[2,2,3,5,10]
input: [2,2,2,3,4,5,6,7] & [2,2,5,5,7,10] output: [2,2,5,7]

Sol.
1. Sort the smaller array.
2. Use a pointer on the unsorted array to search from beginng to end.

Run length encoding

2011-04-13T23:47:00.001-07:00

Word count Program

2011-04-13T23:44:00.001-07:00

=number of white spaces+1

Find the center of a linked list

2011-04-13T23:24:00.000-07:00

Sol 1:
1. scan the list to compute the length
2. scan again to find the median

Sol2:
1. Take two pointers, slow and fast, both pointing to head of list
2. Now move slow point node node next and fast pointer two node next
3. Keep moving until fast pointer reaches to END of list OR 2nd last node (depends on node count in list is odd or even), at this point, slow pointer is at the center of list.

Sort with 2 stacks and a variable

2011-04-13T23:16:00.000-07:00

2 stacks are given, one is full of numbers and other in empty, one integer variable is given, fill the 2nd stack with numbers in ascending order with space and time constraints.
Solution:
1)Pop the elements from stack1 and push them to stack2. While popping find out the max element in the stack1.
2) Keep the max element in the temp variable.

3) Pop all elements in stack2 and push to stack1 except max element.
4) Now Push max element(temp) into stack2 and keep track of no:of max elements pushed into stack2, so that in next rounds, you don't pop the max elements pushed already pushed to stack2.
5) At the end, stack1 will be empty and stack2 contains the elements in increasing order.

Median of two sorted arrays

2011-04-13T11:10:00.001-07:00

Pairing

2011-04-13T10:51:00.000-07:00

Give an unsorted array of integers A and and an integer I, find out if any two members of A add up to I.

For example:
A = < 3, 25, 9, 15>
I = 12 returns true
but I = 19 returns false.

Can you find the answer in O(n*log(n)) time?
Can you find the answer in O(n) time?

O(n):
-Create array B by subtracting A[i] from I for each i
-If B[i] exists in A return true.

Reverse the words in a string.

2011-04-13T10:27:00.000-07:00

Implement BigInteger

2011-04-13T07:10:00.001-07:00

write a function to find out the factorial of a number. it should also work for large numbers like 100!

Deleting current node in a singly linked list

2011-04-13T07:02:00.001-07:00

Given a singly linked list with a pointer p pointing to some node(not the first or last node), how will you delete that node? You have no access to the head of the node

Solution:

Copy next node to current node and delete next node

Merge Array

2011-04-13T06:48:00.001-07:00

Two sorted arrays A[X] and B[Y+X]. in B array contains Y sorted elements and B can accommodate A[] X elements.

W.A.P to Merge two arrays and store resultant in B[] array.

Solution:
Merge A and B from back to front

Tree Mirror Image

2011-04-13T05:47:00.001-07:00

Check if the left subtree is a mirror image of the right subtree.

Solution 1:
Do an inorder traversal. If result is a pallindrom then symmetric else not symmetric

Solution 2:
A solution that may work is - Preorder is reverse to its postorder

most frequent character

2011-04-13T05:13:00.001-07:00

Given an array of characters (not sorted), how do you find the most frequent character?

Given a binary search tree find the its least depth.

2011-04-13T05:11:00.001-07:00

LRU implementation

2011-04-13T04:47:00.001-07:00

Use a Doubly Linked list + Hashtable, similar to the implementation of LinkedHAshMap in Java.
The Hash table will point to a node in the linked list.
Every time a page block, n, is accessed,
  Go to the hashtable with n
  Get the node pointer
  Bring that node to the head of the doubly linked list

Implementing a variable number of loops

2011-04-13T04:29:00.001-07:00

Find out the first non-repeating character in a given input string

2011-04-13T03:18:00.001-07:00

Use a count sort based approach.

Check if a number is power of 2

2011-04-13T01:33:00.001-07:00

public boolean isPowerOf2(int num)
{
if((num&(num-1))==0 && num>0)
return true;
else
return false;
}

Pairing

2011-04-13T01:04:00.001-07:00

Given an array of size 2N, such that its elements are as follows:

{a1,a2,a3,...,an,b1,b2,b3...,bn}

You have to rearrange this array, without using any extra array such that resulting array would be:

{a1,b1,a2,b2,...,an,bn}

1. Swap a2,b1 ; a4,b3...so that pairs a1b1,a3b3,a2b2,a4b4 are created.
2. Now swap the pairs a3b3 with a2b2

Count leaf and non-leaf

2011-04-12T10:07:00.001-07:00

Using recursion return the number of leaf nodes and non leaf nodes from a single method without any global variables for a given BST?

reverse pair of elements in a linked list

2011-04-12T10:05:00.001-07:00

Lowest common ancestor in binary tree

2011-04-12T09:51:00.001-07:00

Given a binary search tree and 2 values find the lowest common ancestor.

The main idea of the solution is — While traversing Binary Search Tree from top to bottom, the first node n we encounter with value between n1 and n2, i.e., n1 < n < n2 is the Lowest or Least Common Ancestor(LCA) of n1 and n2 (where n1 < n2). So just traverse the BST in pre-order, if you find a node with value in between n1 and n2 then n is the LCA, if it's value is greater than both n1 and n2 then our LCA lies on left side of the node, if it's value is smaller than both n1 and n2 then LCA lies on right side

Find kth largest integer from an unsorted array of integers. Provide O(n) algorithm

2011-04-12T07:20:00.001-07:00

Merge two sorted linked lists

2011-04-12T07:19:00.001-07:00

Stack - getMin() in O(1)

2011-04-12T07:18:00.001-07:00

Use two stacks, s1 and s2.
Push: Always push in s2, push in s1 too if value is less than top.
Pop:Pop from s2, if popped value is equal to top of s1, pop from s1 too.
Min: Top of s1.

Write A Program to Remove Duplicates from BST

2011-04-12T07:09:00.001-07:00

Find the hight of a tree

2011-04-12T07:08:00.000-07:00

Recursive solution:

Termination condition : treenode==null

1. Find the height of left subtree
2. Find the height of the right sub tree

if height of left subtree is larger
height=height of left subtree +1
else
height=height of right subtree +1

Integer Palindrome

2011-04-12T07:00:00.001-07:00

given an integer. Check whether its binary equivalent is a palindrome or not

Find Gap

2011-04-12T06:52:00.001-07:00

Given an unsorted array of numbers. Find if the array consists of consecutive numbers after sorting. Do this in linear time.

Example 1: If array has 5,2,3,1,4
after sorting we get 1,2,3,4,5 which represents consecutive numbers

Counter Example:
If the array has 34,23,52,12,3 after sorting we get 3,12,23,34,52 which are not consecutive

Find first n sorted elements

2011-04-12T06:49:00.001-07:00

Describe an algorithm to find the largest 1 million numbers in 1 billion numbers. Assume
that the computer memory can hold all one billion numbers

Swap children of a tree

2011-04-12T06:41:00.001-07:00

write a program that implements a function Swap_Tree() that takes a binary tree and swaps left and the right children of every node .

Median of a stream

2011-04-12T06:38:00.001-07:00

Numbers are randomly generated and passed to a method. Write a program to find and maintain the median value as new values are generated.

Write code to check whether given tree is BST or not

2011-04-12T06:26:00.000-07:00

Write code to check whether given tree is BST or not. Time O(n) and space O(1)

B Tree

2011-04-12T06:21:00.001-07:00

AVL Tree

2011-04-12T06:20:00.001-07:00

Copy Doubly Linked List

2011-04-12T06:19:00.003-07:00

The head pointer of a doubly linked list points to a random node.
Copy the DLL by traversal the nodes just once.

Binary Search

2011-04-12T05:56:00.002-07:00

public int binarySearch(int[]a,int key)
{
int low,mid,high;

low=0;
high=a.length;
mid=high/2;

while(low<=high) { if(a[mid]>key)
{
high=mid-1;
mid=(low+high)/2;
}
else if(a[mid] {
low=mid+1;
mid=(low+high)/2;
}
else
return mid;
}

return -1;

}

Searching in an Up Down Array

2011-04-12T05:53:00.001-07:00

There is an array and the distance between any two consequent
elements is one(+1 or -1) and given a number. You have to check whether the
number is in array or not with minimum complexity

Missing and Duplicated

2011-04-12T05:09:00.001-07:00

I have a array which has numbers from 1 to n one number is missing and one number is duplicated. find those in O(n)

Recursion to iteration

2011-04-12T04:41:00.000-07:00

/recursive
void f()
{
if(cond == false)
return;
f();
g();
}
//iterative

public void iterative_f() {
int count = 0;
while (cond == false)
{
count++;
}

while(count > 0)
{
g();
count--;
}

Find an element in a partially rotated sorted array in O(log n)

2011-04-12T04:17:00.001-07:00

O(1) Insert, delete and Get

2011-04-12T04:03:00.001-07:00

Design a Data Structure with following operations
1.Insert(X) -> insert X if X not present
2.Delete(X) -> delete X if X present
3.Get() -> return any element if it is present
all operations in O(1).
No memory constraint.

Use an array, which has size equal to the maximum size of the key

Find the k-th Smallest Element in the Union of Two Sorted Arrays in (logn)

2011-04-10T23:31:00.001-07:00

resource lock

2011-04-09T02:37:00.001-07:00

Given an n-ary tree of resources arranged hierarchically. A process needs to lock a resource node in order to use it. But a node cannot be locked if any of its descendant or ancestor is locked. You are supposed to:
-> write the structure of node
-> write codes for
* Islock()- returns true if a given node is locked and false if it is not
* Lock()- locks the given node if possible and updates lock information
* Unlock()- unlocks the node and updates information.
Codes should be :
* Islock –O(1)
* Lock()- O(log n)
* unLock()- O(log n)

Check if Anagram

2011-04-09T00:04:00.001-07:00

How do you determine to strings are anagram.

Keep an integer array of size 26.
Go through the first string and increment the array location corresponding to the character.
Go through the second string and decrement the array location corresponding to the character.
At the end, if the array contains any non-zero element, then the strings are not anagrams.

Minimum Distance in an array

2011-04-09T00:02:00.001-07:00

Given an unsorted array and two numbers, find the minimum distance between them. For example, if the array is {1,2, 10, 2, 3, 5, 2, 1, 5} distance between 2 and 5 is 1.

Given an infix expression convert into postfix

2011-04-08T23:47:00.001-07:00

Given a doubly linked list with just 3 numbers 0,1,2 . Sort it

2011-04-08T23:45:00.000-07:00

1) Take 2 pointers at starting and at the end of list.
2) traverse list blindly push all the 2s at end of list.---> O(n)
3) move end pointer just before first two and sort normally by two pointer trick in O(n)

Zig Zag Order To Doubly linked list

2011-04-08T23:35:00.001-07:00

Given a binary tree,convert into a doubly linked list,The list must be as if the tree is traversed in zig-zag order from top to botton.. (left to right in one level and right to level in the next)

Minimum number of Coins

2011-04-08T22:44:00.000-07:00

You are given some denominations of coins in an array (int denom[])and infinite supply of all of them. Given an amount (int amount), find the minimum number of coins required to get the exact amount

Implement a double linked list with only one pointer

2011-04-08T13:31:00.001-07:00

Use XOR

Common Ancestor

2011-04-08T13:27:00.001-07:00

How to find the common ancestor of two nodes in a binary tree

mplement a function that, given a linked list that may be circular, swaps the first two elements, the third with the fourth, etc

2011-04-08T13:03:00.001-07:00

Check if String is a number

2011-04-08T12:58:00.001-07:00

Write a method that takes a string, and returns true if that string is a number

Recursive function for reversing linked list

2011-04-08T12:57:00.001-07:00

Java program to reverse a number

2011-04-08T12:34:00.000-07:00

Write a program to reverse a number. For example if 3652 is the input, the output should be 2563.

Java program for Breadth First Search of a Binary Tree

2011-04-06T11:40:00.000-07:00

The below program uses Binary Search Tree implementation
and Queue implementation

public void BFS()
{
Queue queue=new Queue();
Processable info;
TreeNode temp,temp1;

if(root!=null)
{
queue.enqueue(root);
}

while(true)
{
if(queue.isEmpty())
break;

temp=(TreeNode)queue.dequeue();
info=(Processable)temp.data;
info.process();

temp1=temp.left;
if(temp1!=null)
queue.enqueue(temp1);
temp1=temp.right;
if(temp1!=null)
queue.enqueue(temp1);

}

}

MergeSort - Java Program

2011-03-31T10:12:00.003-07:00

public int[] mergeSort(int[] arr,int start,int end)
{
int mid=(start+end)/2;

if(start {
mergeSort(arr,start,mid);
mergeSort(arr,mid+1,end);
merge(arr,start,mid,end);
}

return arr;
}

//To merge two sorted portions of an array
public int[] merge(int[]arr,int low,int mid,int end)
{
int[] temp=new int[end-low+1];

int ptr1=low,ptr2=mid+1,ptr3=0;

//Copy the elements in sorted order to a third array - O(n)
while(ptr1<=mid && ptr2<=end )
{
if(arr[ptr1] {
temp[ptr3]=arr[ptr1];
ptr1++;
ptr3++;
}
else if(arr[ptr2]<=arr[ptr1] && ptr2<=end )
{
temp[ptr3]=arr[ptr2];
ptr2++;
ptr3++;
}
}

//Copy remaining elements from first half
while(ptr1<=mid)
{ temp[ptr3]=arr[ptr1];
ptr1++;
ptr3++;
}

//Copy remaining elements from second half
while(ptr2<=end)
{ temp[ptr3]=arr[ptr2];
ptr2++;
ptr3++;
}

//Copy the sorted temp array back to the main array -O(n)
for(int i=low,j=0;i<=end;i++)
arr[i]=temp[j++];

return arr;
}

Java program to implement QuickSort

2011-03-31T10:12:00.001-07:00

Java program to find the middle of a linked list in O(n) time

2011-03-31T09:52:00.000-07:00

Method:
. Use two pointers in a loop
. One pointer will jump one node, where as the other pointer will jump 2 nodes.
. When the fast pointer reaches the end, the slow pointer will be at the middle.

To find if a linked list has a loop

2011-03-31T09:48:00.001-07:00

To find the intersection of two linked list

2011-03-31T09:47:00.001-07:00

1) Get count of the nodes in first list, let count be c1.
2) Get count of the nodes in second list, let count be c2.
3) Get the difference of counts d = abs(c1 – c2)
4) Now traverse the bigger list from the first node till d nodes so that from here onwards both the lists have equal no of nodes.
5) Then we can traverse both the lists in parallel till we come across a common node. (Note that getting a common node is done by comparing the address of the nodes)

Java Program to implement Min Heap

2011-03-01T04:49:00.000-08:00

package lab.heaps;

public class MinHeap
{
  int MAX_SIZE=100;
  int last_position; //last position which is empty
  Comparable[] heap=new Comparable[MAX_SIZE];
  //left child:2n+1, Right child: 2n+2

  public MinHeap()
  {
last_position=0;
  }

  public void insert(Object o)
  {
   Comparable data=(Comparable)o;
   Comparable temp;
   int i=last_position;
   last_position++;
   heap[i]=data;
   int parent_i=getParentPosition(i);

   if(parent_i==-1)
   { // No more checks needed for first insertion, so return
   return;
   }

   while(heap[parent_i].compareTo(heap[i])>0)
   {
   temp=heap[i];
   heap[i]=heap[parent_i];
   heap[parent_i]=temp;
   i=parent_i;
   parent_i=getParentPosition(i);
   if(parent_i==-1)
   {//To avoid array out of bound exception
   return;
   }

   }

   }

  public Object deleteMin()
  {
Object temp1=heap[0];
Comparable temp;

if(last_position==0)
{
return null;
}
else if(last_position==1)
{
heap[0]=null;
return temp1;
}

int i=last_position-1;
heap[0]=heap[i];
heap[i]=null;
i=0;

// If there exists a smaller child for i, then get it.
int next=getSmallerChild(i);

while(next!=-1)
{
// Go down the heap until you have no smaller child
temp=heap[i];
heap[i]=heap[next];
heap[next]=temp;
i=next;
next=getSmallerChild(i);
}

last_position--;
return temp1;

  }

  public Object getMin()
  {
return heap[0];
  }

  public int getLeftChildPosition(int i)
  {
return (2*i)+1;
  }

  public int getRightChildPosition(int i)
  {
return (2*i)+2;
  }

  public int getParentPosition(int i)
  {
if(i==0)
{
return -1;
}
else if(i%2!=0)
{
return (i/2);
}
else
{
return (i/2)-1;
}

  }

  public int getSmallerChild(int i)
  {
//Returns the index of the smaller child, if any of the children are smaller
int left=getLeftChildPosition(i);
int right=getRightChildPosition(i);

if(heap[left]==null && heap[right]==null)
{
return -1;
}
else if(heap[left]!=null && heap[right]==null)
{
if(heap[left].compareTo(heap[i])<0)
return left;
else
return -1;
}
else if(heap[left]!=null && heap[right]!=null)
{
if(heap[left].compareTo(heap[right])<0 && heap[left].compareTo(heap[i])<0)
{
return left;
}
else if(heap[left].compareTo(heap[right])>0 && heap[right].compareTo(heap[i])<0)
{
return right;
}
else
{
return -1;
}
}

return -1;

  }

}

2011-02-27T22:10:00.001-08:00

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

Java program for Descending order traversal of binary search tree

2011-02-25T22:20:00.000-08:00

public void descendingOrder(TreeNode rootnode)
{
if(rootnode !=null)
{
Processable info;

descendingOrder(rootnode.right);
info=(Processable)rootnode.data;
info.process();
descendingOrder(rootnode.left);
}
}

Java program for Non recursive tree traversal using stack

2011-02-25T22:19:00.000-08:00

public void inorderNonRecursive(TreeNode rootnode)
{
Stack stack =new Stack();
Processable info;
TreeNode temp;
temp=rootnode;

while(true)
{
while(temp!=null)
{
stack.push(temp);
temp=temp.left;
}
if(stack.isEmpty())
break;
temp=(TreeNode)stack.pop();
info=(Processable)temp.data;
info.process();
temp=temp.right;

}

}

Java program to Convert each level of a binary tree into a linked list and store the list pointers in an array

2011-02-25T21:20:00.000-08:00

Q. Create a linked list to hold each level of the binary tree. Then store the linked list headers in an array.

Algorithm.
1. Create a linked list array as an instance variable.
2. Create a preorder traversal like recursive function.
3. The function takes the level as a parameter and increments it before
passing it to the next recursive call.
4. Add the root element to the linked list stored at listarray[level].
5. make a recursive call with the left subtree and right subtree.

A working Java implementation is given below.

package lab.tree;

import lab.linkedlist.*;

public class SpecialTree extends Tree {

LinkedList[] listarray=new LinkedList[100];

public void treeToListArray(TreeNode rootnode,int level)
{
if(rootnode !=null)
{

if (listarray[level]==null)
{
LinkedList tmplist=new LinkedList();
tmplist.insertBegining(rootnode.data);
listarray[level]= tmplist;
level++;
}
else
{
listarray[level].insertBegining(rootnode.data);
level++;
}

treeToListArray(rootnode.left,level);
treeToListArray(rootnode.right,level);
}

}

Java program to count the number of bits that are set in an integer

2011-02-25T00:59:00.001-08:00

public int setBitCount(int n)
{
//Count the number of bits which are 1

int count=0;

while(n!=0)
{
if((n&1)>0)
{
count++;
}
n=n>>>1;
}
return count;

}

Java program to Find duplicate elements in an array

2011-02-25T00:58:00.001-08:00

public void findDuplicatesInArray()
{
// Find duplicate elements in an array O(n)

Hashtable hashtable=new Hashtable();
int [] inputA={1,2,2,3,4,5,5,6,7};

for(int i=0;i<9;i++)
{
if(hashtable.put(inputA[i], inputA[i])!=null)
{
System.out.println("Duplicate:"+inputA[i]);
}
}

}

Java program to Find the intersection of two arrays

2011-02-25T00:57:00.001-08:00

public void arrayIntersection()
{
//To find the intersection of 2 arrays
HashSet hashsetA = new HashSet();
HashSet hashsetB = new HashSet();
int[] inputA={1,2,3,4,5,6,7,8,9,10};
int[] inputB={5,6,5,12,13,14};

for(int i=0;i<10;i++) { hashsetA.add(inputA[i]); } for(int i=0;i<5;i++) { hashsetB.add(inputB[i]); } Iterator iterator;
iterator=hashsetB.iterator();

int i;
while(iterator.hasNext())
{
i=iterator.next();
if(hashsetA.contains(i))
{
System.out.println(i);
}
}

}

Java program to Shuffle a pack of 52 cards

2011-02-25T00:56:00.000-08:00

Solution :
For every i, card at a random location is placed at i
and card that was at i is placed at j.

If we want every card to change its previous location -
For every i,
Generate a random location >i and which is not same as i

public void shuffle()
{
int[] cards =new int[52];

Random random =new Random();

random.setSeed(new Date().getTime());

for(int i=0,j=0;i<52;i++,j++)
{
cards[i]=j;
System.out.println(j);
}

for(int i=0,j=0,t=0,k=0;i<52;i++)
{
//For every i, card at a random location is placed at i
//and card that was at i is placed at j
j=random.nextInt(52);
t=cards[j];
cards[j]=cards[i];
cards[i]=t;
}

for(int i=0;i<52;i++)
{
System.out.println(cards[i] + ", "+i);
}

}

Java program to find Reverse Factorial

2011-02-25T00:29:00.003-08:00

public int reverseFactorial(int fact)
{
int sum=1;
int i=1;
while(sum{
i++;

sum=sum*i;
}

if(sum==fact)
{
return i;
}
else
{
return -1;
}

}

Java program to De duplicate array in O(n) time

2011-02-25T00:29:00.001-08:00

public int[] deduplicate(int[] numbers,int N)
{
//Number from 1 to N are stored in an array of size N
//De-duplicate the array without using extra space.
//Algo should be O(n)
int val=0;

for(int i=1;i<=N;i++) { val=Math.abs(numbers[i]);//The fact that a number X appeared once - is represented by//changing the sign of the value at arr[X].//So if arr[X] is -ve that means X is duplicate. if(numbers[val]>0)
numbers[val]=numbers[val]*-1;
else
{
numbers[i]=N+1;
}

}
return numbers;

}

Java program to calculates x^m in O(log m) time

2011-02-25T00:28:00.001-08:00

public int logpower(int x,int m)
{
//Calculates x^m in O(log m) time

if(m==1)
return x;
else if(m%2!=0)
return logpower(x,m/2)*logpower(x,m/2)*x;
else
return logpower(x,m/2)*logpower(x,m/2);
}

Java program to find if a number is divisible by 3 without using / or % operator

2011-02-25T00:26:00.000-08:00

public boolean isDivisibleBy3(int num)
{
//Find if a number is divisible by 3 without using / or % operator

int sum=0;
String strnum=(new Integer(num)).toString();
if(num<10){ sum=num; } while(strnum.length()>=2)
{
sum=0;
for(int i=0;i<strnum.length();i++)
{
sum=sum+ Integer.parseInt(strnum.substring(i,i+1));
}
if(sum>=10)
{
strnum=(new Integer(sum)).toString();
}
else
{
break;
}

}

if(sum==3 || sum==6 || sum==9)
{
return true;
}
else
{
return false;
}
}

Java program to get Nth element from the end of a linked list

2011-02-24T05:17:00.000-08:00

Algorithm:
1.Use two pointers.
2.Traverse the list from begining.
3.Start the second pointer only when the first pointer reaches Nth element.

Java implementation:

public Object getNthFromLast(int n)
{
if(n<1) return null;
if(n>nodeCount)
return null;
ListNode temp1,temp2;
temp1=this.headnode;
temp2=this.headnode;
int i=1;
while(i<n)
{
i++;
temp1=temp1.nextnode;
}

while(temp1.nextnode!=null)
{
temp1=temp1.nextnode;
temp2=temp2.nextnode;
}

return temp2.data;

}

Java program to build NL Tree from preorder traversal

2011-02-23T05:45:00.000-08:00

There exists a special kind of tree which has the node value 'N' if it is an internal node
and 'L' if it is a leaf node. An internal node can have either 0 or 2 children, not 1. Build the tree from preorder traversal.

The algorithm works based on the concept that number of leaf nodes=number of internal nodes+1.
(This is true only if internal node can have either 0 or 2 children, not 1).

Count from the beginning of the preorder array and when number of internal nodes==number of leaf node, that means, it is the end of the left subtree.
Now recursively call the routine with the sub array containing the left subtree and with the
sub array containing the right subtree.
Finally join the left subtree and the right subtree with the root.

public TreeNode buildNLTree(char[] preorder)
{
int length_p=preorder.length;
if(length_p<1 )
{
//Wrong input
return null;
}

if(length_p==1)
{ //Stop condition for the recursion;
TreeNode node=new TreeNode();
node.left=null;
node.right=null;
node.data=preorder[0];
return node;
}

int n_count=0,l_count=0;
int pos_right_sub_tree=0;

for(int i=0;i<length_p;i++)
{
if(preorder[i]=='N')
n_count++;
else
l_count++;

if(n_count==l_count)
{
pos_right_sub_tree=i+1;
break;
}
}

char[] newpreorder_left=new char[pos_right_sub_tree-1];
char[] newpreorder_right=new char[length_p-pos_right_sub_tree];

System.arraycopy(preorder, 1, newpreorder_left, 0, pos_right_sub_tree-1);
System.arraycopy(preorder, pos_right_sub_tree, newpreorder_right, 0, length_p-pos_right_sub_tree);

TreeNode treeroot=new TreeNode();
treeroot.data=preorder[0];

TreeNode leftsubtree=buildNLTree(newpreorder_left);
TreeNode rightsubtree=buildNLTree(newpreorder_right);

treeroot.left=leftsubtree;
treeroot.right=rightsubtree;

return treeroot;
}

Java program to build binary tree from preorder traversal and inorder traversal

2011-02-23T03:41:00.001-08:00

public TreeNode buildTree(int[] preorder,int[] inorder )
{
int length_p=preorder.length;
int length_i=inorder.length;

if(length_p<1 ||length_i<1 )
{
//Wrong input
return null;
}

if(length_p==1)
{ //Stop condition for the recursion;
TreeNode node=new TreeNode();
node.left=null;
node.right=null;
node.data=preorder[0];
return node;
}

int preorder_root_val=preorder[0];
int inorder_root_pos=0;

for(int i=0; i<length_i; i++)
{// Get the position of the root in inorder array
if(inorder[i]==preorder_root_val)
{
inorder_root_pos=i;
break;
}
}

//Create arrays which will hold the traversals of
//left and right subtrees
int[] newinorder_left=new int[inorder_root_pos];
   int[] newpreorder_left=new int[inorder_root_pos];
int[] newinorder_right=new int[length_i-inorder_root_pos-1];
   int[] newpreorder_right=new int[length_i-inorder_root_pos-1];

   //Fill the arrays that hold the subtree traversals
System.arraycopy(inorder, 0, newinorder_left, 0, inorder_root_pos);
System.arraycopy(preorder, 1, newpreorder_left, 0, inorder_root_pos);
System.arraycopy(inorder, inorder_root_pos+1, newinorder_right, 0, length_i-inorder_root_pos-1);
System.arraycopy(preorder, inorder_root_pos+1, newpreorder_right, 0, length_i-inorder_root_pos-1);

//Create the root Node
TreeNode treeroot=new TreeNode();
treeroot.data=preorder[0];

//Recursive call to buildTree with subtree traversals
TreeNode leftsubtree=buildTree(newpreorder_left,newinorder_left);
TreeNode rightsubtree=buildTree(newpreorder_right,newinorder_right);

//Join the subtrees with the root
treeroot.left=leftsubtree;
treeroot.right=rightsubtree;

//Return the created tree;
return treeroot;

}