斐波那契数列 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 ，对方公司就是要这个庞大的结果 我现在道心崩了

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

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

我先入为主认为对方出的算法题目没有问题，结合给与留出用于写答案的留白

不可能写那么长的结果

不过以后长记性了，把一切可能都提问到

------

写一个 n 不限制的斐波那契，我还是游刃有余的

我只是面对这么长的结果，我肯定会 MOD ，我也以为其他人也是默认 MOD

现在对方告诉我不需要，我就要原答案

我现在有点崩道心而已

我怀疑自己是不是 “错了” ？

果然解答算法题目的时候，出题要想全面，解答的时候要问全面，我就是想太多了

致所有杠精，少来抬杠，我不是你爹，不会惯着你，少谈什么友好发言。

[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 呗。你有啥困惑的？

[CookCoder]

@lance6716 远程面试，给题目以后就无沟通了，而且运气很差，对方是才毕业一个月的新手，后期沟通答案的时候，她转述程序员的解释，差点让我信仰崩塌。

她说因为我没有 MOD

我？

过了一会说要的是原答案

我？？

那你给我的空白也不够把原答案复制进去啊

[Aoang]

建议直接放弃，不用太在意。

之前远程电话面试某厂，人都是拿着面试题随便挑着问的，都能听到翻页的声音。如果你回答的不是纸上的答案，就说你回答的不对。问题在于还有宏观题…

面试到一半，给我整一句，你简历上写的完全都不会，然后把电话挂了。

面试体验最差的一次

[fds]

……没听说过取模还有什么共识的。你换几个别的数字会有什么问题呢？
我个人理解，这题考点就是时间复杂度和类型的取值范围。时间复杂度别递归就行。取值范围你要用 python 实现，就不用做什么特殊处理，因为 python 支持大整型。用 js 的话，要不就用 bigint ，要不就自己写个数组分段计算，不然 float64 会丢精度。
面试给 pdf 应该也不用在 pdf 上编辑吧？肯定要提供程序代码吧？我觉得面试主要看代码，至于答案，只要是算法对，应该无关紧要。

[masterclock]

1000000007 挺常用，但也没到共识的程度

面试的时候，给了问题，只做，不提疑问，我一般是扣分的

[CookCoder]

@masterclock 我之前因为提问，反而扣分，这个真是看缘分了

[zhandi4]

BigInt 加矩阵快速幂，他就没啥可挑剔的了。题目没有说取 mod 的话，还是没必要先入为主去取，或者说把自己的疑问去沟通一下。事后来看就不用去纠结了，这面试体验太差了，面试也是相互选择的。

[ipwx]

我觉得沟通需求也是程序员重要的基本技能。楼主这就属于沟通技能极差

[littlewing]

要不要 mod 你直接问 HR 不就行了，你再这里问有啥用

[CookCoder]

@zhandi4 他们说我错了，我坚持认为没有错，我要一个解释，然后说我没有 MOD ，可是我的代码里明确进行 MOD ，对方又说需要原答案，所以，真的是一个让我恼火的面试，也是一次体验很差劲的面试。


@ipwx 我只是认为在国内很基本的面试题，没有必要去提问，至于是否沟通能力差劲，仁者见仁智者见智吧。

[CookCoder]

@littlewing 因为一直以为大数值答案是默认 MOD 的，根本不需要提问

[ipwx]

“我只是认为在国内很基本的面试题”

我觉得坚持这个认知没错，这件事情就说明沟通技能差了。（

[CookCoder]

@ipwx 那我感觉您可以和那个因为我提问，反而扣分的面试官进行沟通一下，他说面试题就是考察你所有想到的点，把所有可能都解答到位就 OK ，所以提问当然减分。

所以面试这么多次以后，遇到疑惑，到底提问还是不提问，因为我怎么选择都遇到扣分的情况。

所以这个我感觉和沟通能力什么的都没有任何关系，就是看面试官而已。

[iDontEatCookie]

这么垃圾的面试体验就别找自己的问题了吧？

[jmc891205]

面试不是考试，更像相亲，有时候就是会因为一些莫名其妙的原因被拒（对候选人对公司来说都是）

[mainjzb]

我觉得。。。这个面试很有效。。。证实了这个部门和你真的不合（逃

[jmc891205]

不过就此题来说
如果我是面试官 候选人问我要不要取模或者主动就取模了
那我后面会避免和他讨论 Leetcode 原题了 hhh

[CookCoder]

@jmc891205 我之前也不知道取模，最开始面试的时候，我甚至是递归去回答，经过几轮面试官的教育，才知道有什么动态规划，MOD 等等。

[fds]

面试又不是考试，没有标准答案。不同面试官有不同解读很正常。招人的岗位不同对答案的侧重也有不同。你非得争对错，就比较“学生气”。何况面试也是你选择对方的一个过程，如果对方主管或者工作方式你不喜欢，那就不要强求。

至于取模，十年前考察 C 语言并且是 easy 难度的题目，那一般会提示你取模。难一点的都可以要求你用数组模拟计算出来。现在主流语言基本都支持大整型了，所以直接要精确结果也正常。基本功在面试初级岗位时还是挺重要的。

@CookCoder 你能回答我如果这道题用 js 编写，可以取模，但一定要精确结果，这个取模运算中被除数的最大值是多少吗？我从你之前的回复里感觉你不清楚这个答案。那么对方公司给你扣分也无可厚非。扣分的点不一定是你提问了，而是你的提问暴露出一些知识漏洞。

[CookCoder]

@fds 这个有统计过，有被 MOD 过的被除数有 4658 个，最大的是 1999128362

[encounter2017]

也算是经单老题了

https://zhuanlan.zhihu.com/p/144597328

[ytmsdy]

LZ 不要太过于自闭了，这属于面试官水平不行。
如果我是面试官，第一题算是入门，第二题会问如果 N=1000 的结果，然后再引导 N=10000 结果是什么。
这么运行会不会有什么问题，看面试者的回答，看是怎么优化一下还是有什么其他实现方式。
面试其实是为了看面试者的思考逻辑，和解决问题的方法，以及知识面的情况。

[encounter2017]

n < 2 的时候直接返回，不太对吧。。。
前几项是 1, 1, 2, 3, ...

[CookCoder]

@encounter2017 是从 0 开始的

[Mutoo]

想起之前 jetbrains 夺题游戏第三关，算 fib[50_000_000] 的时候写过。用的分治法 O(n) = log(n) ，需要 js runtime 支持 big int ，另外用 memorize 作了简单优化：

https://blog.mutoo.im/2020/03/jetbrains-quest-session-1-episode-3/#Stage-4

[CookCoder]

@Mutoo 我喜欢这个问题，这个很有考点，谢谢分享

[CookCoder]

@ytmsdy 因为是远程面试，直接发过来一个 PDF ，我也是第一次参与这种形式的面试，和我对接的也不是技术，是一个 HR ，如果是一个技术，我可以很放松的进行提问，但是根据之前的沟通，这个 HR 可能互相转述疑问和解答，都很费劲。

[UIXX]

这不是算法结果优不优化的问题，甚至跟问什么都没关系。

面试官作出的解释让我想起了以前学生考试的“多选选错扣分”的多选题，其中的内涵是应试者有条件地作出应对策略，这种机制用来面试应聘者的技术水平不合适。

一个好的面试官应该要为应聘者提供足够的“容错”，专注于“找缺点”的面试官，要么招聘动机不纯，要么自己是不专业的外行人。落选了没什么好可惜的。

[fds]

@CookCoder 啊，对不起，我问题说错了，不是被除数，是除数，就是你说的 % 1000000007 这里，用比 1000000007 大的数，在 js 下最高能大到多少，能让你给出的代码返回一个精确结果。

[learningman]

高精度呗。。。没说让你取模你凭啥敢取模啊，万一是 998244357 呢

[lervard358]

BigInteger

[efaun]

有没有可能这是对方故意留的坑? 就看你会不会考虑全面, 对应的是做需求前有没有充分沟通

[CookCoder]

@efaun 那就真感觉多余了

[flyhelan]

% 1000000007

[flyhelan]

% 1000000007 有什么用？

[sockball07]

@flyhelan #54 刚好也直接 google 了一下 1000000007 https://www.zhihu.com/question/49374703

[vance123]

无非是考察长整数嘛，大不了用字符串写一个

[lovestudykid]

不 mod 考察啥呢，难道考察你会不会用 bigint?

[CookCoder]

@lovestudykid 我也以为 MOD 是考点，但是我想多了，人家就是要那么大的数字，我自己还非要 MOD 一下，多余的操作，应该直接复制一张 A4 纸的答案，扔给他们。

[Daiwf]

你想多了，就是开发太忙了没高兴来面，找了个 HR 来凑数。结果就把你纠结了

[ffgrinder]

@CookCoder 我觉得是你想太多。

能开起来公司并不一定就是有实力，可能是爹比较有钱。 我最近感受可太深了。

从我个人来说，如果你说明白了你 MOD 1000000007 ，我会怀疑你可能作弊（因为我没要求，你没沟通，默认用了 leetcode 的题解），那加试就行了。

对方这个沟通水平也挺一般的，换家公司好了。

[dany813]

碰到菜鸡面试官 没办法

[FrankHB]

1000000007 ？凭什么不是 100000007 ？
面试体验是垃圾，但是要我遇到没事瞎脑补 MOD 1000000007 这种无中生有的二缺“共识”而不是会主动沟通的候选者，就默认刷掉，撑死进复活区。
说白了，需求描述不清可行性明显有问题就是 bug ，遇到 bug 就报，这做项目和做算法题都一样。什么做题的“共识”那么有排面凌驾于这种常识上了？
（我当年闲着刷 ZOJ 的时候哪来的这种脑补，人比赛去也都是再三强调读懂题意。是最近几年卷多了就想欺负面试官不懂“规矩”么。）

[adoal]

求职不是求知。沙雕的公司 /面试官 /HR 很多，没必要非要咽不下一口气要个说法。尤其是这种涉及惯例达不成默契的人为因素，自己有数知道自己没问题就行了。

[CookCoder]

@FrankHB 只能说这是国内和国外的区别？但是我问了一些国外的朋友，他们遇到这样超大数字的结果，也是 MOD ，至于为啥是 1000000007 ，楼上有回答，请您自己谷歌一下。

如果是 F100 ，我都可以给出原答案，但是 F9292 ，面试公司还要原答案，我现在也不纠结了，可能就是出题的人也不清楚这个结果有多大，或者出题的人不专业，才死活要原答案。

[CookCoder]

@adoal 是的，只是当初他们质疑我结果是错的，我需要一个说法，为何错了。

结果他们最开始说我的结果没有 MOD ，我就请他们查看一下源码，最后又说是转述错误，不需要 MOD 。

就是要那么长的原答案，我就质疑对方，清楚这个结果的长度么？

清楚给出的答案留白哪怕用最小号的字，也复制不下。

对方就不说话了，我就直接去找对方的 CTO 反馈了，我说这就是你们对待面试的态度？

[CookCoder]

@ffgrinder 但是他们最开始说我错误的原因是没有 MOD （后来沟通初步审核答案的是 HR ，只知道用固定的结果去对，我的代码和他手里的正确答案有逻辑差异，就说我错了），我说请再看源码，最后又改口说，不需要 MOD ，就是要结果。

但是他 A4 纸给的答案留白很小。

算了，不纠结

[ffgrinder]

@CookCoder 对 你知道他们水平不行，那还纠结啥，恶心公司多了去了。

[qwertyegg]

@CookCoder

有点中小学数学基础就不会说出“这个数字不是随意的，也是属于共识，如果需要 MOD ，肯定都是 1000000007”

这样的话

[CookCoder]

@qwertyegg ?? 所以呢？

[CookCoder]

@qwertyegg 发个言只有把所有的点都描述到位才没有杠精出来抬杠么？

https://www.bilibili.com/video/BV1G3411b7uB?from=search&seid=16163315209011790087&spm_id_from=333.337.0.0

看这个视频的简介，微博日娃知道么，现在说话都是一堆（防止杠精）

免得浪费大家直接，我直接把 UP 的简介发一下

伴奏来源网络，黑卫衣黑外套是俺本人
太燃叻太燃叻，陈奕迅老师真的太强了！！
看了一点双城之战的片段，感觉解说老师们配音都蛮有趣的，怪好玩滴
歌•绑住手不会唱歌•蛙•小秃头•瓜
防爆：
100 人+的大教室，非自习室，晚上九点之后才赶去拍视频，没有使用或破坏教学设备，整层楼都黑黢黢没有人，上面一层也没有人，下面一层楼有在楼道外练舞的同学，教学楼不临寝室不临图书馆，没有打扰到其他同学，拍完视频之后也关灯了，赶着教学楼关门时间出来的，没有惹管理员麻烦
（升 8key≠高八度，8key 是 4 个全音＝ 8 个半音，八度是 6 个全音＝ 12 个半音，没学过音乐，是搜出来的，如果不对可以指正，我会虚心学习的呜呜呜）
最后，三连的宝贝都是我的小蛋糕（玫瑰

就是你们这群自以为是的人，在那里咬文嚼字，好不容易看到一个以为自己可以彰显优越感的角度就蹬鼻子上脸地抬杠，送你这样的人一个字。

滚！滚！滚！

[clf]

遇到这种笔试 /面试确实很蛋疼。

记得之前字节的笔试，最后结果是返回一个 map ，然后没说明以哪种情况对输出排序，最后 HashMap 、LinkedHashMap 、TreeMap 都试了一遍才过程序检测。

[aguesuka]

摸摸, 不哭, 下次怼回去, 不要受网友气了

[liuidetmks]

哈哈,你以为人家考你快速幂,实际上人家考你大数乘法的存储和实现

[yazinnnn]

为什么前端会问这种问题？

[CookCoder]

@yazinnnn 国外的公司几乎都考算法，日本企业也不分前后端，虽然实际工作的时候区分，但是面试的时候，前后端的问题几乎都是算法，主要考察思路。

但是这个公司的面试体验很差。

[FrankHB]

出题的的确很可能不专业，但你这样看起来是一百步笑五十步。（至于你所谓的“他们”太离谱就不评价了，我不觉得有浪费铜币婊的价值。）
再说清楚点吧，自作主张加戏让别人背锅风险的，任何项目负责人都不会乐意当队友。

国外的朋友？你是问过几个 ICPC 还是 IOI 决赛圈选手，就能管这叫“共识”了呢？
工业界比竞赛圈历来先进的一点就是对这类虚空共识发明家尤其敏感。但是即使做只擅长算法题工业界混不好的，整体也不至于 low 成这样吧。所以我高度怀疑你所谓的国外朋友正经是做什么的。

至于为啥你会认为我需要谷歌 1000000007 （而没看出来我随便举例的特殊性……非要我 4294967297 怼你数论基础砸场子吗），我就不计较了。

[CookCoder]

想教育我，起码审题行吗？

[CookCoder]

@FrankHB 我看了你的一些发言，你很喜欢抬杠和输出观点，而且态度都很不好。

所以你现实生活是多么的不如意，让你戾气这么大

[necomancer]

In[2]:= Fibonacci[9292]

Out[3]= 36615772462226778497854272068347456903203535721576563305001882\
4446808971505522682252557462388869487429215147859670048443557030510924\
2313638033416669900444112247937728056211966758992460916419400444853615\
0659995426159958705401822049236361283380030364021954972693189793054990\
6755541787721845184132515014730718340789844257461094023669363764925901\
6140512151236060436731993551961323374694640088413329540217958532844994\
6021273729864624801649860858997392396829447879954242712774677453828896\
1654341048857935441878207228426883065999292881549658263447447546725460\
1183355700504643184963095650659016150303753725509080657414720402415839\
2279674457694234096817291978625827299718248723889062148394904123612383\
8755719810784487707901717432096035328612595568604179756660091008942882\
4579522915583067121845203670580431109038026031805366693865811657549114\
6451800292235506843706203859421399525135962129895729017175669910289503\
9164133931355135824951376885398355592136531493074426906052845318085318\
1277008706114560211720676164926069583198482669740034992505014190676786\
1826193562982886149731745127900366793891334956005215747258441299727424\
3067473691667279262508464102799073324973945932644031301367264984825431\
5756846997118764723139178365862765173488978551301801196364660097159749\
2165058128156102400945704343883305010014902608294939820797741099763137\
9586795329323235044514114098601714461528505657129718977557957794347601\
7486485426114739433921822640390808840316534298381708300360202292556716\
2756960501161791462185991020606417837285106207003686110205223085088050\
6635426798303144743970873843083081229936959093803928806387360717509525\
3952963248468206808754647017090147700831859035388796576278194027465866\
1016159406917289941299321202063907398141415112260498823238868612459402\
5244669760768036285301069483216818980323500251537269509976571417468577\
6789816323408545017065365758342146429980816094007713959447619038393467\
627366903822647919125618219011528539949951357869642550538579

-_-能调接口吗？ Wolfram engine 永远滴神！（手动狗头

[FrankHB]

“请尽量让自己的回复能够对别人有帮助。”在你身上浪费铜币现在完全是公益性的了：防止共识发明家误导舆论。

至于你本人，现在看来甚至都没什么被人身攻击的价值，所以不再多评价了。

[qwertyegg]

原来杠精喜欢给别人扣杠精帽子，笑死了

你开心就好

[qwertyegg]

@FrankHB 完全同意。反正帽子是给别人扣的。

这样的人应该在单位也很受欢迎吧

[kakawanzi]

请问方便透露下是什么公司么？感觉好奇怪 我好想页遇到了类似的题目

[CookCoder]

@kakawanzi 一家日本的公司

[kakawanzi]

@CookCoder 那最后你去那家公司了么 ？ 你知道后续其他题目么？

[CookCoder]

@kakawanzi 没去

[kakawanzi]

@CookCoder 我特别差异 既然正常算法和逻辑已经溢出了 那这个结果是如何计算出来的啊？ 求教

[acvvkhalil]

这个只能用矩阵快速幂加高精度乘法吧

[acvvkhalil]

@acvvkhalil 直接矩阵快速幂就可以了

[acvvkhalil]

这个只能用矩阵快速幂加高精度乘法吧
@acvvkhalil https://www.luogu.com.cn/problem/P1962

[CookCoder]

@kakawanzi 可以计算出来，不会溢出，毕竟有 bigint 类型，只是这个结果很大，如果把这个结果当答案提交给对方，我感觉很侮辱对方。