斐波那契数列 n = 9292 的结果是什么？

[CookCoder]

面试了一个远程公司，第一题是写一个斐波那契数列的实现，这个没有任何难度，反正是不写递归就行

但是第二题是用自己写的第一题的答案运行 n = 9292

因为每注注意 n = 9292

所以第一题实现的时候比较粗暴，第二题运行结果当然是无穷大

后来进行调整，其实很简单，力扣有题目

var fib = function(n) {
    const MOD = 1000000007;
    if (n < 2) {
        return n;
    }
    let p = 0, q = 0, r = 1;
    for (let i = 2; i <= n; ++i) {
        p = q; 
        q = r; 
        r = (p + q) % MOD;
    }
    return r;
};

持续 % 1000000007 的结果就出来了 随后又实现一下不 % 1000000007 的结果 结果太庞大了，肯定不是，否则太侮辱出题人了

BUT ，对方公司就是要这个庞大的结果 我现在道心崩了

[CookCoder]

所以在面试题没有明确需要 % 1000000007 的时候，面对这样的结果，我们是给出原答案，还是 % 1000000007

[CookCoder]

3661577246222677849785427206834745690320353572157656330500188244468089715055226822525574623888694874292151478596700484435570305109242313638033416669900444112247937728056211966758992460916419400444853615065999542615995870540182204923636128338003036402195497269318979305499067555417877218451841325150147307183407898442574610940236693637649259016140512151236060436731993551961323374694640088413329540217958532844994602127372986462480164986085899739239682944787995424271277467745382889616543410488579354418782072284268830659992928815496582634474475467254601183355700504643184963095650659016150303753725509080657414720402415839227967445769423409681729197862582729971824872388906214839490412361238387557198107844877079017174320960353286125955686041797566600910089428824579522915583067121845203670580431109038026031805366693865811657549114645180029223550684370620385942139952513596212989572901717566991028950391641339313551358249513768853983555921365314930744269060528453180853181277008706114560211720676164926069583198482669740034992505014190676786182619356298288614973174512790036679389133495600521574725844129972742430674736916672792625084641027990733249739459326440313013672649848254315756846997118764723139178365862765173488978551301801196364660097159749216505812815610240094570434388330501001490260829493982079774109976313795867953293232350445141140986017144615285056571297189775579577943476017486485426114739433921822640390808840316534298381708300360202292556716275696050116179146218599102060641783728510620700368611020522308508805066354267983031447439708738430830812299369590938039288063873607175095253952963248468206808754647017090147700831859035388796576278194027465866101615940691728994129932120206390739814141511226049882323886861245940252446697607680362853010694832168189803235002515372695099765714174685776789816323408545017065365758342146429980816094007713959447619038393467627366903822647919125618219011528539949951357869642550538579

[CookCoder]

上面是不 “优化” 的结果

[si]

var fib = function(n) {
if (n < 2) {
return n;
}
let p = 0n, q = 0n, r = 1n;
for (let i = 2; i <= n; ++i) {
p = q;
q = r;
r = (p + q);
}
return r;
};

你的算法改一下就可以了

[CookCoder]

@si 我不是寻求算法解答的，而是面对这么庞大的结果，到底要不要优化一下

[si]

@CookCoder 题目是要这一项的结果，那就给他们这一项的结果。
优化之后的结果都不一样了，那在没有要求优化的时候就不应该优化。

[murmur]

你在问什么，考点是什么，看了一下不实现很常规吧，快速矩阵解法真不会，我还以为靠 BigInt 的实现，题目不是明确告诉 mod 计算么

[hertzry]

还以为你要全部的数列，想了半天怎么发出来。

[air8712]

1, 不说让 mod 就不 mod
2. n <= 200 时候 int64 就不够用了
3. 用大整数即可
4. 用矩阵 + 快速幂，复杂度可以降到 logn

[hello2090]

@CookCoder 啥叫优化？结果不是一个数字吗？还能怎么优化？

[jiezhi]

纸上谈兵地说一下，做第一题的时候就要问清楚输入条件吧，以及超过 int 范围怎么处理之类的。
有些题看起来简单，但更多地是看你的沟通能力以及对细节的把控能力。
---
当然这些都是我从书上看到的。

[CookCoder]

@hello2090 答案要在他们的 PDF 上编辑，但是给的空格大小，看看我上面写的答案，我就复制进去 5 行而已，所以也许我想的太多了，认为既然给给么小的空白，肯定不是输入完整的答案，应该进行 MOD

[hello2090]

@CookCoder 面试题是他们出的，有不清楚的当然是问他们先。。

[hello2090]

@CookCoder 当然你可以按照你想的方法做，但如果人家想的和你想的不一样责任就在你自己了，你用 xxxx7 mod 别人希望你用 xxxx9 呢万一

[CookCoder]

@hello2090 我问了搞算法的博士朋友，这个题目是他们出的有问题，如果 n 不进行限制，那么需要给出内存限制，如果什么都不给出，默认需要 MOD 1000000007 ，这个数字不是随意的，也是属于共识，如果需要 MOD ，肯定都是 1000000007

[lakehylia]

long 整不了，就用 BigInt ，用循环不用递归来解的话，又不吃内存。无非是一个 O(n)的算法。

[lance6716]

面试的时候，沟通也是考察的一环

[CookCoder]

@hello2090 给我面试题目的是对方公司的 HR ，并且给出面试题目以后，就算开始，时间，是否有提问，准确率等等。

所以如果我对这个地方有疑问，结果还不是对方有错误，是我理解问题，那么就扣分了

[Perry]

你这是在线面试还是 take home 面试？在线面试难道不是得问考官 constraints 或 clarifying question 吗？

[hello2090]

@CookCoder 那就按你博士朋友来，要是失败了，对方公司就是 sb 呗。你有啥困惑的？