Thursday, November 28, 2013

Maximum numbers in a sliding window

Given an array of N values and a value K, Write a program to print the maximum of all the sliding windows (sub-array) of size K.

For example let us consider the following array as input 

[4, 5, 3, 2, 6, 1, 2, 3, 8, 4]

Let as take the sliding window of size 3. The output will be as follows

Sliding Window           Maximum
---------------------------------
[4, 5, 3]                  5
[5, 3, 2]                  5
[3, 2, 6]                  6
[2, 6, 1]                  6
[6, 1, 2]                  6
[1, 2, 3]                  3
[2, 3, 8]                  8
[3, 8, 4]                  8

The brute force solution can be to find the maximum of each sliding window when we move forward by one element. In an array of size n, there will be (n-k+1) sliding windows of size k. For each window, it takes O(k) time to find the maximum. So, it's time complexity is O( (n-k+1)* k ) ~= O(n*k).

Can we do better than this?

Yes! this problem can be efficiently solved using the dequeue data structure. Dequeue data structure supports inserting and deleting the elements at both ends of the queue via push_back(), pop_back(), push_front() and pop_front(). Here is how the algorithm works. 

We maintain the indices of elements of the current window in a dequeue. We also make sure that the maximum element always appear in the front of the queue. The new element is added at the back of the queue by deleting all the smaller elements before it. We will also delete the element just went out of scope (previous window element). In each iteration we print the front of the queue which is maximum.

Here is the C++ implementation of this algorithm.


Friday, November 22, 2013

Inserting an element into sorted linked list

Given a sorted linked list write a program to insert data into it's correct position. 
For example consider the following linked list

1 -> 3 -> 4 -> 5 

Inserting 2 should change the list to

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

Inserting 0 should change it to

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

Inserting 6 should change it to

0 -> 1 -> 2 -> 3 -> 4 -> 5 -> 6. 

The three examples indicate three different cases to be considered while inserting into a sorted linked list.

Case 1: List can be empty or new element is added as the first element
Case 2: New element can be inserted anywhere in the middle of the linked list
Case 3: New element is added as the last element.

The following diagram illustrates the insert process.




In the following C++ program case 1 is handled in one block and case 2 and 3 are handled in the last block.


Thursday, November 21, 2013

Finding K-size sub array with minimum sum

Given an array of size N and a number K. We have to find the sub-array of size K such that the sum of it's elements is minimum among all K-size sub arrays.

For example Let us consider the following array of size 10. 

{1, 2, 1, 3, 1, 1, 1, 4, 2, 3}

The smallest sub-array of size 3 is {1, 1, 1} which starts at the index 4 (0-based index).

We can use the following algorithm.

We calculate the sum of first K numbers initially and assume that this is the minimum sum and the index is 0. We maintain a variable to track the running sum of K values.

When we move the sliding window by one element, we subtract the previous element add the current element to the running sum. Then we update the minimum sum if the latest sum is less than minimum sum.

This procedure is repeated till the sliding window reaches the end of the array.

Here is the C++ implementation.


Wednesday, November 20, 2013

Finding two numbers occuring once

Given an array containing all elements twice except two numbers. Write a program to find those two numbers.
For example let us consider the following array
{2, 3, 2, 1, 4, 1, 4, 5} 
The answer is {3,5} because they appear only once and all remaining elements appear twice.
This question is somewhat similar to earlier post. This gives us a hint to use XOR operation to solve this problem. Let us see how we can utilize XOR operation.

We first find the XOR of all the elements in the array. This gives a bit pattern which is an XOR of required two values because all other elements occurs twice they get zeroed out.

For the above example the xor value is 0110 = 0011 ^ 0101

Let the two unique numbers are x, y. The next problem is how to find x,y from this xor value. Let us denote ith bit is the first set bit in the xor result. We divide all the numbers in the array into two parts. One part containing all the numbers with bit i = 1, and the other part containing all the numbers with bit i = 0;

This partition segregates the numbers such that all the pairs with ith bit 1 goes to one partition and all pairs with ith bit 0. But x and y fall into two different buckets their bit patterns will be different.

Now finding the XOR value of these partitions separately gives us the required result.

In the above example. The XOR value has 1st bit as 1.
{2,2,3} forms one partition and {1,1,4,4,5} forms another partition.

Parition-1    Partion-2
0010          0001
0011          0100
0010          0001
                 0100
                 0101
---------------------
 0011(3)     0101(5)
 So 3,5 are the answers

Here is the Java code to do this.


Tuesday, November 19, 2013

Number of bits to change from one number to other

Given two numbers, calculate the number of bits required to change from one number to the other.

For example 12 in binary can be represented as 1100. 15 is represented as 1111. We need to change two bits to convert one number from the other as the last two bits are different.

