A. First Edition

Some problems comes from "topcoder" and some are from interview companies.

B.The problem

　

C.The idea of program

　

                        

D.The major functions

.

E.Further improvement

F.File listing

1.question1

2.question2

3.question3

4.squaredigits

filename: question1.cpp

Problem 1: findMaxReverse

Create a function using one of the following prototypes:

C++:     int findMaxReverse (const int *array, int length);
            -or-
Java:    int findMaxReverse (int array[]);

This function should return the size of the largest sub-array which also appears in reverse order somewhere in the array.  The array will 

always have less than 10000 elements.

For example:

findMaxReverse ({4,1,2,3,0,7,3,2,1}) returns 3 (the largest sub-array is {1,2,3})
findMaxReverse ({8,6,1,9,8,1,6}) returns 2 (the largest sub-array is {6,1})

/////////////////////////////////////////////////

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



int doFindMaxReverse(const int* array, int length)
{
	int result=0;
	
	for (int i=0; i<length/2; i++)
	{
		if (array[i]!=array[length-i-1])
		{
			break;
		}
		else
		{
			result++;
		}
	}
	return result;
}


int findMaxReverse (const int *array, int length)
{
	int result=1, temp;
	for (int i=0; i<length; i++)
	{
		//shrink the array to find
		for (int j=0; j<length-i; j++)
		{

			temp=doFindMaxReverse(array+i, length-i-j);
			if (temp>result)
			{
				result=temp;
			}
		}
	}
	return result;
}


void question1Test()
{
	int array[9]={4,1,2,3,0,7,3,2,1};
	int length=9;
	//int array[7]={8,6,1,9,8,1,6};
	//int length=7;


	printf("result=%d\n", findMaxReverse(array, length));
}

void question1RandomTest()
{
	int*array;
	int length;
	length=rand()%10+6;
	array=new int[length];

	for (int i=0; i<length; i++)
	{
		array[i]=rand()%20;
		printf("%d,", array[i]);
	}

	printf("\nresult=%d\n", findMaxReverse(array, length));
	delete[] array;
}



int main()
{
	srand(time(0));
	question1Test();
	for (int i=0; i<20; i++)
	{
		question1RandomTest();
	}
	return 0;
}

filename: question2.cpp

Problem 2: findPath

We have a 2D integer array filled with the values 0 and 1.  0 represents a ground tile and 1 represents a wall.  We can only walk up,

 down, right or left on ground tiles.

Create a function to determine whether a path exists from the top-left corner of the array (0, 0) to the bottom-right corner (width-1,

 height-1).

C++:     bool findPath (const int *array, int width, int height);
-or-
Java:    boolean findPath (int array[], int width, int height);

Input:
            array – Pointer to the 2D array
            width – Width of the 2D array
            height – Height of the 2D array
Output:
            Return value – true if a path exists, false otherwise

For example, given the array:

001011110
100001100
010000011
110001000
111011100

The function would return true.

///////////////////////////////

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



bool* path;


bool doFindPath(const int* array, int width, int height, int x, int y)
{
	//boundary condition
	if (x<0||x>=width||y<0||y>=height)
	{
		return false;
	}
	//successful
	if (x==width-1&&y==height-1)
	{
		return true;
	}

	if (path[y*width+x])
	{
		return false;
	}
	//test current
	if (array[y*width+x]==1)
	{
		return false;
	}
	path[y*width+x]=true;

	//recursive
	if (doFindPath(array, width, height, x+1, y))
	{
		return true;
	}
	if (doFindPath(array, width, height, x-1, y))
	{
		return true;
	}
	if (doFindPath(array, width, height, x, y+1))
	{
		return true;
	}
	if (doFindPath(array, width, height, x, y-1))
	{
		return true;
	}
	//if none successful return false
	return false;
}





