Given only putchar (no sprintf, itoa, etc.) write a routine putlong that prints out an unsigned long in decimal.

Here is one of the questions from Microsoft interview.

It’s obvious that you can use the modulus operator (%10) and loop thru the digits one-by-one. Since n%10 gives you only the last digit, you need to somehow store it in a temporary array. I am sure the interviewer will not be too pleased with this and ask you to rethink again without using temporary storage.

The key is to think recursively. Recursion is very powerful and is able to solve this question easily. In fact, it is often used in conjunction with pointers to weed out candidates. Read this article on how Microsoft conduct interviews to get what I mean. Think of recursion as the allocation of a stack… Push the last digit onto the stack, then continue with the 2nd last, …, up until the first digit. Then when the function pops off the stack, you get the digit in the correct order. Voila!

You will probably attempt something like this at first try:

1 2 3 4 5 6 |
void putlong(unsigned long n) { if (n == 0) return; putlong(n / 10); putchar(n % 10 + '0'); } |

Guess what’s wrong?

You forgot to consider the special case when n == 0!

The above code can be modified to handle the special case of n == 0:

1 2 3 4 5 6 7 8 |
void putlong(unsigned long n) { if (n < 10) { putchar(n + '0'); return; } putlong(n / 10); putchar(n % 10 + '0'); } |

Great! Now you are able to think recursively 🙂 Here is another similar question that often pops up in a job interview:

Print a string in reverse order.

1 2 3 4 5 6 |
void printReverse(const char *str) { if (!*str) return; printReverse(str + 1); putchar(*str); } |

Reversing linked-list can be done recursively too. Can you figure out how to do it? Find out how in my next post.

Recursion to the rescue!,
Thanks for the code on recursion. I always have a headacre about it. 🙁

And thanks for the link provided, which let me have a glimpse on what the interviewer is thinking about.

0Hi, 1337:

Today, I am flipping the good old bible – The C Programming Language by K&R, for the implementation of quicksort function. As you know, it is implemented recursively.

Another glimpse let me catch another recursive example presented in the book before qsort.

—

4.10 Recursion

C functions may be used recursively; that is, a function may call itself either

directly or indirectly. Consider printing a number as a character string. As we

mentioned before, the digits are generated in the wrong order: low-order digits

are available before high-order digits, but they have to be printed the other way

around.

There are two solutions to this problem. One is to store the digits in an

array as they are generated, then print them in the reverse order, as we did with

i toa in Section 3.6. The alternative is a recursive solution, in which printd

first calls itself to cope with any leading digits, then prints the trailing digit.

Again, this version can fail on the largest negative number.

#include

/* printd: print n in decimal */

void printd(int n)

{

if (n < 0) {

putchar (' -' ) ;

n = -n;

}

if (n / 10)

printd(n / 10);

putchar(n % 10 + '0');

}

When a function calls itself recursively, each invocation gets a fresh set of all

the automatic variables, independent of the previous set. Thus in

printd(123) the first printdreceives the argument n = 123. It passes 12

to a second printd, which in turn passes 1 to a third. The third-level printd

prints 1, then returns to the second level. That printd prints 2, then returns

to the first level. That one prints 3 and terminates.

—

It is dealing almost the same problem as the M$ interview problem. And it seems the textbook solution has handled the case where n == 0.

Isn't it?

0Yup, you are right. It has handled the case where n == 0. This code is also more elegant without the repeated section in my example code. The conditional statement “if (n / 10)” is equivalent to “if (n >= 10)”.

+2Nevertheless, they have a bug. When n is INT_MIN

n = -n

will again generate INT_MIN.

0I checked the book.

In limits.h they define the magnitude of min and max limits of the signed integral types the same. So, the code is OK within the book’s limits.

However, in platforms I have came across, the magnitude of the min is 1 more than max.

0In flipping the K&R bible, I happened to find another solution to the string-reverse problem.

Using the code in Section 3.5:

#include

/* reverse: reverse string s in place */

void reverse(char s[])

{

int c, i, j;

for (i = 0, j = strlen(s)-1; i 1) {

/* Reverse the rest of the string. */

reverse(s + 1);

/* Put the first character at the end. */

c = s[0];

for (i = 1; i < l; i++)

s[i – 1] = s[i];

s[l – 1] = c;

}

}

This is extracted from http://www.bamsoftware.com/computers/tcpl-answers.html.

0putlong can easily cause stackoverflow!!!

0Limit for the unsigned long is 4294967495 which is 11 digits.

So needed stack space is only sizeof(unsigned long) * 11 bytes at most.

0(correction) Limit for the unsigned long is 4294967295.

0Above code wont produce the reverse of the digits…

I think the code should be like this…

void putlong(unsigned long n) {

if (n < 10) {

putchar(n + '0');

return;

}

putchar(n % 10 + '0');

putlong(n / 10);

}

please correct me if I am wrong…

+2Pingback: putlong | 口├人人│의 Blog

Pingback: Printing a Binary Tree in Level Order | 口├人人│의 Blog

I don’t get it what’s the difference using an array and recursion? They both use O(n) space.

+1I wonder too

0maybe it doesn’t use array explicitly, that make the code neat..who knows~~

0バッグ トート ブランド

+1