面试了一个远程公司,第一题是写一个斐波那契数列的实现,这个没有任何难度,反正是不写递归就行
但是第二题是用自己写的第一题的答案运行 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 ,对方公司就是要这个庞大的结果 我现在道心崩了
1
CookCoder OP 所以在面试题没有明确需要 % 1000000007 的时候,面对这样的结果,我们是给出原答案,还是 % 1000000007
|
2
CookCoder OP 3661577246222677849785427206834745690320353572157656330500188244468089715055226822525574623888694874292151478596700484435570305109242313638033416669900444112247937728056211966758992460916419400444853615065999542615995870540182204923636128338003036402195497269318979305499067555417877218451841325150147307183407898442574610940236693637649259016140512151236060436731993551961323374694640088413329540217958532844994602127372986462480164986085899739239682944787995424271277467745382889616543410488579354418782072284268830659992928815496582634474475467254601183355700504643184963095650659016150303753725509080657414720402415839227967445769423409681729197862582729971824872388906214839490412361238387557198107844877079017174320960353286125955686041797566600910089428824579522915583067121845203670580431109038026031805366693865811657549114645180029223550684370620385942139952513596212989572901717566991028950391641339313551358249513768853983555921365314930744269060528453180853181277008706114560211720676164926069583198482669740034992505014190676786182619356298288614973174512790036679389133495600521574725844129972742430674736916672792625084641027990733249739459326440313013672649848254315756846997118764723139178365862765173488978551301801196364660097159749216505812815610240094570434388330501001490260829493982079774109976313795867953293232350445141140986017144615285056571297189775579577943476017486485426114739433921822640390808840316534298381708300360202292556716275696050116179146218599102060641783728510620700368611020522308508805066354267983031447439708738430830812299369590938039288063873607175095253952963248468206808754647017090147700831859035388796576278194027465866101615940691728994129932120206390739814141511226049882323886861245940252446697607680362853010694832168189803235002515372695099765714174685776789816323408545017065365758342146429980816094007713959447619038393467627366903822647919125618219011528539949951357869642550538579
|
3
CookCoder OP 上面是不 “优化” 的结果
|
4
si 2022-03-02 09:22:20 +08:00
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; }; 你的算法改一下就可以了 |
7
murmur 2022-03-02 09:33:54 +08:00
你在问什么,考点是什么,看了一下不实现很常规吧,快速矩阵解法真不会,我还以为靠 BigInt 的实现,题目不是明确告诉 mod 计算么
|
8
hertzry 2022-03-02 09:35:05 +08:00 via Android
还以为你要全部的数列,想了半天怎么发出来。
|
9
air8712 2022-03-02 09:35:58 +08:00
1, 不说让 mod 就不 mod
2. n <= 200 时候 int64 就不够用了 3. 用大整数即可 4. 用矩阵 + 快速幂,复杂度可以降到 logn |
11
jiezhi 2022-03-02 09:39:07 +08:00
纸上谈兵地说一下,做第一题的时候就要问清楚输入条件吧,以及超过 int 范围怎么处理之类的。
有些题看起来简单,但更多地是看你的沟通能力以及对细节的把控能力。 --- 当然这些都是我从书上看到的。 |
12
CookCoder OP @hello2090 答案要在他们的 PDF 上编辑,但是给的空格大小,看看我上面写的答案,我就复制进去 5 行而已,所以也许我想的太多了,认为既然给给么小的空白,肯定不是输入完整的答案,应该进行 MOD
|
14
hello2090 2022-03-02 09:43:23 +08:00
@CookCoder 当然你可以按照你想的方法做,但如果人家想的和你想的不一样责任就在你自己了,你用 xxxx7 mod 别人希望你用 xxxx9 呢万一
|
15
CookCoder OP @hello2090 我问了搞算法的博士朋友,这个题目是他们出的有问题,如果 n 不进行限制,那么需要给出内存限制,如果什么都不给出,默认需要 MOD 1000000007 ,这个数字不是随意的,也是属于共识,如果需要 MOD ,肯定都是 1000000007
|
16
lakehylia 2022-03-02 09:46:26 +08:00
long 整不了,就用 BigInt ,用循环不用递归来解的话,又不吃内存。无非是一个 O(n)的算法。
|
17
lance6716 2022-03-02 09:46:29 +08:00 via Android
面试的时候,沟通也是考察的一环
|
18
CookCoder OP |
19
Perry 2022-03-02 09:48:39 +08:00 via iPhone
你这是在线面试还是 take home 面试?在线面试难道不是得问考官 constraints 或 clarifying question 吗?
|
21
CookCoder OP @lance6716 远程面试,给题目以后就无沟通了,而且运气很差,对方是才毕业一个月的新手,后期沟通答案的时候,她转述程序员的解释,差点让我信仰崩塌。
她说因为我没有 MOD 我? 过了一会说要的是原答案 我?? 那你给我的空白也不够把原答案复制进去啊 |
22
Aoang 2022-03-02 10:00:31 +08:00 via iPhone
建议直接放弃,不用太在意。
之前远程电话面试某厂,人都是拿着面试题随便挑着问的,都能听到翻页的声音。如果你回答的不是纸上的答案,就说你回答的不对。问题在于还有宏观题… 面试到一半,给我整一句,你简历上写的完全都不会,然后把电话挂了。 面试体验最差的一次 |
23
fds 2022-03-02 10:06:54 +08:00
……没听说过取模还有什么共识的。你换几个别的数字会有什么问题呢?
我个人理解,这题考点就是时间复杂度和类型的取值范围。时间复杂度别递归就行。取值范围你要用 python 实现,就不用做什么特殊处理,因为 python 支持大整型。用 js 的话,要不就用 bigint ,要不就自己写个数组分段计算,不然 float64 会丢精度。 面试给 pdf 应该也不用在 pdf 上编辑吧?肯定要提供程序代码吧?我觉得面试主要看代码,至于答案,只要是算法对,应该无关紧要。 |
24
masterclock 2022-03-02 10:13:03 +08:00
1000000007 挺常用,但也没到共识的程度
面试的时候,给了问题,只做,不提疑问,我一般是扣分的 |
25
CookCoder OP @masterclock 我之前因为提问,反而扣分,这个真是看缘分了
|
26
zhandi4 2022-03-02 10:17:34 +08:00
BigInt 加矩阵快速幂,他就没啥可挑剔的了。题目没有说取 mod 的话,还是没必要先入为主去取,或者说把自己的疑问去沟通一下。事后来看就不用去纠结了,这面试体验太差了,面试也是相互选择的。
|
27
ipwx 2022-03-02 10:17:53 +08:00
我觉得沟通需求也是程序员重要的基本技能。楼主这就属于沟通技能极差
|
28
littlewing 2022-03-02 10:20:55 +08:00
要不要 mod 你直接问 HR 不就行了,你再这里问有啥用
|
29
CookCoder OP |
30
CookCoder OP @littlewing 因为一直以为大数值答案是默认 MOD 的,根本不需要提问
|
31
ipwx 2022-03-02 10:22:44 +08:00
“我只是认为在国内很基本的面试题”
我觉得坚持这个认知没错,这件事情就说明沟通技能差了。( |
32
CookCoder OP @ipwx 那我感觉您可以和那个因为我提问,反而扣分的面试官进行沟通一下,他说面试题就是考察你所有想到的点,把所有可能都解答到位就 OK ,所以提问当然减分。
所以面试这么多次以后,遇到疑惑,到底提问还是不提问,因为我怎么选择都遇到扣分的情况。 所以这个我感觉和沟通能力什么的都没有任何关系,就是看面试官而已。 |
33
iDontEatCookie 2022-03-02 10:28:24 +08:00
这么垃圾的面试体验就别找自己的问题了吧?
|
34
jmc891205 2022-03-02 10:32:13 +08:00
面试不是考试,更像相亲,有时候就是会因为一些莫名其妙的原因被拒(对候选人对公司来说都是)
|
35
mainjzb 2022-03-02 10:32:44 +08:00
我觉得。。。这个面试很有效。。。证实了这个部门和你真的不合(逃
|
36
jmc891205 2022-03-02 10:34:10 +08:00
不过就此题来说
如果我是面试官 候选人问我要不要取模或者主动就取模了 那我后面会避免和他讨论 Leetcode 原题了 hhh |
37
CookCoder OP @jmc891205 我之前也不知道取模,最开始面试的时候,我甚至是递归去回答,经过几轮面试官的教育,才知道有什么动态规划,MOD 等等。
|
38
fds 2022-03-02 10:56:15 +08:00
面试又不是考试,没有标准答案。不同面试官有不同解读很正常。招人的岗位不同对答案的侧重也有不同。你非得争对错,就比较“学生气”。何况面试也是你选择对方的一个过程,如果对方主管或者工作方式你不喜欢,那就不要强求。
至于取模,十年前考察 C 语言并且是 easy 难度的题目,那一般会提示你取模。难一点的都可以要求你用数组模拟计算出来。现在主流语言基本都支持大整型了,所以直接要精确结果也正常。基本功在面试初级岗位时还是挺重要的。 @CookCoder 你能回答我如果这道题用 js 编写,可以取模,但一定要精确结果,这个取模运算中被除数的最大值是多少吗?我从你之前的回复里感觉你不清楚这个答案。那么对方公司给你扣分也无可厚非。扣分的点不一定是你提问了,而是你的提问暴露出一些知识漏洞。 |
40
encounter2017 2022-03-02 11:07:26 +08:00
|
41
ytmsdy 2022-03-02 11:10:22 +08:00
LZ 不要太过于自闭了,这属于面试官水平不行。
如果我是面试官,第一题算是入门,第二题会问如果 N=1000 的结果,然后再引导 N=10000 结果是什么。 这么运行会不会有什么问题,看面试者的回答,看是怎么优化一下还是有什么其他实现方式。 面试其实是为了看面试者的思考逻辑,和解决问题的方法,以及知识面的情况。 |
42
encounter2017 2022-03-02 11:16:46 +08:00
n < 2 的时候直接返回,不太对吧。。。
前几项是 1, 1, 2, 3, ... |
43
CookCoder OP @encounter2017 是从 0 开始的
|
44
Mutoo 2022-03-02 11:24:04 +08:00
想起之前 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 |
46
CookCoder OP @ytmsdy 因为是远程面试,直接发过来一个 PDF ,我也是第一次参与这种形式的面试,和我对接的也不是技术,是一个 HR ,如果是一个技术,我可以很放松的进行提问,但是根据之前的沟通,这个 HR 可能互相转述疑问和解答,都很费劲。
|
47
UIXX 2022-03-02 11:36:03 +08:00 3
这不是算法结果优不优化的问题,甚至跟问什么都没关系。
面试官作出的解释让我想起了以前学生考试的“多选选错扣分”的多选题,其中的内涵是应试者有条件地作出应对策略,这种机制用来面试应聘者的技术水平不合适。 一个好的面试官应该要为应聘者提供足够的“容错”,专注于“找缺点”的面试官,要么招聘动机不纯,要么自己是不专业的外行人。落选了没什么好可惜的。 |
48
fds 2022-03-02 12:09:28 +08:00
@CookCoder 啊,对不起,我问题说错了,不是被除数,是除数,就是你说的 % 1000000007 这里,用比 1000000007 大的数,在 js 下最高能大到多少,能让你给出的代码返回一个精确结果。
|
49
learningman 2022-03-02 12:38:39 +08:00
高精度呗。。。没说让你取模你凭啥敢取模啊,万一是 998244357 呢
|
50
lervard358 2022-03-02 13:30:57 +08:00
BigInteger
|
51
efaun 2022-03-02 13:54:08 +08:00
有没有可能这是对方故意留的坑? 就看你会不会考虑全面, 对应的是做需求前有没有充分沟通
|
53
flyhelan 2022-03-02 16:25:11 +08:00
% 1000000007
|
54
flyhelan 2022-03-02 16:25:23 +08:00
% 1000000007 有什么用?
|
55
sockball07 2022-03-02 17:52:24 +08:00
@flyhelan #54 刚好也直接 google 了一下 1000000007 https://www.zhihu.com/question/49374703
|
56
vance123 2022-03-02 18:00:53 +08:00
无非是考察长整数嘛,大不了用字符串写一个
|
57
lovestudykid 2022-03-02 18:12:46 +08:00
不 mod 考察啥呢,难道考察你会不会用 bigint?
|
58
CookCoder OP @lovestudykid 我也以为 MOD 是考点,但是我想多了,人家就是要那么大的数字,我自己还非要 MOD 一下,多余的操作,应该直接复制一张 A4 纸的答案,扔给他们。
|
59
Daiwf 2022-03-02 22:05:28 +08:00
你想多了,就是开发太忙了没高兴来面,找了个 HR 来凑数。结果就把你纠结了
|
60
ffgrinder 2022-03-02 23:23:31 +08:00
@CookCoder 我觉得是你想太多。
能开起来公司并不一定就是有实力,可能是爹比较有钱。 我最近感受可太深了。 从我个人来说,如果你说明白了你 MOD 1000000007 ,我会怀疑你可能作弊(因为我没要求,你没沟通,默认用了 leetcode 的题解),那加试就行了。 对方这个沟通水平也挺一般的,换家公司好了。 |
61
dany813 2022-03-02 23:29:14 +08:00
碰到菜鸡面试官 没办法
|
62
FrankHB 2022-03-02 23:46:18 +08:00
1000000007 ?凭什么不是 100000007 ?
面试体验是垃圾,但是要我遇到没事瞎脑补 MOD 1000000007 这种无中生有的二缺“共识”而不是会主动沟通的候选者,就默认刷掉,撑死进复活区。 说白了,需求描述不清可行性明显有问题就是 bug ,遇到 bug 就报,这做项目和做算法题都一样。什么做题的“共识”那么有排面凌驾于这种常识上了? (我当年闲着刷 ZOJ 的时候哪来的这种脑补,人比赛去也都是再三强调读懂题意。是最近几年卷多了就想欺负面试官不懂“规矩”么。) |
63
adoal 2022-03-03 00:31:17 +08:00
求职不是求知。沙雕的公司 /面试官 /HR 很多,没必要非要咽不下一口气要个说法。尤其是这种涉及惯例达不成默契的人为因素,自己有数知道自己没问题就行了。
|
64
CookCoder OP @FrankHB 只能说这是国内和国外的区别?但是我问了一些国外的朋友,他们遇到这样超大数字的结果,也是 MOD ,至于为啥是 1000000007 ,楼上有回答,请您自己谷歌一下。
如果是 F100 ,我都可以给出原答案,但是 F9292 ,面试公司还要原答案,我现在也不纠结了,可能就是出题的人也不清楚这个结果有多大,或者出题的人不专业,才死活要原答案。 |
65
CookCoder OP @adoal 是的,只是当初他们质疑我结果是错的,我需要一个说法,为何错了。
结果他们最开始说我的结果没有 MOD ,我就请他们查看一下源码,最后又说是转述错误,不需要 MOD 。 就是要那么长的原答案,我就质疑对方,清楚这个结果的长度么? 清楚给出的答案留白哪怕用最小号的字,也复制不下。 对方就不说话了,我就直接去找对方的 CTO 反馈了,我说这就是你们对待面试的态度? |
66
CookCoder OP @ffgrinder 但是他们最开始说我错误的原因是没有 MOD (后来沟通初步审核答案的是 HR ,只知道用固定的结果去对,我的代码和他手里的正确答案有逻辑差异,就说我错了),我说请再看源码,最后又改口说,不需要 MOD ,就是要结果。
但是他 A4 纸给的答案留白很小。 算了,不纠结 |
68
qwertyegg 2022-03-03 10:29:26 +08:00
|
70
CookCoder OP @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 个半音,没学过音乐,是搜出来的,如果不对可以指正,我会虚心学习的呜呜呜) 最后,三连的宝贝都是我的小蛋糕(玫瑰 就是你们这群自以为是的人,在那里咬文嚼字,好不容易看到一个以为自己可以彰显优越感的角度就蹬鼻子上脸地抬杠,送你这样的人一个字。 滚!滚!滚! |
71
clf 2022-03-03 13:37:46 +08:00
遇到这种笔试 /面试确实很蛋疼。
记得之前字节的笔试,最后结果是返回一个 map ,然后没说明以哪种情况对输出排序,最后 HashMap 、LinkedHashMap 、TreeMap 都试了一遍才过程序检测。 |
72
aguesuka 2022-03-03 13:42:44 +08:00
摸摸, 不哭, 下次怼回去, 不要受网友气了
|
73
liuidetmks 2022-03-03 15:14:23 +08:00
哈哈,你以为人家考你快速幂,实际上人家考你大数乘法的存储和实现
|
74
yazinnnn 2022-03-03 15:42:48 +08:00
为什么前端会问这种问题?
|
75
CookCoder OP |
76
FrankHB 2022-03-03 19:57:09 +08:00 1
出题的的确很可能不专业,但你这样看起来是一百步笑五十步。(至于你所谓的“他们”太离谱就不评价了,我不觉得有浪费铜币婊的价值。)
再说清楚点吧,自作主张加戏让别人背锅风险的,任何项目负责人都不会乐意当队友。 国外的朋友?你是问过几个 ICPC 还是 IOI 决赛圈选手,就能管这叫“共识”了呢? 工业界比竞赛圈历来先进的一点就是对这类虚空共识发明家尤其敏感。但是即使做只擅长算法题工业界混不好的,整体也不至于 low 成这样吧。所以我高度怀疑你所谓的国外朋友正经是做什么的。 至于为啥你会认为我需要谷歌 1000000007 (而没看出来我随便举例的特殊性……非要我 4294967297 怼你数论基础砸场子吗),我就不计较了。 |
77
CookCoder OP 想教育我,起码审题行吗?
|
78
CookCoder OP |
79
necomancer 2022-03-04 04:17:39 +08:00
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 永远滴神!(手动狗头 |
80
FrankHB 2022-03-04 13:12:37 +08:00
“请尽量让自己的回复能够对别人有帮助。”在你身上浪费铜币现在完全是公益性的了:防止共识发明家误导舆论。
至于你本人,现在看来甚至都没什么被人身攻击的价值,所以不再多评价了。 |
81
qwertyegg 2022-03-05 08:56:31 +08:00
原来杠精喜欢给别人扣杠精帽子,笑死了
你开心就好 |
83
kakawanzi 2022-03-22 15:22:08 +08:00
请问方便透露下是什么公司么?感觉好奇怪 我好想页遇到了类似的题目
|
88
acvvkhalil 2022-04-11 10:57:41 +08:00
这个只能用矩阵快速幂加高精度乘法吧
|
89
acvvkhalil 2022-04-11 11:01:57 +08:00
@acvvkhalil 直接矩阵快速幂就可以了
|
90
acvvkhalil 2022-04-11 11:05:57 +08:00
|
91
CookCoder OP @kakawanzi 可以计算出来,不会溢出,毕竟有 bigint 类型,只是这个结果很大,如果把这个结果当答案提交给对方,我感觉很侮辱对方。
|