Thursday, February 25, 2010

FInd n incresing number of MAX sum

Given a array, find the n increasing number whose summation will be maximum.

Thanks to my friend pallav for asking this.
Certainly its DP, I will post once i am through.

Friday, February 5, 2010

[Tree]..Is parent or grandparent?

There are two nodes given in a tree(not binary tree). Find whether one node
is parent/grand parent of other.
order should be O(1).

tag root as 0 , tag left child as 00 , right child as 01.
left child's left child as 000 , left's child's right child as
001 ... and so on.
let input be tags t1 and t2
if( (t1 == (t2>>1)) || (t2==(t1>>1)))
return child parent relationship
if( (t1 == (t2>>2)) || (t2==(t1>>2)))
return child grand-parent relationship ...

This solution can take a lot of space as the three grows.

We can tag the node by number ..
Root -0
1 -2-3-4

SO given two node get their tags..
Get Max of both t1, t2.
Go for parent of that node if other node then return or check for parent of parent and check again for other node.

With 2^32 value avaialable for indexing ..u wont run out of values.

Thursday, February 4, 2010

Printing Real number Problem

Given an integer say i of size 32.
Now if i mention a fixed point say 12.
We have to convert/treat above integer to a real number.

So From bit 12....31 will form integer part.
and from 0...11 will be after decimal part.

Now the problem is that we have to print this as real value
without any floating point operation and division operation.

My friend, provided this solution.

for bit 11 -> 5^1 * 10^11 = 500000000000
for bit 10 -> 5^2 * 10^10 = 250000000000
for bit 0 -> 5^11 * 10^0 = ...............(calculate the value)
Add all the above value and print as decimal but after a . char.

Monday, January 18, 2010

Least jump to reach array end

Given an array of Integers arr,
from an element val = arr[i], you can go to element i to i+val.
If val is zero, you cannot move forward.
find the least selection to reach end of the array.

example: 1 3 5 8 9 2 6 7 6 8 9
@index 0, can go to 1
@index 1, can go to 4.
if index 3 and 4 choosen, it will reach to end frm there only.

Give an algorithm and program.

This can be solved with greedy aproach.

Assume we are at index i,
So For all i ..to i+a[i] index check for the max value value
of k+a[k], where i
We can prove the correctness of this .

If k+a[k] having maximum value then any value except the k in range of i to i+a[i]
will be less than range reachable by k.
So by choosing k, you still can choose the option available with other indexs.

Merge two sorted array inplace

Given an integer array of which both first half and second half are sorted. Write a function to merge the two parts to create one single sorted array in place [do not use any extra space].
e.g. If input array is [1,3,6,8,-5,-2,3,8] It should be converted to: [-5,-2,1,3,3,6,8,8]

Sunday, January 17, 2010

search in nxn matrix.

We are having a matrix of size nxn, given
rows and column are always sorted order.

Need the fastest algorithm to search an given element.
I am hoping this can be done in O(log n).
Wait for my answer.

Saturday, January 16, 2010

Complete the Tour

Given a circular road and a set of petrol pumps located at distances d1 d2 ... dn away from each other and supplying p1 p2 p3 ... pn amounts of fuel and your vehicle has a mileage of 1km/l. Determine the feasibility of going around the path starting with zero fuel. Find a point from which you can start and complete the cycle given that you have zero initial fuel.

This will be O(n) algorithm.

Start from a random node say i...check till the last node it reach.
Two case:
1: Either it reach to last node. And current node i is result.
2. It stopped at node j.
Then start from node j+1. to find where we can reach all the node by
above algorithm.
No Node from i to j can complete the traversal, because each node will start with 0 petrol. While traversing from i we always reached that node >= 0. So that condition is already checked.

String Cruncher

given a string, remove all repeated consecutive substring with length 1, then delete substring of length 2 and so on...
Example : string is “abcabeccced”

After removing repeated substring of length 1: “abcababceccced” --> “abcababceced” (2 'c' are removed)
After removing repeated substring of length 2: “abcababceced” --> “abcabceced” (substring “ab” is removed)
and so on...


using namespace std;
bool check ( char *s, int st1, int st2, int size)
for ( int i = 0; i le size; i++)
if ( s[st1+i] != s[st2+i] )
return false;
return true;
int main()
char s[15] = "abcababceccced";
int length = strlen(s);
int maxlen = length/2;
int match = 0;
for ( int len = 1; len < maxlen;len++)
int j = len;
int i = 0 ;
while ( j < length)
if (check(s,i,j,len))
j +=len;
if ( match)
int temp = i+len;
int k = j;
while ( k < length )
s[temp] = s[k];
length = length -(match*len);
s[length] = '\0';
match = 0;
i +=len;
j =i+len;
if ( match)
int temp = i+len;
int k = j;
while ( k < length )
s[temp] = s[k];
length = length -(match*len);
s[length] = '\0';
match = 0;
i +=len;
j =i+len;
length = i+len;
s[length] = '\0';
return 0;

I am not sure if above code i written can be simplified, but its working fine.

for size of substring len, two index will be, i at start and second j = i+len.
maxlen is half of total size of strng.
For every size of substring from 1 to maxlen.
match with every possible consecutive match. Count it.
If mismatch then shift this value to previous location.and keep reducing the
lenth of string.

i.e. aababc for size 2.
SO at 1 and 5, we get mismatch, so we move c to location 3. So string changed to aabc
If no match found previously then increment both pointer by one.