bool findPath (const int *array, int width, int height)
{
	//quick test
	if (array[height*width-1]==1)
	{
		return false;
	}
	path=new bool[width*height];
	for (int i=0; i<width*height; i++)
	{
		path[i]=false;
	}
	

	return doFindPath(array, width, height, 0, 0);
}

void printArray(int* array, int width, int height)
{
	for (int i=0; i<height; i++)
	{
		for (int j=0; j<width; j++)
		{
			printf("%d,", array[i*width+j]);
		}
		printf("\n");
	}
	printf("\n");
}


void question2RandomTest()
{
	int* array;
	int width, height;
	width=rand()%10+1;
	height=rand()%10+1;
	array=new int[width*height];
	for (int i=0; i<width*height; i++)
	{
		array[i]=rand()%2;
	}
	if (findPath(array, width, height))
	{
		printf("yes\n");
	}
	else
	{
		printf("no\n");
	}

	printArray(array, width, height);
	delete[]array;

}



void question2Test()
{
	int array[]=
	{
		0,0,1,0,1,1,1,1,0,
		1,0,0,0,0,1,1,0,0,
		0,1,0,0,0,0,0,1,1,
		1,1,0,0,0,1,0,0,0,
		1,1,1,0,1,1,1,0,0
	};
	int width=9;
	int height=5;
	if (findPath(array, width, height))
	{
		printf("yes\n");
	}
	else
	{
		printf("no\n");
	}
}






int main()
{
	question2Test();

	for (int i=0; i<30; i++)
	{
		question2RandomTest();
	}

	return 0;
}

filename: question3.cpp

Problem 3: findMaxSplit

We have an integer array which we’d like to split into a sequence of consecutive sub-arrays.  The sum 

of the values contained in each sub-array should be the same.

Create a function to find the maximum possible number of such sub-arrays in the given input array.

C++:     int findMaxSplit (const int *array, int length);
            -or-
Java:    int findMaxSplit (int array[]);

The array will always have less than 10000 elements.

For example:

findMaxSplit ({1,2,3})                            returns 2  (sum=3, sub-arrays: {1,2}, {3})
findMaxSplit ({1,2,3,6,12,8,4,3,3,3,3})  returns 4  (sum=12, sub-arrays: {1,2,3,6}, {12}, {8,4}, {3,3,3,3})
findMaxSplit ({1,2,6,30})                       returns 1  (can’t be split)
findMaxSplit ({1,2,3,4,2})                      returns 2  (sum=6, sub-arrays: {1,2,3}, {4,2})

/////////////////////////////////////////

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


bool doFindMaxSplit(const int* array, int len, int target, int current, int& counter)
{
	if (len==0)
	{
		//successful condition
		return current==0;
	}

	if (current+array[0]==target)
	{
		//find match, recursion
		counter++;
		return doFindMaxSplit(array+1, len-1, target, 0, counter);
	}

	if (current+array[0]<target)
	{
		//continue
		return doFindMaxSplit(array+1, len-1, target, current+array[0], counter);
	}
	//busted
	return false;
}

		

int findMaxSplit (const int *array, int len)
{
	int result=1, target=0;
	int counter;
	if (len<=1)
	{
		return 1;
	}


	for (int i=0; i<len-1; i++)
	{
		counter=1;
		target+=array[i];
		if (doFindMaxSplit(array+i+1, len-i-1, target, 0, counter))
		{
			if (counter>result)
			{
				result=counter;
			}
		}
	}
	return result;
}


void question3Test()
{
	//int array[3]={1,2,3};
	//int length=3;

	//int array[11]={1,2,3,6,12,8,4,3,3,3,3};
	//int length=11;

	//int array[5]={1,2,6,30};
	//int length=5;
	
	int array[5]={1,2,3,4,2};
	int length=5;
                    

	printf("result=%d\n", findMaxSplit(array, length));
}


