Thursday, October 31, 2013

Traversals of a binary tree

Traversal algorithms of non-linear data structures like trees are designed to visit/print all the elements in that structure.

There are three main traversals of the binary tree. Namely
  • In-order traversal
  • Post-order traversal
  • Pre-order traversal
In addition to these, there are inverses of the above algorithms, and there is a level order traversal.

In this post we will see the three main traversal algorithms mentioned above. All of these are defined as recursive algorithms.
In In-order traversal, we first visit the left sub-tree, then root, and then the right sub-tree.
In Post-order traversal, we first visit the left sub-tree, then the right sub-tree, and then the root.
In Pre-order traversal, We first visit the root, then visit the left sub-tree and then visit the right sub-tree.
For example consider the simple  3 node binary tree
In-order traversal: B  A  C
Post-order traversal: B  C  A
Pre-order traversal: A  B  C

To consider a bigger example, take the following binary search tree and it's traversal sequences for the three algorithms.
In-order: 1  2  3  4  5  6  7  8
Post-order: 1  2  4  3  7  6  8  5
Pre-order: 5  3  2  1  4  8  6  7 
The in-order traversal of the binary search tree always produces the sorted order of it's elements.
Here is the C++ code for all the traversals.


Wednesday, October 30, 2013

Finding the height of the binary tree

Given a binary tree how to find the height of the tree. 
It is defined as the number of nodes in the longest path from root to any leaf.
 We can assume that the height of empty tree is 0 and the height of a tree with just root node as 1. For example the below tree has a height of 4.

We can calculate the height of the tree using recursive method very easily. It is based on the observation that height of a binary tree is 
1 + Max( height(left-sub-tree), height(right-sub-tree) )

Here is the C++ code which implements this simple algorithm.

Tuesday, October 29, 2013

Subset sum problem

Given a set of numbers and a target value, we have to find if there is any subset whose sum is equal to the target value.

For example let the array be {10, 34, 19, 27, 58, 45} and the target sum is 56, we have a subset {10,19,27} with the given sum. We don't have any subset with sum 100.

A simple recursive solution can be given as follows. We pass the array, the starting index, and target sum to the function. 
At each index we have two choices:
  • Include the current element and search for {sum - current_num} in the remaining set of elements.
  • Exclude the current element and search for sum in the remaining set of elements.
public static boolean hasSum(int [] array, int start, int sum)
    {
        if( sum == 0 ) //found the sum?
            return true;
        
        if( start > array.length-1 )//reached end of the array?
            return false;
        
        return hasSum(array, start+1, sum) || hasSum(array, start+1, sum-array[start]);
        
    }

But this algorithm has an exponential time complexity which is not efficient. 
Let us look at more efficient approach based on Dynamic programming.

We take a boolean matrix of size (sum+1) x (N+1) where sum is the target sum and N is the size of the given set.

matrix[i][j] = true; indicates that there is a subset of array[0..j-1] which contains the sum i.

We initialize the following entries as base values.
  • matrix[0][j] = true; where 1 <= j <= N since in any set there will be empty subset with sum 0;
  • matrix[i][0] = false; where 1 <= i <= sum since we can't find a sum > 0 in an empty array.
We calculate the remaining entries as follows.
matrix[i][j] = matrix[i][j-1];
If there exists a subset of array[0..j-2] with the sum i; then there should be a subset of array[0..j-1]also with the sum i.

If i >= array[j-1]; we check to see if matrix[i - array[j-1]][j-1] is true. This means check if there is any subset of array[0..j-2] with sum i-array[j-1].
If there is, then we assign true to this entry.

Finally we return the value at matrix[sum][N] which indicates true if there is a subset of array[0..N-1] with the given sum. Otherwise false.

Here is the Java code which implements this.


Monday, October 28, 2013

Jolly jumpers problem

In this post I introduce you to a competitive programming problem called Jolly jumpers. This problem is available on UVa online judge on this link

UVa site is one of the first online judge websites which listed programming problems from different competitions like ACM ICPC and IOI and allowed users to solve and submit their programs online to check if their solutions are correct or not. This site contains a huge number of programming problems of varying complexities. Go and register yourself on this site if you are passionate about programming and start solving the problems!

The problem is defined as follows...

A sequence of n > 0 integers is called a jolly jumper if the absolute values of the difference between successive elements take on all the values 1 through n-1. For instance,
1 4 2 3
is a jolly jumper, because the absolutes differences are 3, 2, and 1 respectively. The definition implies that any sequence of a single integer is a jolly jumper. You are to write a program to determine whether or not each of a number of sequences is a jolly jumper.

