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


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.


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.


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.


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.

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.

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.

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

 

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

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.