关于node.js:全栈岗位面试算法题-数字输入框校验

起因

最近面试 web 全栈开发工程师 岗位，接触到一个算法题，感觉很考验剖析能力并且在理论中是有肯定作用的算法，因而分享进去跟大家探讨。

题目

依据经营需要，你要为咱们的数值公布零碎减少一项数字输入框校验性能。咱们通常会对一些数字输出进行大小限度。
比方要求输出的值必须在 300 - 347 之间（包含 300 和347）。聪慧的你发现，有时你能够不用等用户输出完就晓得他的输出是否非法的了。
比方，下面这种状况，当用户输出 37 时，必定他的输出就是非法的了。

当初你须要用程序来做这件事。
输出：
第一行为输入框的下界
第二行为输入框的上界
第三行为一些用逗号宰割的整数，这些整数作为用户输出的数字
输入：
仅有一行，为一些用逗号宰割的字符串。
每个字符串对应一个用户输出的数字，如果用户输出为非法则输入INVALID，否则输入VALID

输出束缚
上下界均位于 [1, 2000000000] 之间，且下界小于等于上界，第三行的数字个数位于 [1, 50] 之间，且每个数字也位于 [1, 2000000000] 之间

举例 1：
输出
300
347
37
输入
INVALID

举例 2：
输出
310
320
3,31,317,3174,310,320
输入
VALID,VALID,VALID,INVALID,VALID,VALID
解释：前 3 个是输出 317 时的程序输出，所以都是非法的。最初 2 个时上界和下界，也是非法的

题目剖析

1. 输出大于下限间接返回INVALID
2. 输出在上限和下限之间，间接返回VALID

3. 只有输出小于上限的状况，才会产生校验，因而代码重点在于这一步

   • 下限和上限数字位数相差 1 位以上，比方上限 31 是两位数, 下限 7001 是四位数，因为输出是小于上限 31 的，又因为上上限两头能够蕴含全副的三位数字，三位数字都是符合条件的，因而间接返回VALID
   • 下限和上限数字位数相等的状况，只须要把上上限数字缩短到和输出数字一样的长度（从左边去除），这时输出必须在缩短后的上上限之间，能力返回VALID，否则你在输出之后无论怎么补充数字都无奈保障在上上限之间。

   • 下限和上限数字位数正好相差 1 位的状况

     • 上限首位小于下限首位，比方上限 50，下限618，又因为输出小于50，因而你在输出前面轻易加一位都大于50 小于618，间接返回VALID
     • 上限首位大于等于下限首位，同样把上上限数字缩短到和输出数字一样的长度（从左边去除），这时候你必须保障输出大于等于缩短后的上限，或者小于等于缩短后的下限（此时缩短后的上限 > 缩短后的下限），能力返回VALID，否则你在输出后再次增加任何数字都是不非法的
4. 其余状况，一律返回INVALID

代码实现

const readline = require('readline');
const rl = readline.createInterface(process.stdin, process.stdout);
let min = 0;
let minLen = 0;
let max = 0;
let maxLen = 0;
let strArr = null;
let outputArr = [];
let index = 0;
rl.on('line', function(line) {if (index === 0) {min = parseInt(line);
      if (min < 1 || min > 12000000000) {console.log('输出有误!');
        rl.close();}
      minLen = line.length;
    }
    if (index === 1) {max = parseInt(line);
      if (max < 1 || max > 12000000000) {console.log('输出有误!');
        rl.close();}
      if (min > max){console.log('上界不能小于下界!');
        rl.close();}
      maxLen = line.length;
    }

    if (index === 2) {strArr = line.split(',');
      const len = strArr.length;
      if (len < 1 || len > 50) {console.log('输出有误!');
        rl.close();}

      for (const str of strArr) {const num = parseInt(str);
        if (num < 1 || num > 12000000000) {console.log('输出有误!');
          rl.close();}
        // 大于下限间接返回 INVALID
        if (num > max) {outputArr.push('INVALID');
          continue;
        }
        // 大于等于上限且小于等于下限间接返回 VALID
        if (num <= max && num >= min) {outputArr.push('VALID');
          continue;
        }
        // 小于上限的状况

        // 上上限位数相差 1 以上，间接返回 VALID
        if (maxLen - minLen > 1) {outputArr.push('VALID');
          continue;
        }
        // 上上限位数相等的状况，即 maxLen = minLen;
        const len = str.length;
        const offsetMin = String(min).slice(0, len);
        const offsetMax = String(max).slice(0, len);
        if (maxLen === minLen && str >= offsetMin && str <= offsetMax) {outputArr.push('VALID');
          continue;
        }
        // 上上限位数相差 1 位的状况
        if (maxLen - minLen === 1) {
          // 上限首位小于下限首位
          if (String(min)[0] < String(max)[0]) {outputArr.push('VALID');
            continue;
          }
          // 上限首位大于等于下限首位
          if (str >= offsetMin || str <= offsetMax){outputArr.push('VALID');
            continue;
          }
        }
        
        // 其余状况
        outputArr.push('INVALID');
      }
      console.log(outputArr.join(','));
      rl.close();}
    index++;
}).on('close',function(){
    // It's important to exit, otherwise the execution will time out
    process.exit(0);
});

总结

此代码跑通了测试端全副测试用例并且没有超出响应工夫限度，各位同学能够做个参考，也欢送有其余更好思路的敌人留言分享。