## Saturday, January 29, 2011

### Lexicographically smallest string

Given a group of strings, find a string by concatenating all the strings in any order which produces the lexicographically smallest string.
For e.g strings are acc bcc abb
So the string formed should be abbaccbcc

Approach:

By looking at the problem the most quick and easy solution seems to sort the strings and concat them.
But wait, will it really work?
Lets say, strings are aba and ab
With the above approach the solution would be ababa
But infact there exists a lexicographically smaller string and that is abaab.

So what went really wrong? Take a minute to think it through and how to overcome it.

## Sunday, January 23, 2011

You are provided with four possible operations that can be done on the editor(each operation requires 1 keyboard hit)

1. A
2. Ctrl+A
3. Ctrl+C
4. Ctrl+V
Now you can hit the keyboard N times and you need to find the maximum number of A's that can be printed. Also print the sequence of keyboard hits.

Approach:

Its trivial to have the observation for n <= 6, the max number of A's = n
How about n = 7? If you computed the answer as 8 or 9, open an editor and type the sequence and validate the answer. This is a common gotcha thinking that Ctrl + A, Ctrl + C, Ctrl + V would double the characters but it doesn't :). Infact the characters remains intact while the next Ctrl + V would infact copy the same sequence.

Further thoughts, can you arrive at an optimal number which you can go ahead and copy over and over, or you need a calculated strategy where you refresh your clipboard with current contents. Once you are able to identify this, you should be able to arrive at a proper formative answer

## Saturday, January 22, 2011

### Merge two sorted arrays

Given two sorted arrays A and B with X and Y elements. The array A has X+Y space. Now merge array A and B in the array A with minimum number of steps and without using any auxiliary array space.

Approach:

A = {7, 9, 14, 19, _ , _, _, _, _}
B = {4, 12, 17, 18, 23}

So, the final configuration should be
A = {4, 7, 9, 12, 14, 17, 19, 23}

The simplest naive approach comes from the concept of the insertion sort, compare iteratively successive elements of array B to the elements in array A and if it is greater, then move all the elements in A by one position forward from that index and insert the element B in the current position. Code is left as an exercise to the reader.

## Friday, January 21, 2011

### Find the second largest number in an array

Given an array of integers find the value of 2nd largest element in minimum number of comparisons.

Approach

Well its trivial to prove that the lower bound of the algorithm will be O(n) (Since the array is unordered so we need to scan the values atleast once to figure out the solution)

What can be the possible solutions?

### Number of digits

Given a positive number n find the number of digits in factorial n. 'n' can be very large (may be 10^4) so consider the case of the overflow.

Approach:
Lets analyse how we can find the number of digits in any give number
If the given number is x = 10^y (x being an integer and y being a float)
The number of digits = floor(y) + 1
So y = log10(x)

Now to find the number of digits in n!, we need to find the
y = log(n!) = log(1*2*3*4.......*n) = log(1) + log(2) + log(3) + ......+ log(n)

## Sunday, January 16, 2011

### Number of pairs whose sum equals k

You have an integer array and a number k, find all the pairs of numbers from the array whose sum is equal to k.
What will be the approach if the numbers in the given array are sorted and unsorted?

Approach:
There are myraid number of approaches to attack this problem.
Lets take the case when the array is already sorted.
One of the approaches can be to iterate over each element let say a[i] = x, then we need to figure out if a number k - x exists or not in the array

We can very well search for the element in the array in O(n) making the overall complexity O(n^2).
But wait, since the array is already sorted we could have just performed a binary search over the array to search a given element.
This reduces the overall complexity to O(n*logn)

Can we improve the approach?
Well, there is an important observation that if we pick the two extreme indexes of the array and sum it up, there are 3 possibilities

1. Sum is equal, bingo :)
2. Sum is less than the target k,
3. Sum is greater than target k

For the case 2, if there exists a pair, it has to be achieved by increasing the sum, i.e by moving the left index ahead.
For the case 3,  if there exists a pair, it has to achieved by decreasing the sum, i.e by moving the right index behind.
For the case 1, you can move any index.
Following the above approach you can figure out all the possible combinations.

So how about the time complexity?
Each element is accessed only once, hence the overall complexity turns out to be linear O(n)
Below piece of code just does the job

```void printPairs(int *arr, int n, int k) {
if (n < 2)
return;
int front = 0, back = n - 1;
while (front < back) {
if (arr[front] + arr[back] == k) {
cout << front << " " << back << endl;
if (back > 0 && arr[back - 1] == arr[back]) back--;
else front++;
} else if (arr[front] + arr[back] < k) {
front++;
} else {
back--;
}
}
}```

In case the array is not sorted?
Well we can sort the array in O(nlogn) and then apply one of the above approaches, the overall complexity would be O(nlogn)

But is it necessary to sort?
If you have the luxury, you can easily push the elements in the hash, and then look for each element x, if there exists an element k - x?
Safely assuming the Insertion and lookup complexity of the hash implemention to be O(1), the overall complexity of the algorithm would be O(n)

## Tuesday, January 11, 2011

### Binary array !!!

Given an array of 0's and 1's. only, find the maximum length of the subarray such that the number of 0's and 1's in that subarray are equal.

## Sunday, January 2, 2011

### Maximum sub array revisited !!!

Given an array of positive numbers, find the maximum sum of a subsequence such that no 2 elements in the sequence should be adjacent in the array.
For e.g
For an array  3 2 5 10 7 function should return 15

Approach:

If we figure out all the combinations in which no two elements are adjacent and pick the maximum sum, our job would be done.
A simple recursive algorithm would perform the job

```int maxSum(int *a, int size, int idx, int sum) {
if (idx >= size)
return 0;
return max (maxSum(a, n, idx + 1), a[idx] + maxSum(a, n, idx + 2));
}```

But wait how about the complexity? The order would be equal to number of combination processed, which would be exponential in nature.

So how do we reduce it? If we observe carefully many of the subproblems are repeated and computed over and over (To gain more insight on the repeating subproblems refer this link).
Indeed it is a dynamic programming problem and storing the results of the subproblems would improve the complexity considerably.

Below is short snippet code for the same

```int maxSum(int *a, int size, int idx, int sum) {
if (idx >= size)
return 0;
if (mem[idx + 1] == 0)
mem[idx + 1] = maxSum(a, n, idx + 1);
if (mem[idx + 2] == 0)
mem[idx + 2] = maxSum(a, n, idx + 2);

return max (mem[idx + 1], a[idx] + mem[idx + 2]);
}
```