We can find out the difference bits as follows. We first find out the XOR of two numbers. This gives us a bit pattern in which there is a set bit, if two bits differ. Then we can calculate the number of set bits in the XOR which gives the required answer.

Here is C++ code for this.

Monday, November 18, 2013

Pair swapping in a linked list

Given a singly linked list, we have to swap the adjacent nodes in it.

For example some input/output samples are given below

Input                              output
-------------------------------------------------
1->2->3->4->X                      2->1->4->3->X
1->2->3->4->5->X                   2->1->4->3->5->X
1->X                               1->X

The algorithm is very simple. We have to move pair by pair and swap the data part of each pair. 


Here is the C++ code for this.

Friday, November 15, 2013

Printing the prime factorization of a given number

How do we write a program to find the prime factorization of a given number?

For example prime factorization for 18 can written as 2 * 3 * 3 or 2 * 3 ^ 2.
For any number there is only one possible prime factorization. 

An efficient algorithm can be given as follows. we run a loop with i ranging from 2 to sqrt(n). In each iteration, we try to reduce the number by dividing it with i as many times as possible. As we examined in the last post, we can find all the factors of a number by checking the divisibility of it from 1 to square root of n itself.

Here is the C++ code to do this.

Thursday, November 14, 2013

Finding all the factors of a given number

Given a number, how do we write a program to find all of it's factors or divisors.
For example, for the number 18, the factors are {1, 2, 3, 6, 9, 18}.

An immediate algorithm that comes to our mind is to run a loop from 1 to n. In each iteration check if the counter divides the number n. If it divides print it.
for( i = 1; i <= n; i++ )
{
    if( n % i == 0 )
        cout << i << " ";
} 
But this approach runs for n iterations. we can do better than this. One possible improvement can be to start with 1 and n as factors and run the loop from 2 to n/2. This is based on the observation that after n/2 there will not be any factors of n until n. So it is safer to stop at n/2 itself.
list.add(1);
for( i = 2; i <= n/2; i++ )
{
    if( n % i == 0 )
       list.add(i);
}
list.add(n); 
This is clearly an improvement over the previous method because it runs only for n/2 iterations. Can we still improve this?  

Yes it is possible! This is based on the observation that the factors always appear in pairs. If a is a factor of n, then there should be some k such that a * k = n. so k must also be a factor of n. This approach runs only for sqrt(n) iterations and performs better than the previous two algorithms.
factorList.add(1);
for( i = 2; i <= sqrt(n); i++ )
{
    if( n % i == 0 )
    {
       factorList.add(i);
       if( i != sqrt(n) )
          factorList.add(n/i);
    }
}
factorList.add(n);
 

Wednesday, November 13, 2013

constant pointers and pointer to constant

In this post we talk a little bit about the constant pointers and pointer to a constant and the difference between them.

In C programming, pointer is a crucial concept and it is always good to have a clear understanding of the fundamentals.

Constant pointers:
Constant pointer as the name indicates is a pointer whose value can not be changed. In another way, once a pointer is initialized with an address of a variable, it can not point to any other variable further. We can also say it is a read-only pointer. For example, take a look the following code snippet.
int var1 = 1, var2 = 2;
int * const pVar = &var1; //constant pointer to an integer
pVar = &var2; //Incorrect, gives a compilation error
We have declared two variables var1, and var2. A constant pointer pVar is initialized to point to var1. In the next statement we are trying to point pVar to var2 which is incorrect and gives a compilation error as follows.
[Error] assignment of read-only variable 'pVar1'
A constant pointer is useless if we don't initialize it with any address. The compiler gives no error in this case, but that pointer is useless because it can not point to any object further.
int count = 10;
int * const pCount;//Valid code;no compiler error
pCount = &count; //Invalid; compiler error
Pointer to constant:
A pointer to a constant object. This means that we can not modify the object addressed by this pointer. But we can always read the object via this pointer and also we can make this pointer to address another object. To understand this, let us look at the following code snippet.
int var = 1, other = 2;
const int *pVar =&var; //pointer to a constant
*pVar = 10;//error:assignment of read-only location'*pVar1'
printf("%d", *pVar); // Valid; we can always read the value
pVar = &other; //valid
We can also create a constant pointer to a constant with the following code. Through this pointer we can not change the value, and we can not make it point to any other object. 
int var = 100, other = 200;
const int * const pVar = &var;//constant pointer to a constant
*pVar = 10;//Error:assignment of read-only location'*pVar1'
pVar = &other; //Invalid; compiler error
other = var / 10; //valid; we can read the value

Tuesday, November 12, 2013

Reverse a single linked list

Given a singly linked list, how do we reverse it by re-arranging the links?

For example if the given linked list is  1 -> 2 -> 3 -> NULL. The output of reverse method should be 3 -> 2 -> 1 -> NULL.

The following diagram shows the simple steps to perform the reversal.


And here is the C++ code which includes both recursive and iterative versions of reversal method.