Input

Each line of input contains an integer n <= 3000 followed by n integers representing the sequence.

Output

For each line of input, generate a line of output saying "Jolly" or "Not jolly".

Sample Input

4 1 4 2 3
5 1 4 2 -1 6

Sample Output

Jolly
Not jolly

The C++ code to solve this problem is given below.
To solve this problem we use a diff array. We try to calculate the absolute difference between each of the successive elements and populate the result in the diff array. while populating, we check if the result lies in the range [1, N-1]. If not, the array is not a jolly jumper. Also if the same difference appears more than once, it is not a jolly jumper.

Sunday, October 27, 2013

Finding three elements with zero sum in an array.

Given an array of positive and negative numbers, how do we write a program to check if it has three elements with sum 0.

For example, the array  {-31, 19, -6, -45, 12, -8, 3, -77, 56, 29} contains {-31,12,19} with sum zero.

One obvious solution is to examine each possible triplet of the array and check if there is a triplet with sum = 0. But this takes O(n3) time and is not efficient for large arrays.

A better approach would be to sort the array first in increasing order. Follow this iterative algorithm.
  • Fix the first element, start two pointers one at the begin and the other at the end of the sorted array. 
  • If the sum of the three elements is zero return.
  • If the sum is greater than zero, we decrement the end pointer so that the sum moves closer to zero
  • If the sum is negative, we increment the begin pointer to add up value to sum.
  • Iterate this procedure until the fixed element moves towards the end.
This procedure takes O(n log n) for sorting the array and O(n2) for actually finding the triplet. So the overall time complexity would be O(n2) and O(1) extra space. 

Here is the java code to do this.


Saturday, October 26, 2013

How to insert into a binary search tree

A binary search tree is a hierarchical data structure which stores data in a non-linear fashion. It supports the insertion, search and deletion operations in O( log n ) time. Take a look at the below picture.

This is an example of binary search tree. The node at the top containing 5 is the root and all the elements to the left of it(left sub-tree) are less than 5 and all the elements to the right of it (right sub-tree) are greater than 5. A binary search tree does not allow duplicate elements in it. 

In this post we see how an insertion method works. It works very similar to the binary search.

The insert method looks at the root. If the given data is lesser than root data, it has to be inserted into the left sub-tree. Otherwise it has to be added in the right sub-tree. Since the left/right sub-trees are also binary search trees, we call the procedure recursively.
Here is the complete C++ program which implements a binary search tree in Object Oriented approach. I have used in-order traversal to print all the elements of the binary search tree. These procedures are explained in future posts.

Friday, October 25, 2013

Deleting duplicates from a sorted linked list

Given a sorted linked list, We have to delete all the duplicates in that list. For example, If we get the following list

1 -> 1 -> 2 -> 3 -> 3 -> 3 -> 4 -> 4 -> 5

The output should be

1 -> 2 -> 3 -> 4 ->5

To solve this problem we take two pointers current and next, we iterate through the list until the next pointer reaches the end of the list.

In each iteration we compare the data at current and next nodes. If they are equal, we delete the next node, and the next pointer is advanced to the subsequent node. Take a look at the pictorial representation of this step to understand better.


Here is the working code of C++ for this.

Thursday, October 24, 2013

Sorting a linked list using bubble sort

How do we sort a linked list? 
In this post, we see one such method using bubble sort algorithm.

We have discussed the Bubble sort algorithm on arrays in my previous post. The same algorithm is also applicable to singly linked lists as well.

We first find the length of the linked list (len). The outer loop iterates for (len-1) times and the inner loop iterates for (len-1-i) times.

Since we cannot access the linked list elements by their indices, we use two pointers to keep track of the current node and the next node which will be compared and swapped in each iteration.

Here is the Object Oriented C++ implementation. 
 

Monday, October 21, 2013

Searching for an element in the sorted matrix

Given a row wise and column wise sorted two dimensional array or matrix. How to search for an element efficiently?

Example of the array can be

int[][] matrix = {
                   {1,3,5,7,9},
                   {10,12,14,16,18},
                   {19,21,23,25,27},
                   {28,30,32,34,36},
                   {37,39,41,43,45}
                };


This can be done using the following algorithm. 

We start our search with the top right element. 
  • If it is equal to the key, we print corresponding indices and we are done!. 
  • If the key is greater than the current element, we move to the next row because all the elements in the current row prior to this element are lesser. 
  • If the key is less than the given element, we move to the previous column.  The reason is similar to the above.
We continue this search until we find the key or until we confirm the element is not present. If we reach last row first column, we can confirm that the element is not present.