void question3RandomTest()
{
	int* array;
	int length;
	length=rand()%100+1;
	array=new int[length];
	for (int i=0; i<length; i++)
	{
		array[i]=rand()%20;
		printf("[%d]", array[i]);
	}

	printf("\n result=%d\n", findMaxSplit(array, length));
	delete[] array;

}


void test()
{
	for (int i=0; i<20; i++)
	{
		question3RandomTest();
	}
}


int main()
{
	question3Test();

	return 0;
}

filename: squaredigits.cpp

/*
Problem Statement
????
***Note:  Please keep programs under 7000 characters in length.  Thank you


Class Name: SquareDigits
Method Name: smallestResult
Parameters: int
Returns: int

Define the function S(x) as the sum of the squares of the digits of x.   
For example: S(3)=3*3=9 and S(230)=2*2+3*3+0*0=13.

Define the set T(x) to be the set of unique numbers that are produced by
repeatedly applying S to x.  That is: S(x), S(S(x)), S(S(S(x))), etc... 
For example, repeatedly applying S to 37:
S(37)=3*3+7*7=58.  
S(58)=5*5+8*8=89.
S(89)=145.
S(145)=42. 
S(42)=20.
S(20)=4.
S(4)=16.
S(16)=37. 
Note this sequence will repeat so we can stop calculating now and: 
T(37)={58,89,145,42,20,4,16,37}.
However, note T(x) may not necessarily contain x.  

Implement a class SquareDigits, which contains a method smallestResult.  The
method takes an int, n, as a parameter and returns the smallest int, x, such
that T(x) contains n.

The method signature is (be sure your method is public): 
int smallestResult(int n); 

TopCoder will ensure n is non-negative and is between 0 and 199 inclusive.

Examples:
If n=0: S(0) = 0, so T(0)={0}, so the method should return 0.

If n=2: T(0) through T(10) do not contain the value 2.  If x=11, however:
S(11)=1*1+1*1=2, so T(11) contains 2, and the method should return 11.

If n=10: T(0) through T(6) do not contain 10.  If x=7:
S(7)=49.
S(49)=97.
S(97)=130.
S(130)=10.
S(10)=1.
and it starts to repeat... 
so T(7) is {49,97,130,10,1}, which contains 10, and the method should return 7.

n=1 -> x=1 
n=19 -> x=133
n=85 -> x=5
n=112 -> x=2666
Definition
????
Class:
SquareDigits
Method:
smallestResult
Parameters:
int
Returns:
int
Method signature:
int smallestResult(int param0)
(be sure your method is public)
????

This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this 

information without the prior written consent of TopCoder, Inc. is strictly prohibited. (c)2003, TopCoder, Inc. All rights reserved.
*/


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

using namespace std;
const int MaxNumber=200;
class SquareDigits
{
typedef set<int> IntSet;
typedef map<int, IntSet> SetMap;
typedef map<int, int> IntMap;

private:
	IntMap squareTable;
	SetMap setTable;
	
	int calcSquare(int number);
	bool calcSet(int number, int current);
	
public:
	int smallestResult(int param);
};

int SquareDigits::smallestResult(int param)
{
	int i=0;
	while (true)
	{
		if (calcSet(i, param))
		{
			break;
		}
		i++;
	}
	return i;
}


bool SquareDigits::calcSet(int number, int target)
{
	IntSet::iterator it;
	IntSet mySet, subSet;
	pair<IntSet::iterator, bool> result;
	SetMap::iterator setMapIt;
	int current=number;
	int squareDigit;
	while (true)
	{
		squareDigit=calcSquare(current);
		if (squareDigit==target)
		{
			return true;
		}
		setMapIt=setTable.find(squareDigit);
		if (setMapIt!=setTable.end())
		{
			subSet=setMapIt->second;
			for (it=subSet.begin(); it!=subSet.end(); it++)
			{
				mySet.insert(*it);
			}
			break;//we find the subset and can quit
		}
		
		result=mySet.insert(squareDigit);
		if (!result.second)
		{
			//it converges
			break;
		}
		current=squareDigit;
	}
	setTable.insert(make_pair(number, mySet));
	return false;
}
				
		

int SquareDigits::calcSquare(int number)
{
	int modulo, remainder=number;
	int sum=0;
	IntMap::iterator it;
	it=squareTable.find(number);
	if (it!=squareTable.end())
	{
		return it->second;
	}
	while (remainder!=0)
	{
		modulo=remainder%10;
		sum+=modulo*modulo;
		remainder/=10;
	}
	squareTable.insert(make_pair(number, sum));
	return sum;
}


int main()
{
	int result, input=10;
	SquareDigits mySqr;
	result=mySqr.smallestResult(input);

	printf("%d=%d\n", input, result);
	return 0;
}

///////////////////////////////

//the following are something I want to find in case there is a coding test for me. :)

#include <stdio.h>

struct Link
{
	int value;
	Link* next;
};

void reverseLink();

void displayLink(Link* list);

void createLink(Link*& list, int length);

Link* findTail(Link* list);

void swapLink(Link* startParent, Link* endParent)
{
	Link* startSon, *endSon, *temp;
	if (endParent==NULL)
	{
		return;
	}	
	startSon=startParent->next;
	endSon=endParent->next;
	startParent->next=endSon;
	endParent->next=startSon;
	temp=endSon->next;
	endSon->next=startSon->next;
	startSon->next=temp;
}

void doReverseLink(Link*& startParent, Link*& endParent)
{
	if (endParent==NULL)
	{
		return;
	}
	
	
	if (endParent->next->next==NULL)
	{	
		swapLink(startParent, endParent);
		if (startParent->next!=endParent)
		{
			startParent=startParent->next;
		}		
		return;
	}
	doReverseLink(startParent, endParent->next);

	swapLink(startParent, endParent);
	if (startParent->next!=endParent)
	{
		startParent=startParent->next;
	}		
}

void swapDouble(Link* grandPa)
{
	Link* sonNext, *father, *son;
	
	sonNext=grandPa->next->next->next;
	father=grandPa->next;
	son=father->next;

	grandPa->next=son;
	son->next=father;
	father->next=sonNext;
}
	

	


void createLink(Link* list, int length)
{
	Link* current=list;
	for (int i=0; i<length; i++)
	{
		current->next=new Link;
		current->next->value=i;
		current=current->next;
	}
	current->next=NULL;
}


void displayLink(Link* list)
{
	Link* current=list;
	while (current!=NULL)
	{
		printf("[%d]", current->value);
		current=current->next;
	}
	printf("*****************\n");
}


void reverseLink()
{
	Link head, *start;
	head.next=NULL;
	head.value=-1;
	createLink(&head, 6);
	displayLink(head.next);
	start=&head;
	doReverseLink(start, head.next->next);
	displayLink(&head);
}




int main()
{

	reverseLink();
	return 0;
}

void reverseList(char* str);


//void doReverse(char* start, char* stop);

void swapPtr(char* first, char* second)
{
	char temp;
	temp=*first;
	*first=*second;
	*second=temp;
}


char* getFence(char* head)
{
	if (*(head+1)=='\0')
	{
		return head;
	}
	else
	{
		return getFence(head+1);
	}
}
//at least length=3
void doReverse(char*& target, char*& head, char*& fence)
{
	if (head==fence)
	{
		return;
	}
	else
	{		
		head++;
		doReverse(target, head, fence);
		if (target>=head)
		{
			return;
		}
		swapPtr(target, head);		
		target++;
		head--;		
	}
}


void reverseList(char* str)
{
	char* fence=NULL, *start=str, *head;
	printf("before reverse=%s\n", str);
	fence=getFence(str);
	head=start+1;
	
	doReverse(start, head, fence);
	printf("after reverse=%s\n", str);
}

void reverseListDemo()
{
	char buf[80];
	sprintf(buf, "12345");
	reverseList(buf);
}