Implement: itoa

I don't know the answer of this question. I could do a guestimate on how such thing would work, but I've never coded c/c++ extensively. Am I useless now? I don't really see how this proves someone has basic knowledge about programming. However I could be wrong and this is a function that c/c++ programmers write on a daily base and is indeed a good indicator if someone ever ran a c++ compiler.

It's not in itself something a C programmer would ever really find themself doing, but as an algorithmic question it's fine - it's testing knowledge of looping, radices, strings etc. In C, you normally have to output the string in reverse and then reverse it, so you need to be aware of that. It's also a problem that's quite easy to explain (programmers are familiar with numbers and strings), but due to it's library availability, most people won't have actually written it themselves so it's not just a case of having done it before.

Coincidentally, I was asked this exact question in a phone interview this week. I didn't have to give exact code, I just walked through the principal of it (loop for each digit, dividing by the radix each time using the leftover specify the character (can be a lookup in an array), possible to use bit shifting in base 2/8/16 situations).

Well, I've written that a handful of times, but those were back when I was an embarrassingly bad programmer. Nowadays, I just use one of the various library functions to do it -- if you count C++, there are somewhere near half a dozen ways. It's a task I perform a lot, but the libraries have it covered.

The very same is true for "sort a linked-list", though, and that seems to be a popular one. This type of question isn't normally asked because they actually expect you to do it, but because if you don't know some specific things, the question will expose that.

Heh, an ex-employer had an even simpler filter we used :-)

We had a 2 page tech test and did read it all, but most of the time we could mark it based on the first question. For a VB+SQL job, most of the candidates couldn't write a valid INNER JOIN statement.

Oops. Bye.

I've done it on my computer. Clearly it works, but without a computer at hand, I am pretty sure I would have made many errors. For example initialize strsize to 1 instead of 0 (in order to add the '\0' at the end of the string).

I believe it is far harder than one could imagine, even more if you are nervous during the interview.

Why not just a binary search. I remember an article claiming 90% of engineer can't write it without bug.

I personnaly asked simply to write a function foo(c,string) (in any language) such that if the string contain the character c, then it returns true. And even with a question as simple as that I had more error I could have imagined.

char itoa(int i) { int strsize; int tmp; char res; int j;

    if (i==0) return "0";

    // allocate the right size
    strsize=0;
    if (i<0) strsize++;
    tmp=i>0?i:-i;
    while (tmp > 0) {
        strsize++;
        tmp /= 10;
    }
    res=(char *)malloc(strsize);

    // write the values
    j=strsize;
    res[j]='\0';
    if (i<0) {
        i=-i;
        res[0]= '-';
    }
    while (i != 0) {
        // printf(".%d(%c)", j, '0'+i%10);
        res[--j] = '0' + i%10;
        i/=10;
    }
    return res;
}

I had to lookup what itoa is not being a C programmer. Which got me interested - how would you implement this?

My inital thought is to do something like (in pseudo code):

    str = '';
    while (i > 0 ) {
      # least significant digit
      r = i % 10;
      # throw away the least significant digit
      i = i / 10;
      case
        when r = 0 then
          str =  '0' << str
        when r == 1 then
          str =  '1' << str
        ... etc
      end
    }
    return str;

Would I pass with that? Is there a better way?

Well, itoa() stands for "integer to ASCII". You can use the property of sequential numbers (starting at 0x30 in ASCII table) to avoid the case statement.

Good point, I actually thought of doing that and then dismissed it. Maybe the best perfoming way would be to use the remainder as the index to an array (suggested in another comment)?

It's C we talking about, just add the remainder to 0x30 and you get your character.

[pedantic]: you should use '0', not 0x30.

1. The standard library C function atoi may be named 'ASCII to integer', but it should convert a numerical string in the platform's encoding to integer. For symmetry, itoa should convert an integer to a platform encoded numeric string, not to an ASCII numerical string.

2. Not all computers use ASCII for C strings. Because of that, '0' need not equal 0x30. For example, in EBCDIC, one has '0' == 0xF0.

Utterly pedantic: IIRC, the C standard guarantees that '0' through '9' are contiguous and in order. If you know better, or aren't sure, use "0123456789"[i] to convert a 0...9 value to the corresponding char.

I used 0x30 for didactic purposes, so that a person less familiar with C would understand what exactly is happening.

I'm a Java person, but I forced myself to implement it in C.

  #include <stdio.h>
  
  int main() {
  	int integer = -1231232342;
  	int negative = integer < 0 ? -1 : 1;
  	integer = integer * negative;
  	char c[11];
  	int index = 0;
  	while(integer != 0) {
  		int position = integer % 10;
  		c[index++] = 48 + position;
  		integer = integer / 10;
  	}
  	if(negative == -1)
  		c[index++] = '-';
  	int swap = 0;
  	while(swap < index / 2) {
  		char t = c[swap];
  		c[swap] = c[index - swap - 1];
  		c[index - swap++ - 1] = t;
  	}
  	printf("%s\n", c);
  	return 10;
  }

I think that becomes a better question if it's in a strange base, like 12. The implementation is exactly the same, but good candidates are not necessarily sitting there thinking "I'd just use sprintf, or maybe a stringstream."