Loading...

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

#include

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;
match++;
}
else
{
if ( match)
{
int temp = i+len;
int k = j;
while ( k < length )
{
s[temp] = s[k];
temp++;
k++;
}
length = length -(match*len);
s[length] = '\0';
match = 0;
i +=len;
j =i+len;
}
else
{
i++;
j++;
}
}
}
if ( match)
{
int temp = i+len;
int k = j;
while ( k < length )
{
s[temp] = s[k];
temp++;
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.

"ababcbccc"
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.