practicing...
A. First Edition
Some problems comes from "topcoder" and some are from interview companies.
¡¡
.
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); }
¡¡
¡¡