javascript - 递增整数序列

Question

在面试中，我被要求找到以下算法问题的答案。

假设你得到一个递增整数的短输入，比如“2 4”，你能算出 4 后面是什么整数吗？如果你假设第二个整数比第一个大+2，那么下一个整数应该是6；但是如果你假设第二个整数是第一个整数的两倍，那么下一个整数可能是 8。但是，如果短输入是“2 4 8”，那么你几乎可以确定下一个整数是 16。

简而言之，你得到的数字越多，你可以消除的假设就越多。我们希望您用 Javascript 编写一个程序。请明确说明您想使用哪一个。该程序将递增整数的简短列表作为输入，假设整数中可能的模式，并生成接下来的 10 个整数。

例如，如果程序接收到以下输入: 4 14

程序可能假设下一个整数是前一个整数加 10，因此它会生成:

24 34 44 54 64 74 84 94 104 114

但是如果程序收到以下输入: 4 14 34

然后它可以假设下一个整数是前一个整数乘以 2 加 6。

74 154 3314 634 1274 2554 5114 10234 20474 40954

这是我们提出的一个开放式问题，换句话说，整数的输入列表可能具有非常有趣的属性(例如斐波那契数列)，没有特定的集合我们正在测试的整数序列。所以，要有创意!尝试识别尽可能多的序列。

---

你如何解决这个算法？

Answer 1

这是对疯狂的刺痛，因为今天是星期五，而且很有趣哈哈。 我写了 3 个 tests 很容易添加更多。让我知道你的想法。

function doubleLast(seq) {
  this.seq = seq;
  this.display = 'Double the last number';
  this.match = (seq) => seq.every((v, i) => (i > 0) ?  v === seq[i-1]*2 : true);
  this.nextValue = (seq) => seq[seq.length-1]*2;
}

function simpleAdd(seq) {
  const addNum = (seq) => seq[1] - seq[0];
  this.seq = seq;
  this.display = 'Add a single number';
  this.match = (seq) => {
    // subtract initial value from the second
    return seq.every((v,i) => (i > 0) ? v === seq[i-1]+addNum(seq) : true);
  };
  this.nextValue = (seq) => seq[seq.length-1]+addNum(seq);
}

function divideAddMod(seq) {
  const modifier = (seq) => seq[1] - (seq[0]*2);
  this.seq = seq;
  this.display = 'Try to divide by 2, then add Mod';
  this.match = (seq) => {
    // subtract initial value from the second
    return seq.every((v,i) => (i > 0) ? v === (seq[i-1]*2)+modifier(seq) : true);
  };
  this.nextValue = (seq) => (seq[seq.length-1]*2)+modifier(seq);
}

const algos = [new doubleLast(), new simpleAdd(), new divideAddMod()];

document.addEventListener('click', (e) => {
  if(e.target.matches('button')) {
    let seq = document.querySelector('input').value.split(' ').map(e => parseInt(e));
    algos.forEach(a => {
      let possibleMatch = a.match(seq);
      if(possibleMatch) {
        console.log(`Match found ${a.display} - Next value ${a.nextValue(seq)}`);
      } else {
        console.log(`${a.display} did not match`);
      }
    });
  }
});

<input type="text"></input>
<button>Work It out</button>
<p>Suppose you get a short input of increasing integers, say, "2 4", can you figure out what integers come after 4? If you assume the second integer is +2 greater than the first, then the next integer should be 6; but if you assume the second integer is double the first integer, then perhaps the next integer is 8. However, if the short input was "2 4 8", then you can almost be sure that the next integer is 16.

In short, the more numbers you get, the more hypotheses you can eliminate. We would like you to write a program, in Javascript. Please clearly indicate which one you would like to use. The program takes in a short list of increasing integers as inputs, hypothesize possible patterns in the integers, and generate the next 10 integers in line.

For instance, if the program receives the following input: 4 14

the program may assume that the next integer is the previous integer plus 10, thus it will generate:

24 34 44 54 64 74 84 94 104 114

but if the program receives the following input instead: 4 14 34

then it may hypothesize that the next integer is the previous multiplied by 2 plus 6.

74 154 3314 634 1274 2554 5114 10234 20474 40954

This is an open-ended problem that we're presenting, in other words, the input list of integers may have very interesting properties (e.g. a fibonacci sequence), there is no particular set of integer sequences that we are testing. So, be creative! try to identify as many sequences as you can think of.</p>