Programming Problem Solution 2

This post is all about solving a programming problem which I had put in here. The problem 3 of this post is being solved here. The problem is

You r given a large string of characters lets call it Sbig. Then there is a small set of characters lets call it Ssmall. You have to find smallest substring of Sbig which contains all characters in Ssmall.
For example you are given Sbig = “hello what are you doing”
Ssmall= “eo”
answer is “ello”

The idea for the solution to this problem is that we need to find a “window”, in the big string, which contains all the characters in small string. Notice that any such window will start and end at characters which are in small string. Now once we have found such a window, we just set the left most end point of the window at the character which is just right to to and also in the big string. Now we are short of 1 character in the window but still our left and right end points are pointing to characters in small string. Now we advance the right end point until we find that missing character. When we find it, if the current length of window is smaller than previous, we record it. Then again repeat the process.

eg. Sbig : “theryq fanw rtip etug aifge”
Ssmall : “aie”

So, in the above case, “eryq fanw rti” is the first window which we find in the Sbig which has all the characters in Ssmall. Now we set the left end point from ‘e’ to ‘a’ (in ‘fanw’). Now ‘e’ is absent from the window, so we advance the right end point until we find it. We find it at ‘etug’ and also the length of this window is smaller than previous one. Now the solution window is ‘anw rtip e’. Again we shift the left end point from ‘a’ to ‘i’ ( in rtip) and advance the right end point. This way we will find the solution to the problem. Notice that this algorithm runs in amortized O(n).

Now, this was just the idea behind the solution, the game isn’t over yet :P. This solution will only work when the Ssmall does not have repeated characters and the window which we find also does not have repeated characters ( of small string). Just make a small case and figure it out :). So what should be done ??? Well, the idea remains the same, but some other requirements need to be satisfied to keep the algorithms still in O(n). A lot of book-keeping has to be done to maintain the count of all the characters in small string and the window which we find and adjust them accordingly.
The C program which solves it for all the cases.

#include<stdio.h>
#include<string.h>
#include<stdlib.h>

int main()
{
	char Sbig[100000], Ssmall[1000], lookup[256];
	
	scanf("%[^\n] ",Sbig);
	scanf("%[^\n]",Ssmall);
	
	int l_b = strlen(Sbig), l_s = strlen(Ssmall),i,ans_left = 0, ans_right = 0, min = 1<<30, left_anchor = 0, right_anchor = 0, count = 0;
	int lookup_count[256], temp_lookup_count[256], temp_right_anchor;
	
	memset((void *)lookup, 0, 256);
	memset((void *)lookup_count, 0, 256 * sizeof(int));
	memset((void *)temp_lookup_count, 0, 256 * sizeof(int));
	
	for (i = 0 ; i < l_s ; i++) {
		lookup[Ssmall[i]] = '1';
		lookup_count[Ssmall[i]]++;
	}
	// Search for the left anchor to put for the first time
	while (lookup[Sbig[left_anchor]] != '1') left_anchor++;
	count = 1;
	temp_lookup_count[Sbig[left_anchor]] = 1;
	
	// An O(n) loop which implements the algorithm
	for (right_anchor = left_anchor + 1 ; right_anchor < l_b ; right_anchor++) {
		if ( count < l_s && lookup[Sbig[right_anchor]] == '1' ) {
			if (temp_lookup_count[Sbig[right_anchor]] < lookup_count[Sbig[right_anchor]])
				count++;
			temp_lookup_count[Sbig[right_anchor]]++;
		}
		if (count == l_s) {
			if (right_anchor - left_anchor + 1 < min ) {
				ans_left = left_anchor;
				ans_right = right_anchor;
				min = right_anchor - left_anchor + 1;
			}
			temp_lookup_count[Sbig[left_anchor]]--;
			temp_right_anchor = right_anchor;
			if (temp_lookup_count[Sbig[left_anchor]] < lookup_count[Sbig[left_anchor]])
				count--;
			else
				right_anchor--; // This is done to keep the right anchor fixed at its place, for loop will increment it to same value
			left_anchor++;
			while ( left_anchor < temp_right_anchor && lookup[Sbig[left_anchor]] != '1') left_anchor++;
		}
	}
	printf("Min length : %d   : Start : %d  End : %d\n",min, ans_left, ans_right);
	return 0;
}

