Tech Puzzle int atoi( char* pStr )

Tech Puzzle int atoi( char* pStr )
Question:Write the definition for this function without using any built-in functions. if pStr is null, return 0. if pStr contains non-numeric characters, either return 0 (ok) or return the number derived so far (better) (e.g. if its “123A”, then return 123). assume all numbers are positive. plus or minus signs can be considered non-numeric characters. in order to solve this program, the programmer must understand the difference between the integer 0 and the character ‘0’, and how converting ‘0’ to an int, will not result in 0. in other words, they have to understand what ascii is all about.
Answer:
string manipulation functions are great programming questions. they test whether the user can understand and translate into code simple algorithms. string functions test pointer arithmetic which usually shows a knowledgeable programmer. also there are usually multiple solutions, some more efficient than others. plus people use them all the time so they should understand how they work. my favorite is atoi and i start the problem like this:
int atoi( char* pStr )
write the definition for this function without using any built-in functions. if pStr is null, return 0. if pStr contains non-numeric characters, either return 0 (ok) or return the number derived so far (better) (e.g. if its “123A”, then return 123). assume all numbers are positive. plus or minus signs can be considered non-numeric characters. in order to solve this program, the programmer must understand the difference between the integer 0 and the character ‘0’, and how converting ‘0’ to an int, will not result in 0. in other words, they have to understand what ascii is all about. if they are stuck solving this problem, just ask them first to write:
charToInt(char c)
if they can’t do that then they basically missed half the problem. any moderately talented programmer who has a CS degree knows how to convert a char to an int. (note i said convert, not cast. charToInt('9') should return 9.)
when they start to solve the problem you will notice that they must make a choice in how they will process the string - from left to right or right to left. i will discuss both methods and the difficulties encountered in each.
“right to left” - this method starts at the right hand letter of the string and converts that character to an int. it then stores this value after promoting it to its correct “tens” place.
int atoi( char* pStr )
{
int iRetVal = 0;
int iTens = 1;
if ( pStr )
{
char* pCur = pStr;
while (*pCur)
pCur++;
pCur--;
while ( pCur >= pStr && *pCur <= '9' && *pCur >= '0' )
{
iRetVal += ((*pCur - '0') * iTens);
pCur--;
iTens *= 10;
}
}
return iRetVal;
}
“left to right” - this method keeps adding the number and multiplying the result by ten before continuing to the next number. e.g. if you had “6234” and you processed from left to right you’d have 6, then if you kept reading you’d multiply your result by 10 (6*10) to add a zero for where the next number would go. 60, and then you’d slide the 2 into the zero place you just made. 62. do it again, 620, slide the next number in, 623.
int atoi( char* pStr )
{
int iRetVal = 0;
if ( pStr )
{
while ( *pStr && *pStr <= '9' && *pStr >= '0' )
{
iRetVal = (iRetVal * 10) + (*pStr - '0');
pStr++;
}
}
return iRetVal;
}
i think the “left to right” method is a little bit cleaner, or maybe its just cooler. but both are “correct”.
remember that debugging code on paper is somewhat hard. most programmers aren’t used to studying code that much when you can just hit F-7, compile and see if the compiler barfs or not. if you notice an error, just ask them to step through a sample string drawing out what is happening with all the variables and the pointers in every step. they should find their mistake then and fix it (no points deducted).

Puzzles: Card Pariology Question

Puzzles: Card Pariology Question
Question: John and Matt decide to play a game using a deck of cards. The game involves flipping two cards at a time. If both cards are black, they go into John’s pile and if both cards are red, they go into Matt’s pile. If one card is red and one card is black, they go into a discard pile. The game is played until all 52 cards have been flipped. The person with the most cards in their pile wins. If there is a tie, John wins. If Matt has more cards than John, then John pays Matt a dollar. What is the chance of Matt getting a dollar?
Answer:Any guesses? The chance of Matt getting any money is zero. Do you know why?
Say the deck is arranged in a way such that there are 13 black pairs. In this situation, John gets 13 black pairs. And since there are no other black cards left, Matt gets 13 red pairs too. So there’s a tie and John wins.
Suppose there are 12 black pairs in the deck. In this case, there would be 2 black cards left in the deck that would pair up with 2 other red cards in the deck. These 2 black cards would never be together since we have already claimed that there are only 12 black pairs in the deck. As a result, 2 pairs of cards end up in the discard pile. The remaining cards would all be red and Matt would get 12 red pairs too. So once again, there’s a tie and John wins.
We could continue this process through induction. Assuming there are 11 black pairs, there would be 4 other black cards that pair up with 4 other red cards and go into the discard pile. Once again, both John and Matt end up with 11 pairs of cards each and John wins.
Here’s a table to explain each case.
John Discarded Matt
13 pairs 0 pairs 13 pairs
12 pairs 2 pairs 12 pairs
11 pairs 4 pairs 11 pairs
10 pairs 6 pairs 10 pairs
9 pairs 8 pairs 9 pairs
8 pairs 10 pairs 8 pairs
7 pairs 12 pairs 7 pairs
6 pairs 14 pairs 6 pairs
5 pairs 16 pairs 5 pairs
4 pairs 18 pairs 4 pairs
3 pairs 20 pairs 3 pairs
2 pairs 22 pairs 2 pairs
1 pair 24 pairs 1 pair
0 pairs 26 pairs 0 pairs

So we see that in any case, there is a tie between John and Matt. So Matt never ends up with a dollar.