What's the origin of asking interviewees to manually parse a string as an int? [closed]

Question

I'm wondering, what's the origin of asking interviewees to manually parse a string as an int? (without relying on any casting/type-conversion that may be built into the language). Is this a standard question, suggested from a book or list or something?

Has anybody else here on SO gotten asked this particular question during an interview? I guess I nailed it when explaining it and scribbling it on the white board, as I have received a tentative job offer :)

Below is my fleshed out implementation in Javascript. There are some naive facets (e.g. it doesn't take a radix argument) to the following but it demonstrates a (more or less) correct algorithm.

function to_i(strValue) { //named so as to not be confused with parseInt
    if (typeof strValue !== 'string' || strValue.length === 0) {
        return Number.NaN;
    }

    var tmpStr = strValue;
    var intValue = 0;
    var mult = 1;

    for (var pos=tmpStr.length-1; pos>=0; pos--) {
        var charCode = tmpStr.charCodeAt(pos);
        if (charCode < 48 || charCode > 57) {
            return Number.NaN;
        }

        intValue += mult * Math.abs(48-charCode);
        tmpStr = tmpStr.substr(0, tmpStr.length-1); 
        mult *= 10;
    }

    return intValue;
}

Answer 1

I haven't been asked this question, either.

At first glance, it seems like one of those "weed the obviously incompetent idiots out as early as possible to avaid wasting valuable interview time" type of questions.

But if you look at it more closely, there's actually some quite interesting stuff in there. So, if I were the one asking that question, here's what I would be looking for:

• That question is obviously stupid, because there already is a function in the ECMAScript standard library that does exactly that. And I would want the interviewee to tell me that the question is stupid, because otherwise they are either a) mindless zombies that stupidly follow braindead orders instead of engaging their brain, or b) they don't actually know that that function exists.
• It's also obviously a parsing problem, and it is interesting to see whether the interviewee approaches it as more of a string hacking problem or a formal parsing problem and how much overhead either approach generates. In this particular case, I believe that string hacking is the right approach, but it still leads into a great followup question: "Now do the same thing with a recursive-descent parser". Any programmer should be able to sketch out the recursive-descent parser for this problem within a couple of minutes.
• Last but not least, this is obviously a fold over the characters of the string. Now, I would not necessarily expect a novice programmer to spot this fold on their own right away, but if I hint that there is a fold in there, they should be able to spot it themselves, and rewrite their solution in form of a fold.
• And of course, you can judge all the general qualities that this type of question allows you to: does the interviewee stop and think about the problem or does he start hacking away. Does he start with requirements, documentation, specification, examples, tests, or code. Does he ask for clarification of the corner cases (like what happens with the empty string, what happens with a string that only contains a minus sign and nothing else, what about whitespace, are strings guaranteed to be well-formed integers, is negative zero a well-formed integer). Does he habitually use the strict subset of ES5. Does he write readable code. Does he write jslint-friendly code

Here's an example of solving the problem with a fold (which in ECMAScript is called reduce):

"use strict";

function toInteger(s) {
    return s.split('').reverse().reduce(function (n, c, i) {
        if (c === '-') return -n;
        return n + (c.charCodeAt(0) - 48) * Math.pow(10, i);
    }, 0);
}

And this is a simple recursive-descent parser which builds up the value on the fly:

"use strict";

function toInteger(s) {
    var input,
        output = 0,
        sign = 1,

        lookahead = function () {
            return input.charAt(0);
        },

        consume = function () {
            var res = input.slice(0, 1);
            input = input.slice(1, input.length);
            return res;
        },

        isDigit = function (c) {
            return /[0-9]/.test(c);
        },

        signParser = function () {
            if (lookahead() === '-') {
                sign *= -1;
                consume();
            }
        },

        digitParser = function () {
            if (!isDigit(lookahead())) return false;
            output *= 10;
            output += (consume().charCodeAt(0) - 48);
            return true;
        },

        numberParser = function () {
            signParser();
            while (digitParser());
        };

    input = s;
    numberParser();
    if (!input.length === 0) return false;
    output *= sign;

    return output;
}

As is always the case with this kind of interview questions, nobody would seriously expect the interviewee to just write those functions down on the whiteboard. Especially the recursive-descent parser. But IMHO, anybody should be able to sketch out what the function would look like. In particular, one of the beauties of a recursive-descent parser is that it is a very direct transformation of a context-free grammar into a set of parsing functions, and an interviewee should be able to explain roughly how that transformation works, and what kind of parsing functions correspond to what kind of grammar constructs.

---

phew, that is a lot of stuff that you can get out of such a simple question!

Answer 2

They wanted to test your math knowledge, because many "code monkeys" did not receive proper math education.

A number that is expressed in digits $d_1 d_2...d_n$ can be written in this form: $d_1 r^(n - 1) + ... + d_(n - 1) r^1 + d_n$, where r is the radix.

That means, 123 in decimal = $1 * 10^2 + 2 * 10^1 + 3$ while 123 in octal is $1 * 8^2 + 2 * 8^1 + 3$ = 83

function to_i(str, rad) {
  // the function to transform an ascii code into a number value
  function dig(c) {
    if (c >= 48 && c <= 57) {
      // 0 - 9: as-is
      return c - 48;
    } else if (c >= 97 && c <= 122) {
      // a - z: a means 10, b means 11 and so on until z
      return 10 + c - 97;
    } else {
      return Number.NaN;
    }
  }

  // validate arguments
  if (str == '' || rad < 2 || rad > 35) return Number.NaN;
  // strip extra characters and lowercase ("$10" -> "10")
  var result = str.toLowerCase().match(/^.*?(-?)([a-z0-9]+).*?$/);
  // break on empty numbers
  if (result == null || !result[2]) return Number.NaN;
  // get sign multiplier
  var sign = (result[1] == '-' ? -1 : 1), val = result[2], num = 0;
  // num = dv_0 * rad ** n + dv1 * rad ** (n - 1) + ... dv_n * rad ** 0
  //  where dv_n = dig(val.charCodeAt(i))
  //  and a ** b = a * ... * a, b times
  // for each digits
  for (var i = val.length - 1, m = 1; i >= 0; i --, m *= rad) {
    // get digit value
    var dv = dig(val.charCodeAt(i));
    // validate digit value (you can't put 5 in binary)
    if (dv >= rad || num == Number.NaN) return Number.NaN;
    // multiply
    num += m * dv;
  }
  // return 
  return num * sign;
}

to_i("ff", 16);

This one supports radixes, a means 10, b means 11 and so on until z. Hope this works.