It is very simple but just the book-keeping has made it look tedious. I’d suggest one should think of how to handle the cases of duplicates, figure out a solution and then compare with my code.

Hope this has been helpful. 🙂

Advertisements

Combination of all characters of a string

A very common questions and a fairly interesting exercise in programming is to develop and implement an algorithm which prints all the combinations of characters in a string, assuming that all the characters are distinct. eg. for input avi, the output should be a,v,i,av,ai,vi,avi.

Almost all of us are aware of the recursive algorithm for this problem and its implementation is also straight forward.
The recursive code which does the job.

#include <stdio.h>
#include <string.h>
#include <stdlib.h>

void mycomb_ultrabad(char const * const s, int l, int *arr, int index, int start, int d)
{
	int i,j;
	if (index >= d)
		return ;
	for (j = start ; j < l ; j++)
	{
		arr[index] = j;
		if (index == d-1)
		{
			for (i=0;i<d;i++)putchar(s[arr[i]]);
			putchar('\n');
		}
		else
			mycomb_ultrabad(s,l,arr,index+1,j+1,d);
	}
	return ;
}


int main()
{
	int i,d;
	char s[100];
	scanf("%s",s);
	d = strlen(s);
	int arr[d+1];
	for (i=0;i<d;i++)
	{
		mycomb_ultrabad(s, d, arr,0,0,d-i);
	}
	return 0;
}

Also, all of us are very aware of the highly recursive nature of this code and hence the intriguing time it takes to complete even for a very small input. Knuth has given a very efficient algorithm in his epic TAOCP which does the job at a very high speed.
The (following) code which implements his algorithm and is very fast indeed.

#include<stdio.h>
#include<string.h>
#include<stdlib.h>


void string_combinations(char * s, int d) {
	int n, j, x, *c;

	if (d <= 0) { puts(s); putchar('\n'); return; }
	if (d >= (n = strlen(s))) return;
	c = (int *)malloc((n + 2 - d)*sizeof(int));

	for(j = 0; j < n - d; ++j) c[j] = j;
	c[j + 1] = 0; x = n;
	do {
		c[j--] = x;
		for(x = 0; c[x] < n; ++x) { putchar(s[c[x]]); } putchar('\n');

		if (j >= 0) { x = j + 1; continue; }
		for(x = c[j = 0] + 1; x == c[j + 1]; x = c[++j] + 1) c[j] = j;
	} while (j < n - d);

	free(c);
}

int main()
{
	int i,d;
	char s[100];
	scanf("%s",s);
	d = strlen(s);
	int arr[d+1];
	for (i=0;i<d;i++)
	{
		string_combinations(s,d-i);
	}
	return 0;
}

When I was in first year at my college, and was introduced to programming, I was given this problem. I had no idea about recursion and the concept of algorithms because it was the first time I was studying computers. So, after some brain-storming I developed a method to solve the problem which did not use recursion (obviously because I didn’t even know what recursion was :P). The code which I had made then worked very fine and was very fast indeed. A few days back I was browsing through the codes I had made and I saw through that code. Well, keeping the algorithm same I implemented the code again, (now being a much better programmer than was then :D) and to my surprise my code beats the Knuth’s implementation by a considerable margin for all inputs. 😀 The following is the code which I recently made. Can you guess the algorithm ??? It was motivated from a very common real life analogy. Try to figure out how it works 🙂

#include<stdio.h>
#include<string.h>
#include<stdlib.h>


void mycomb_optimized(char const * const s, int d)
{
	d++;
	int l = strlen(s);
	int arr[d], j, k;
	for (j=0; j < d; j++) arr[j]=j;
	while ( j >=0  )
	{
		for (j=arr[d-1];j < l ; )
		{
			// print the existing string
			for (k=0;k<d;k++) putchar(s[arr[k]]);putchar('\n');
			arr[d-1] = ++j;
		}
		j = d - 2;k = 2;
		while (j >= 0)
		{
			if (arr[j] + 1 <= l - k )
			{
				arr[j]++;j++;
				break;
			}
			j--;k++;
		}
		while (j >= 0 && j <= d - 1 ) { 
			arr[j]=arr[j-1]+1;
			j++;
		}
	}
	return ;
}


int main()
{
	int i,d;
	char s[100];
	scanf("%s",s);
	d = strlen(s);
	int arr[d+1];
	for (i=0;i<d;i++)
	{
		mycomb_optimized(s, i);
	}
	return 0;
}