Here is the java implementation of the above algorithm. The time complexity of this program is O(n) and n is the number of rows and columns.

Sunday, October 20, 2013

Printing biggest elements to its right in an array

Given array of elements we have to write a program to print the biggest element to it's right for each of the elements in the given array.

For example let us consider the array {3, 9, 2, 4, 6, 1}.

The output for this array should be {9, 6, 6, 6, 1, -1}. As a convention, we print -1 for the last element because there are no elements to it's right.

This problem can be solved in O(n) time and O(1) space by using the following algorithm.

Start from the end of the array. print -1 for the last element. Use a variable to keep track of the greatest element found so far while traversing backwards and fill the entries with this variable.

Here is the Java program to do this.

Saturday, October 19, 2013

Alternative arrangement of numbers in the array

Given an array of 2n numbers of the following format
{a1, a2, a3,...an, b1, b2, b3, ...bn}
We have to write a program to transform this into the following format.
{a1, b1, a2, b2, a3, b3, ..., an, bn}

This can be done using the following algorithm. 
We iterate over the array for (n-1) times. In first iteration we swap the middle pair. In the second iteration we swap two of the middle pairs, and so on.

For example let us consider an array of 6 numbers {1,3,5,2,4,6}. Here is how the array is changed while traversing through the algorithm.

1  3  5 <-> 2  4  6
1  3 <-> 2  5 <-> 4  6
1  2  3  4  5  6

Since n = 3, the algorithm iterated just two times and a total of 3 swaps.To generalize, for some arbitrary n, there will be (n2+2*n) / 8 swap operations performed. So it's time complexity is O(n2) and space complexity is O(1). 


Friday, October 18, 2013

Finding the nth node from the end in a linked list

Given a linked list, how do efficiently find the nth node from the end?

For example  in the following linked list, 3rd node from the end is '6'.

2 -> 1 -> 6 -> 5 -> 9

One obvious method is to find the length of the linked list (len) by going through the list. calculate the difference (len - n). Again traverse the list (len - n) times to get the required node. Though this approach is O(n), we traverse the list twice.

We can do it in just one iteration itself. We take two pointers one main pointer (ptr) and one helper pointer (hPtr). First we travel a distance of n nodes with hPtr. Then we start from the beginning with main pointer also. By the time the hPtr reaches the end, ptr would be pointing to the nth node from the end.

Here is Object Oriented implementation of this in C++


Thursday, October 17, 2013

Finding a number in a sorted array with the least difference from given number

Given a sorted array and a value, we have to find the closest value (with least difference).

For example let the input array be {-2, 4, 7, 11, 17} and the input number is 10, the output should be 11.

This problem is actually a variation of binary search where in we have to find out the closest value found the array. If the given value exists in the array, we have to return that.

A sorted array and binary search gives a hint that we can solve this problem in O( log n) complexity. Here is how we can modify the binary search algorithm to solve this problem.

As in binary search algorithm, we try to search for the given number in the middle of the array. If the element is found, we just return it, because we got the least difference i.e 0.

We also maintain two variables one to store the minimum difference found so far (minDiff), and the other (result) to store the corresponding number. In each iteration, we find the difference between the given value and middle value. If this is lesser than minimum difference, we update the two variables.

At the end of the search we have the required number in the result variable.

Below is the Java code which implements the above algorithm.


Wednesday, October 16, 2013

Moving zeroes to the end of array

Given an array of elements which contains some zeros in between, we have to write a program to move all zeros to the end without disturbing the original order of the elements.

For example if the input is {0, 6, 2, 0, 0, 3, 1, 0, 4, 5, 0}, the output should be {6, 2, 3, 1, 4, 5, 0, 0, 0, 0, 0}

The algorithm is simple, we take two  indices , one to loop through the entire array, and another to keep track of the non-zero elements. Once we loop through all the elements, we can fill the remaining spaces with zeros.

This algorithm scans the input array only once and hence runs in O(n) time and does not take any extra space O(1).

Here is the Java code to do this.

Tuesday, October 15, 2013

Printing last K lines from a file

Given a large file containing many lines of text, How do we write an efficient program to print last k lines from that file.

One obvious approach is to read the entire file first to find the number of lines (n). In the second iteration skip first (n-k) lines, and print the remaining k lines. 

However, this approach might be prohibitively costly as the file is very big and disk operations are slow. More over, we are reading the file twice.

We can design an efficient solution if we take a buffer of size k and keep filling the buffer with the lines read from the file in a circular fashion. This is a type of page replacement algorithm often used in operating systems. If the buffer is full, we replace the oldest entry in the buffer with the new entry.

