longtail

practicing...

    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 ¨C Pointer to the 2D array
                width ¨C Width of the 2D array
                height ¨C Height of the 2D array
    Output:
                Return value ¨C 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);
    }

    ¡¡

    ¡¡