I still can’t believe how I could come up with such a nice method to solve the problem..

Programming Problems 9

Found some more questions for you guys 🙂

1. Given a list of points in the plane, write a program that outputs each point along with the three other points that are closest to it. These three points ordered by distance.

2. [Google] Given n elements, sort the elements. Here, only one operation is permitted decreaseValue..
Note that you cannot swap the values.. output should be a sorted list..
if input is 4 5 2 1 3
output is 3 3 3.. There can be many answers.. Give the optimum solution with minimum cost. where as cost is the sum of decreased amounts..
for this example, 4,5 are decreased by 1.. 2 is decreased by 2.. 1 is decreased by 1.

3. Given a string S of alphabets and 2 characters a,b find the minimum distance between instances of them such that position of a <= position of b.

4. Given a string S of words and no of character per line m , with m being greater than the longest word in S, print S in a set of lines so that each line contains no more than m characters and no word split between 2 lines.

5. An array is of size N with integers between 0 and 1024(repetitions allowed). Another array of integers is of size M with no constraints on the numbers. Find which elements of first array are present in the second array.
(If you are using extra memory, think of minimizing that still, using bitwise operators)

6. [Google] Describe an algorithm that takes an unsorted array of axis‐aligned rectangles and returns any pair of rectangles that overlaps, if there is such a pair. Axis‐aligned means that all the rectangle sides are either parallel or perpendicular to the x‐ and y‐axis. You can assume that each rectangle object has two variables in it: the x‐y coordinates of the upper‐left corner and the bottom‐right corner.

7. [Google] Given an n x n grid with a person and obstacles, how would you find a path for the person to a particular destination? The person is permitted to move left, right, up, and down.