Once k lines are read from the file, we wrap around, and go back to the beginning of the buffer and overwrite the previous entries as they are no longer the last  k lines. 

Following is the java implementation of the above algorithm.

Sunday, October 13, 2013

Finding the majority element of an array

Given an array of  N elements, the majority element is defined as the one which occurs more than N/2 times.

One simple approach is to find the mode (which appears for most number of times) and check if its frequency is greater than N/2.

Three strategies for finding the mode are discussed in my previous post. The best one among them, the hash map approach takes O(n) time and O(n) space.

We can solve this program even better by using Moore's voting algorithm. This takes O(n) time and O(1) space.

This algorithm tries to find out the majority number in two iterations. In the first iteration, a probable candidate for majority number is found. In second iteration, we check if the candidate is really the majority number by counting it's frequency.

The first iteration works as follows. We initialize the first element as the majority number and the count variable is initialized with 1. During further iterations, if the element is equal to majority number, we increment the count, otherwise we decrement the count. If at any point, the count reaches zero, We reassign the majority number to the current element and assign 1 to count.

For example, let us consider the input array {6, 2, 3, 6, 3, 6, 6, 6}. The following table explains the logic.

Iteration#12345678
Data62663616
Majority62666666
count11121212

At the end 6 is the candidate for majority number. In the second iteration we check the frequency of 6. If it is more than half of the array size it is the majority element.
 
Here is the Java implementation of this approach.

Reversing the words in the string

Given a string, how do we reverse the words inside the string?

For example if the input string is "this is a test" the output should be "test a is this".

The algorithm is simple. This can be done in two steps. The first step is to reverse the entire string. In the second step we traverse the string to find the individual words separated by spaces and reverse them.

In the following program I have used C++ STL string instead of a C-style null terminated string. To read a string including spaces I have used getline(cin,str) function. I have also used reverse(str.begin(), str.end()) as a helper function from standard template library for simplicity. 

Here is the C++ program.

Friday, October 11, 2013

Inserting an element into a sorted linked list

Given a sorted linked list, how do we insert data into the list in proper order?

This is nothing but a step in insertion sort. Simply iterate through the elements to find the position for given number and insert at that position.

Here is the Java code to do that. I have used the LinkedList class available in java utilities so that we need not implement the entire linked list class on our own.


import java.util.LinkedList;
import java.util.ListIterator;

/**
 * Created with IntelliJ IDEA.
 * User: Ravi
 * Date: 10/11/13
 * Time: 5:32 AM
 * To change this template use File | Settings | File Templates.
 */
public class SortedListDemo {
    public static void main(String[] args)
    {
        LinkedList<Integer> sortedList = new LinkedList<Integer>();

        sortedInsert(sortedList, 3);
        sortedInsert(sortedList, 1);
        sortedInsert(sortedList, 6);
        sortedInsert(sortedList, 4);
        sortedInsert(sortedList, 2);
        sortedInsert(sortedList, 5);

        System.out.println("Contents of the sorted list: " + sortedList);
    }
    public static void sortedInsert(LinkedList<Integer> sList, int data)
    {
        int pos = 0;

        for(int listData : sList )
        {
            if( listData > data)
                break;
            pos++;
        }

        //Alternative code for the above loop using an iterator
        /*
        ListIterator<Integer> listIterator = sList.listIterator();
        while( listIterator.hasNext() && listIterator.next() < data )
            pos++;
        */
        //insert the data in its correct position
        sList.add(pos, data);
    }
}

Thursday, October 10, 2013

Removing a given character from the string

Given a string and a character, Write a function to remove all instances of the character and return the modified string.

One easy method is to iterate through each character of the string, Once a restricted character is seen, we move all the characters appearing after it by one position. This approach involves a lot of shift operations and in worst case it takes O(n2) time.

We can be more efficient if we follow the approach given below.

Take two indices; one running index (i) and one result index (r). All the valid characters are copied to beginning of the string and both indices are incremented. If a prohibited character is seen, we skip that character and just increment i. At the end, we re-size the string so that the characters beyond the index 'r' are removed.

Let us understand this with a simple example.

Let the input string be 'PROGRAM' and we want to remove the letter 'R'. The following table illustrates the behavior of the algorithm by iteration.


0
1
2
3
4
5
6
P
R
O
G
R
A
M
P
R
O
G
R
A
M
P
R
O
G
R
A
M
P
O
O
G
R
A
M
P
O
G
G
R
A
M
P
O
G
G
R
A
M
P
O
G
A
R
A
M
P
O
G
A
M
A
M

The shaded part indicates the result string that is formed in-place without using the extra space.