Monthly Archives: October 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). 

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++


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.

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.

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.

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# 1 2 3 4 5 6 7 8
Data 6 2 6 6 3 6 1 6
Majority 6 2 6 6 6 6 6 6
count 1 1 1 2 1 2 1 2

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.

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

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.

How does a counting sort work?

Counting sort as its name indicates sort a list of integers by counting the occurrence each number appearing in the list. This is possible when the range of integers (particularly small) is given.

Unlike comparison based sorting algorithms which run in O( n log n) time in the worst case, Counting sort runs O(n) time.

For example let us assume the range of numbers is 0-4. and we have an input array as follows.


3
0
3
2
4
0
2
1
2
4

This is basically integer sorting algorithm where in 
  1. The first iteration it counts the frequency of each number appearing the list. These counts are stored in an array indexed by the numbers itself. 
  2. In the second iteration, it counts the prefix sum array by counting how many numbers that are less than or equal to that number.
  3. The third iteration places the numbers in the correct place based on their frequency.
Count array


Index
0
1
2
3
4
Counts
2
1
3
2
2
Prefix Sum
2
3
6
8
10

  

 You can take a look at this animation for understanding counting sort better.

The following Java program implements the above approach.

/**
* Created with IntelliJ IDEA.
* User: Ravi
* Date: 10/10/13
* Time: 5:29 AM
* To change this template use File | Settings | File Templates.
*/
public class CountingSortDemo {
public static void main(String[] args)
{
int[] numArray = {3,0,5,9,6,2,4,5,4,1};
int[] sortedArray = countingSort( numArray );
for( int i = 0; i < sortedArray.length; i++ )
{
System.out.print( sortedArray[i] + " ");
}
}
//Counting sort method
public static int[] countingSort(int [] array )
{
int[] sortedArray = new int[array.length];
int[] countArray = new int[10]; //For simplicity Assume the range 0-9
int i;
for( i = 0; i < array.length; i++ )
{
countArray[ array[i] ]++;
}
//calculate the prefix sums
for( i = 1; i < countArray.length; i++ )
{
countArray[i] += countArray[i-1];
}
//place the elements in the sorted array
for( i = 0; i < array.length; i++ )
{ 
            //Get the index to place into sorted array 
            int cIndex = countArray[ array[i] ];

sortedArray[cIndex-1] = array[i];
//decrement the frequency so that the same number is placed next
            //to previous entry 
countArray[ array[i] ]--;
}
return sortedArray;
}

}

This code is generic to sort any array objects with integer keys. If we just want to sort the array, we can combine the last two loops where we can fill the array with count of each number in order. You can do this by the following loop. 

int resIndex = 0;
for( i = 0; i < countArray.length; i++ )
{
for( int j = 0; j < countArray[i]; j++)
sortedArray[resIndex++] = i;
}