8. Given a long string and a given word find out how many times you can write that word using subsets of the string. (i.e., you can create "dog" with "doom dogged" 8 times.

Solution to Dynamic Programming Problems

In an earlier post I had given a set of Dynamic Programming problems which are a must do for every person interested in programming. I would like to share the solutions of them today. This is a link to all those problems and their solutions. The solutions are in swf format and can be viewed in the web browser.

I would suggest one should try to solve them first hand and go to the solutions only after digging deep enough 🙂

Rabin Karp String Search Algorithm

I came across the Rabin–Karp string search algorithm when I was looking for a method to implement strstr as a C program. The obvious brute-force method was a waste, so I found the Rabin-Karp, Knuth-Morris-Pratt Algorithm and Boyer-Moore Algorithm . The KMP is hectic to understand and code as well but Boyer-Moore is very practical and can be coded quickly. I had less time so coded only the Rabin-Karp Algorithm.
The code which I had made.

#include<iostream>
#include<string>
#include<vector>
#include<cmath>

using namespace std;

int main()
{
	string T, P;
	cin >> T;
	cin >> P;
	long long int PRIME = atoll("10002949999");
	int l_T = T.length(), l_P = P.length(), t=0, h = 1, d = 26, H = 0;
	for (int i=1; i < l_P; i++)
		h = (h * d) % PRIME;
	for (int i=0;i<l_P;i++)
	{
		H = ( (d*H)  + P[i] - 'a')%PRIME ;
		t = ( (d*t)  + T[i] - 'a')%PRIME ;
	}
	for (int i = 0, j = l_T - l_P - 1 ; i < j ; i++)
	{
		if (t == H)
		{
			int state = 1;
			for (int k = 0 ;k < l_P; k++)
				if (T[i+k] != P[k])
				{
					state = -1;
					break;
				}
			if (state == 1 )
			{
				cout << " Match found at index : " << i << "\n";
			}
		}
		else
		{
			t =  ( (d * (t - h*(T[i]-'a')) + T[i+l_P] - 'a')%PRIME );
		}
	}
	return 0;
}

The algorithm can be found on wiki, I had used the pseudo-code from CLRS.

nth Fibonacci Number

I was in the test run of a programming contest just a couple of days back and there was this good old problem of finding out the nth Fibonacci Number. But the constraints were tight (upto 10^9) and the number of test cases were also high ( ~100). Well I knew that the conventional DP solution of O(n) won’t work, still I tried and got the TLE :P. Out of the shackles of laziness, I went out to code the O(log(n)) version of calculating the nth Fibonacci Number. The method to do it is very simple, the recurrence is
Fibonacci Number - I
Fibonacci Number - II

I used recursion and coded it. Interestingly, I got TLE again 😦 . When I ran the code on my system it was very slow for high values. Any Guesses why ??? 😀 Think it over 🙂
Anyways, I figured out immediately why it was slow and then used the good old technique of Memoization to code the same solution with slight modification. This time it got accepted 🙂
The code which I made.

#include<stdio.h>
#include<string.h>
typedef long long LL;

int mem[5000000];

LL fib(LL n) {
	if ( n == 1 )
		return 1;
	if ( n == 2 )
		return 1;
	if (n & 1 ) // odd 
	{
		LL t1, t2, t3;
		if ((n+1)/2 < 5000000 && mem[(n+1)/2] != 0 )
			t1 = mem[(n+1)/2];
		else {
			t1 = fib( (n + 1)/2)%10007;
			if ( (n+1)/2  < 5000000) 
				mem[(n+1)/2] = (int)t1;
		}
		if ((n+1)/2 - 1 < 5000000 && mem[(n+1)/2-1] != 0 )
			t2 = mem[(n+1)/2-1];
		else {
			t2 = fib( (n + 1)/2-1)%10007;
			if ( (n+1)/2 -1 < 5000000) 
				mem[(n+1)/2-1] = (int)t2;
		}
		return ((t1*t1)%10007 + (t2*t2)%10007)%10007;
	}
	else {
		LL t1, t2, t3;
		if ((n)/2 < 5000000 && mem[(n)/2] != 0 )
			t1 = mem[(n)/2];
		else {
			t1 = fib( (n )/2)%10007;
			if ( (n)/2  < 5000000) 
				mem[(n)/2] = (int)t1;
		}
		if ((n)/2 - 1 < 5000000 && mem[(n)/2-1] != 0 )
			t2 = mem[(n)/2-1];
		else {
			t2 = fib( (n)/2-1)%10007;
			if ( (n)/2 -1 < 5000000) 
				mem[(n)/2-1] = (int)t2;
		}
		if ((n)/2 + 1 < 5000000 && mem[(n)/2+1] != 0 )
			t3 = mem[(n)/2+1];
		else {
			t3 = fib( (n)/2+1)%10007;
			if ( (n)/2 +1 < 5000000) 
				mem[(n)/2+1] = (int)t3;
		}
		return (((t2 + t3)%10007)*t1)%10007;
	}
}

int main()
{
	int t;
	memset((void *)mem,0,5000000*sizeof(int));
	long long int n;
	scanf("%d",&t);
	while (t--) {
		scanf("%lld",&n);
		if ( n == 1) { printf("1\n"); continue;}
		if ( n == 2) { printf("2\n"); continue;}
		printf("%lld\n",fib(n+1));
	}
	return 0;
}

It was good that I coded it, because nowadays people are not satisfied with the good old O(n) DP method :P. They want the O(log(n)) code. I remember a company at our campus asked a guy to do it, the interviewer helped him a lot but he couldn’t answer it. Nice practice to do actually 🙂

Programming Problem Solution 1

Change of plan. I figured, giving out questions is getting boring now. 😦 Above that noone has asked any doubt regarding any question. Either my blog is read only by me or the people who read my blog are too intelligent :D. Anyways, for a change I decided to solve a problem for you in this post. So, what can be a better problem/concept to provide to you than Dynamic Programming . So here is a problem which I have solved using dynamic programming and now I will show you the steps and code for the same.

The problem can be found here.

I chose this problem because it is a very good example of a problem where a Greedy Algorithm seems to be sufficient but it’s not :). Now any standard textbook will provide you a decent enough background on how to go about solving a problem using DP. Following their legacy, I first propose to you to think of a recurrence relation for this problem and confirm to yourself whether that relation is valid or not.

I hope you have tried, if you have found it, awesum, if not, don’t worry I have the solution for you. The following program which solves the problem using the recurrence relation. It’s a recursive code, so obviously it’s uber low :). You can figure out the recurrence relation easily from the program. I hope you’ve got the idea of the solution. Now, the job is not done yet, we need to improve upon the solution.

#include<stdio.h>
#include<stdlib.h>

int N = 0, *arr;

int max(int a,int b)
{
	return a>b?a:b;
}

