我想知道,要求受访者手动将字符串解析为 int 的起源是什么? (不依赖于语言中可能内置的任何强制转换/类型转换)。这是一个标准问题,是从一本书或 list 或其他东西中建议的吗?
SO 上有没有其他人在面试中被问到这个特定问题?我想我在解释它并在白板上潦草地写下它时把它钉牢了,因为我收到了一份暂定的工作机会:)
下面是我用 Javascript 充实的实现。以下内容有一些幼稚的方面(例如,它不采用基数参数),但它展示了一个(或多或少)正确的算法。
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;
}
我也没有被问到这个问题。
乍一看,这似乎是“尽早淘汰明显不称职的白痴,以免浪费宝贵的面试时间”之类的问题。
但是如果你更仔细地观察它,里面实际上有一些非常有趣的东西。所以,如果我是那个问这个问题的人,这就是我要寻找的东西:
- 这个问题显然很愚蠢,因为在 ECMAScript 标准库中已经 了一个函数来做这件事。而且我希望受访者告诉我这个问题很愚蠢,因为否则他们要么 a) 愚蠢的僵尸,愚蠢地遵循脑死亡的命令而不是动用他们的大脑,要么 b) 他们实际上没有知道那个函数存在。
- 这显然也是一个解析问题,有趣的是看看受访者是将其更多地视为字符串破解问题还是形式解析问题,以及这两种方法会产生多少开销。在这种特殊情况下,我相信字符串破解是正确的方法,但它仍然会导致一个很好的后续问题:“现在用递归下降解析器做同样的事情”。任何程序员都应该能够在几分钟内草拟出针对此问题的递归下降解析器。
- 最后但同样重要的是,这显然是字符串字符的折叠。现在,我不一定希望新手程序员自己立即发现这个折叠,但如果我暗示那里有一个折叠,他们应该能够自己发现它,并以折叠的形式重写他们的解决方案.
- 当然,您可以判断此类问题允许您具备的所有一般特征:受访者是停下来思考问题,还是开始胡说八道。他是从需求、文档、规范、示例、测试还是代码开始的?他是否要求澄清极端情况(例如空字符串会发生什么,仅包含减号而没有其他任何内容的字符串会发生什么,空白又如何,字符串是否保证是格式正确的整数,是否为负零一个格式正确的整数)。他是否习惯性地使用 ES5 的严格子集。他是否编写可读代码。他写的是
jslint
友好的代码吗
这是一个用折叠解决问题的例子(在 ECMAScript 中称为 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);
}
这是一个简单的递归下降解析器,可以动态构建值:
"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;
}
与此类面试问题的情况一样,没有人会认真地期望受访者将这些功能写在白板上。特别是递归下降解析器。但恕我直言,任何人都应该能够勾勒出函数的外观。特别是,递归下降解析器的优点之一是它非常直接地将上下文无关文法转换为一组解析函数,受访者应该能够大致解释这种转换是如何工作的,以及什么什么样的解析函数对应什么样的语法结构。
呸,从这样一个简单的问题中可以得到很多的东西!