Monday, November 11, 2013

Printing the matrix in a spiral order

Given a two dimensional array or a matrix, how do we write a program to print the elements in a spiral order.

For example the spiral order for the following matrix is
1  2  3  4  8  12  16  15  14  13  9  5  6  7  11  10

1   2   3   4
5   6   7   8
9  10  11  12
13 14  15  16 

The algorithm for this problem involves four steps. 
  • Print the elements of the top row from left to right and increment top.
  • Print the elements of right column from top to bottom and decrement right.
  • Print the elements of bottom tow from right to left and decrement bottom.
  • Print the elements of left column from bottom to top and increment left.
Repeat the above steps until there are no more elements left. 
As the algorithm indicates, we need four variables to keep track of the top and bottom rows, left and right columns. We also use an extra variable for the direction. It can have four values indicating four possible directions.

Here is the Java implementation of the above algorithm.

Saturday, November 9, 2013

Reversing a doubly linked list

Given a doubly linked list, how do we reverse it by just re-arranging the pointers?

Here is an example of input/output.

The following picture depicts how we re-arrange the pointers.


Here is the Java implementation.

Wednesday, November 6, 2013

Checking if any anagram of a given string is palindrome or not

Given a string, how do we check if any anagram of it can be a palindrome?

For example let us consider the string "AAC". An anagram of it is "ACA" which is a palindrome. We have to write a method which takes a string and outputs true if we can form a palindrome from any anagram of the given string. Otherwise outputs false.

We can immediately think of a solution where we can generate all anagrams of the given string and check if there is any palindrome exists. But this approach is very lengthy and has exponential time complexity (O(n!)).

The key to solve this problem efficiently is to understand how a palindrome is formed. We all know that a palindrome reads the same when you read from left to right or right to left. 

A palindrome can be broken into two halves. where in the first half is the reverse of second half. In case of odd length of strings, we have to ignore the middle character.

So for every character in the first half, there is a corresponding matching character in the second half. This indicates that all the characters in a string must occur even number of times except for one which appears in the middle of the string.

Hence if we check if there is at most one character with odd occurrences in the string we can say that we can form a palindrome from any anagram.
Here is the Java code which implements this algorithm. For simplicity, I assumed that the input string contains only lowercase English alphabets.

Tuesday, November 5, 2013

Merge two sorted linked lists

Given two sorted linked lists, how do we merge them without using any extra space. That means we have to re-arrange the links to form a single sorted linked list.

For example let us consider the following two sorted lists as input.
1 -> 3 -> 5 -> 7
2 -> 4 -> 6 -> 8
The output should be
1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8

The algorithm is simple. We take the smaller node between the two lists in each iteration, and add it to the result list. We do this until we process any of the list to completion. If there is any remaining portion of the other list, we join it with the result list.

Here is the C++ code do this.
  

Monday, November 4, 2013

Merging k sorted lists

Given K sorted lists, how to merge them into a single sorted list?

Let total number of elements in K sorted lists is N. We have to form a single sorted list of length N.

For example let us consider the following input lists
{4, 19, 27}
{1, 6, 50, 73}
{9, 45, 59, 67}

The output should be {1, 4, 6, 9, 19, 27, 45, 50, 59, 67, 73}.

In this post, we discuss an efficient approach by using priority queues (heaps). This problem is one of the nice examples of using priority queues.

Here is how the algorithm works.
  1. Add the first elements from all the lists into a priority queue along with their list indices.
  2. Until the priority queue is empty, do the following
    1. Remove the minimum element from the priority queue and add it to the result list. Let this minimum element belongs to min_list.
    2. Add the next element from min_list to the priority queue if there exists at least one element.
Here is the Java implementation of the above algorithm.

Time complexity of this algorithm is O(N log K) as we have N elements in total, and insert and remove-min operation of the priority queue takes O(log k) time.

Saturday, November 2, 2013

Level order traversal of a binary tree

Given a binary tree, we have to print the data level wise. 
For example level order traversal of the following tree produces the sequence 5,3,8,2,4,6,1,7.
The hint to solve this problem is to use a Queue data structure. We start by inserting the root node into the queue. Until the queue is empty, we remove the first element from the queue and insert it's left and right children at the last.

This will give us the level order traversal of the binary tree. For example look at the queue state at each iteration.
5
3,8
8,2,4
2,4,6
4,6,1
...
Here is the C++ program which contains the level order traversal function.

Friday, November 1, 2013

Finding the minimum and maximum elements in a binary seach tree

Given a binary search tree, how do we find the maximum and minimum elements in it?

For example in the given tree, the maximum element is 8 and the minimum element is 1.
This algorithm is based on the following simple observation.
In a Binary search tree, the minimum element always lies on the left most node and the maximum element always lies on the right most node.
Here is the simple implementation of this algorithm in C++.