int fun(int day, int start, int end)
{
	if (day > N)
		return 0;
	return max(fun(day+1,start+1,end) + day*arr[start],fun(day+1,start,end-1) + day*arr[end]);
}

int main()
{
	scanf("%d",&N);
	arr = (int *)malloc(sizeof(int)*(N+1));
	int start,end,day,i;
	for (i=1;i<=N;scanf("%d",&arr[i]),i++);
	start = 1;end = N;day = 1;
	printf("%d\n",fun(1,1,N));
	return 0;
}

The next step found in any standard textbook is to use Memoization. So we’ll do the process here too. You should find a way to store the precomputed results and use them for further calculations. Hope you will code it. The program which uses memoization for this problem. Have a look at it. Hope you get the idea :).

#include<stdio.h>
#include<stdlib.h>

int N = 0, *arr;
int **table;

int max(int a,int b)
{
	return a>b?a:b;
}

int fun(int day, int start, int end)
{
	if (day > N)
		return 0;
	if (start >= end && table[end][start] != 0)
		return table[end][start];
	if ( start+1 <= N && table[start+1][end] == 0 )
		table[start+1][end] = fun(day+1,start+1,end);
	if (end-1 >= 0 && table[start][end-1] == 0 )
		table[start][end-1] = fun(day+1,start,end-1);
	return max(table[start+1][end] + day*arr[start],table[start][end-1] + day*arr[end]);
}

int main()
{
	scanf("%d",&N);
	arr = (int *)malloc(sizeof(int)*(N+1));
	table = (int **)malloc(sizeof(int *)*(N+2));
	int start,end,day,i,j;
	for (i=0;i<=N+1;i++)
	{
		*(table+i) = (int *)malloc(sizeof(int)*(N+2));
		for (j=0;j<=N+1;j++)
			table[i][j]=0;
	}
	for (i=1;i<=N;scanf("%d",&arr[i]),i++);
	start = 1;end = N;day = 1;
	printf("%d\n",fun(1,1,N));
	return 0;
}

Now is the time To Play THE GAME . It’s DP time :). The last nail in the coffin??? We’ll see. Well by now you will have had an idea of how you are going to program this as a DP solution. Great !! go ahead. For newbies, try out. The DP code for this. Do notice the sizes of the codes I am providing, see how they change 🙂

#include<stdio.h>
#include<stdlib.h>

int max(int a,int b)
{
	return a>b?a:b;
}

int main()
{
	int N;
	scanf("%d",&N);
	int arr[N+1],i,j, table[N+1][N+1],tmp=0;
	for (i=1;i<=N;scanf("%d",&arr[i]),i++);
	for (i=1;i<=N;i++)
		table[i][i] = arr[i] * N;
	for (i=1;i<N;i++)
	{
		tmp++;
		for (j=1 ;j+tmp <= N;j++)
			table[j][j+tmp] = max(table[j+1][j+tmp] + arr[j]*(N-tmp), table[j][j+tmp-1] + arr[j+tmp]*(N-tmp) );
	}
	printf("%d\n",table[1][N]);
	return 0;
}

Now what ?? Is the game over ??? Not yet, for geeks, the memoization and DP solution will get uploaded on spoj, but to get to the best timing, you still have to do something special. Think about how this code can be optimized. Notice the way the table is being filled by the DP solution and which part of the table is being used to fill an entry in the table. Take some time to think. Just a hint, it can be done in O(N) space only :). The following is my solution which is among the best which has been uploaded. It’s really fast :P. Analyze this, the pattern how the table has been filled was exploited to use only O(N) space rahter than O(N^2) space.

#include<stdio.h>
#include<stdlib.h>

int max(int a,int b)
{
	return a>b?a:b;
}

int main()
{
	int N;
	scanf("%d",&N);
	int arr[N+1],i,j,table[N+1],tmp=0;
	for (i=1;i<=N;scanf("%d",&arr[i]),i++);
	for (i=1;i<=N;i++)
		table[i] = arr[i] * N;
	for (i=1; i < N; i++)
	{
		tmp++;
		for (j=1;j <= N-i ;j++)
			table[j] = max(table[j+1] + arr[j]*(N-tmp), table[j] + arr[j+tmp ]*(N-tmp));
	}
	printf("%d\n",table[1]);
	return 0;
}

Hope you geeks had a good time.

Do post comments for anything or just compliments 😛

%d bloggers like this: