V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
phpfpm
V2EX  ›  程序员

面试笔试做不出长整数加法的是不是 coding 能力就基本当没有了?

  •  
  •   phpfpm · 2020-08-20 11:02:09 +08:00 · 22698 次点击
    这是一个创建于 1557 天前的主题,其中的信息可能已经有所发展或是发生改变。

    最近面试,按说候选人背景也都不错吧。

    我们对算法要求没那么高,业务代码为主。

    因此对于各种语言的候选人,我基本都会问一道长整数加法的问题。

    俩数相加,都没有符号 /没有小数点 /字符串表示 返回和 /用字符串表示

    这题难吗?

    考察的知识点点挺广的:

    字符串 /数组操作,循环控制,流程逻辑,边界条件等等。

    这也基本上是编程的时候经常能遇到的问题。

    但是我遇到的面试者写的千奇百怪的都有:

    • 反复强调不能转 Int/number 还要强行转之后加起来的
    • 说了不能转但是按位 map 一下乘以 10 的幂加起来的
      • 乘方还写反的 idx ** 10
    • 字符串 /数组非得 reverse 否则不会写循环的
      • reverse 拼成 reserve/压根不会写这个函数的
    • 循环次数拎不清的,把短的的长度加一下长的就不管了
      • 好一点的知道再处理梳理一下长的数字的剩余位数
    • 最后多的一个进位忘记了的(很多)
      • 当然也不排除先相加判断是不是大于 10,再加上之前的进位的
    • 啰啰嗦嗦写了一大堆的
      • 极限是一个 go 的候选人干了七十多行还漏掉一些逻辑
      • 有人写 if a 长度>b 长度 then .... 我问他 else 写啥

    等等吧

    所以如果你遇到这个题,如何优雅的写一个 a+b?

    稍后我写一个我自己花了一小点时间写的答案,八行,没有很过分的压缩代码 我的代码大概长这样:

    function add(a, b) {
        let ...
        some magic {
        	cast something
            cast other
        }
        return ...
    }
    

    正经逻辑三四行写完,晚一些我贴条的方式公布我的答案。

    如果要你写,你写啥?

    第 1 条附言  ·  2020-08-20 11:35:54 +08:00
    漏了一句:
    也不许用 BigInt/各种高精度计算库了。。。

    坚持抖机灵会被面试官打死的。
    第 2 条附言  ·  2020-08-20 11:41:34 +08:00
    补充我写的 Emca Script 的版本:

    ```
    function add(a, b) {
    let pos = 0, res = ''
    while(a.length > pos || b.length > pos) {
    let carry = res.length - pos++
    res = (~~a[a.length - pos] + ~~b[b.length - pos] + carry) + res.substring(carry)
    }
    return res
    }
    ```

    这个进位处理也是受到某个面试者启发的,最后一次进位直接拼上去不处理了。
    321 条回复    2020-08-24 11:54:05 +08:00
    1  2  3  4  
    251
        201
    251  
       2020-08-21 02:25:01 +08:00 via Android
    讨论
    251
        202
    251  
       2020-08-21 02:30:35 +08:00 via Android
    我觉得这道题没什么问题。考察最基本的逻辑能力加最基本编码能力。整天我 google 就可以了,那你跟我 google 一下怎么成为亿万富翁?
    但我觉得 reverse 写错了不是问题,代码太长也不是问题。
    littlewing
        203
    littlewing  
       2020-08-21 03:29:22 +08:00 via iPhone
    按楼里某些人的说法,google amazon apple microsoft 都是垃圾,因为他们面试问算法最多
    OHyn
        204
    OHyn  
       2020-08-21 03:38:04 +08:00   ❤️ 1
    @calpes
    之前我也很喜欢位运算。
    比如,某个整数除二+向下取整。无符号右移一位,多酷炫。除 2 + 向下取整太 Low 了。
    结果,在 nodejs 里,这两个方法比起来,位运算居然是慢的。。。。。
    cassyfar
        205
    cassyfar  
       2020-08-21 03:47:11 +08:00
    这题挺弱智的。既然应聘者给出了 BigInt 的解法,就不应该说人家抖机灵。搞得自己实际工作中用不到第三方库一样。我就反感这种只期待某种解法的题。你知道就简单得不行,你不知道就卡住。
    而且如果这个是社招,更无厘头了。还加面更存纯粹的算法题,你们是在找做题家吗?社招都是算法轻,应用强。主要还是看 system design 吧。想起我司以前最爱考的就是动态规划,二维 DP 先来一套给你个下马威。后来 HR 明文禁止了,no DP !
    w7938940
        206
    w7938940  
       2020-08-21 03:58:22 +08:00
    题目都看不懂,是咸鱼没错了,哎
    CismonX
        207
    CismonX  
       2020-08-21 04:27:27 +08:00
    还有,十四楼那个不叫 VLA (variable length array)

    那个叫 FAM (flexible array member)
    CismonX
        208
    CismonX  
       2020-08-21 04:28:43 +08:00
    @CismonX 看错了,是 23 楼
    CismonX
        209
    CismonX  
       2020-08-21 04:29:44 +08:00
    @CismonX 而且严格意义上来讲,[0] 也不能算 FAM,[] 才算
    laminux29
        210
    laminux29  
       2020-08-21 06:02:25 +08:00   ❤️ 1
    稍微看了一些题主以前写的东西,发现了问题所在。

    题主是偏算法类的,但却面试者偏业务的人,这才是冲突的本质所在。

    如果被招的人,能够通过题主的面试,最后却去做了业务的活,要不就是被面试者傻,有着算法的能力却拿着业务的低工资;要不就是公司傻,用算法的高薪养了个本应低薪的写业务的。
    zjsxwc
        211
    zjsxwc  
       2020-08-21 06:09:43 +08:00 via Android
    我也考算法实现,不过都是线性代数里的矩阵基本运算实现
    qdwang
        212
    qdwang  
       2020-08-21 07:02:11 +08:00 via iPhone   ❤️ 3
    lz,你拼错了,是 ECMAScript 。不是 emca 。

    你这样去面试拼错单词,要被拉到 V2EX 批斗的。
    wnpllrzodiac
        213
    wnpllrzodiac  
       2020-08-21 07:32:23 +08:00 via Android
    写代码的多少不是搬砖的,你说的这个工作中能用几次,面试官主要看思路,解决问题能力。一道题刷人估计是面试候选人太多,忙不过来,一刀切
    cassyfar
        214
    cassyfar  
       2020-08-21 07:45:55 +08:00   ❤️ 3
    看了下 LZ 之前的提问,比如这个: https://v2ex.com/t/665885

    感觉就是科学家来做工程。比如你要是懂一点儿分布式,你可以把算汉明距离的进 queue,搞个 worker pool,几台机器平行一弄就好了。算法上抠智商搞出了的 10% 提升,可能平行 3 台机器就给解决了。
    expy
        215
    expy  
       2020-08-21 08:24:09 +08:00
    大数的四则运算,原题啊,上学没自己做过估计也抄袭过。
    xuanbg
        216
    xuanbg  
       2020-08-21 08:38:27 +08:00
    大数四则运算不是一个好的面试题。面试时间有限,没专门看过题的,大多只能给你一个小学生列竖式这种粗暴的算法。这种你能认可?真能没看过大数运算库源码的,面试这几分钟就能写得出来差不多代码的,估计万中无一。想找这样的天才,你是在想屁吃。

    真工程上要用,你会自己写一个?还不是找个库解决。
    ragnaroks
        217
    ragnaroks  
       2020-08-21 08:48:49 +08:00
    面试造螺丝,上班拧螺丝
    siteshen
        218
    siteshen  
       2020-08-21 09:08:05 +08:00
    面试者时的代码里有 “~~” 是会被我扣分的。
    hsliu
        219
    hsliu  
       2020-08-21 09:24:29 +08:00
    类似力扣上面两链表相加的题目啊,处理好边界就可以了(虽然我写的比较乱)
    chrunlee
        220
    chrunlee  
       2020-08-21 09:46:19 +08:00
    反正不让调试的话..我是肯定写不出来了
    cc029
        221
    cc029  
       2020-08-21 10:02:30 +08:00
    楼主是面前端还是后端呢?
    ChanKc
        222
    ChanKc  
       2020-08-21 10:04:48 +08:00 via Android
    @OHyn 而且 js 位运算不能覆盖到 MAX_SAFE_INTEGER,只能在 31 位以内,真的反直觉反人类
    oahebky
        223
    oahebky  
       2020-08-21 10:08:13 +08:00
    原文题目描述不清楚。

    不过应该是输入是 string 的意思;重新刷了 leetcode 415,

    发现上一次提交写得确实很长,这一次重新写了一遍,减少了一半的长度:


    ```python
    def big_add(num1: str, num2: str) -> str:
    ____l1, l2 = list(num1), list(num2)
    ____ans = []

    ____def helper(ans: list, carry: int, l1, l2=None) -> int:
    ________if l2 is None:
    ________l2 = ['0' for _ in range(len(l1))]
    ________while l1 and l2:
    ____________sum_ = (ord(l1.pop()) - ord('0')) + (ord(l2.pop()) - ord('0')) + carry
    ____________carry, mod = divmod(sum_, 10)
    ____________ans.append(chr(mod + ord('0')))
    ________return carry

    ____carry = helper(ans, 0, l1, l2)
    ____carry = helper(ans, carry, l1) if l1 else helper(ans, carry, l2)
    ____if carry:
    ________ans.append(chr(carry + ord('0')))

    ____return ''.join(ans[::-1])
    ```

    不过比起楼主的 append,想必不入法眼吧。


    ======


    至于原标题,如果说 string + string 做不出来,那确实有存有疑虑。
    但是要是说做成楼主那样的 solution 才算做出来,不然就是没有 coding 能力,我觉得是否定的。
    ChanKc
        224
    ChanKc  
       2020-08-21 10:10:22 +08:00 via Android
    @zjsxwc 你这个比 lz 的题还要难啊
    phpfpm
        225
    phpfpm  
    OP
       2020-08-21 10:23:05 +08:00
    今日摸鱼开始,集中回复一下各位同学。


    @cassyfar 其实我工作中一点项目都不搞,仅仅是个人爱好。
    @oahebky 这么写已经很优秀了,我在评论中也说了,我在炫技而已。
    @cc029 看我 id
    @siteshen ~~不能完全代替+ 还是有存在的意义的
    @xuanbg 没说写出来小学生的我就认可,我只是淘汰掉写不出来的而已(大概率)
    @wnpllrzodiac 对就是太多 我一周 70%的时间都在面试 喵喵喵?
    @CismonX 行,我 2 了~关于 c 我就记得这个 trick 了,毕业之后就没写过。
    @ChanKc 我认错,看我 id
    @laminux29 同,我的工作还真的跟算法没啥关系,没那么大,很贴业务。
    之前发过汉明距离那个问题自以为已经解决的比较完美了,计算的耗时在完全可接受的程度,没有占用过多的机器资源。
    ygtq
        226
    ygtq  
       2020-08-21 10:27:13 +08:00
    res = (~~a[a.length - pos] + ~~b[b.length - pos] + carry) + res.substring(carry)
    楼主答案里这一行的这个~~,真的有意思么? 就是不让用 parseInt 呗
    hitmanx
        227
    hitmanx  
       2020-08-21 10:28:24 +08:00   ❤️ 2
    @cassyfar "我就反感这种只期待某种解法的题。你知道就简单得不行,你不知道就卡住"

    这题应该不算。最简单的,竖式运算每个人小学就会了,只是把这个东西翻译成没有 bug 的代码而已,不存在需要"aha"的那种瞬间,或者说“不知道就卡住”之类。但是要写的没 bug 还很简洁,也不是每个人都能做到的。从这个角度上说,我觉得这道面试题作为考察编程能里还不错。

    你说的那种是某个场景需要某种特定的算法,没了解过那种高级算法就只能写简单暴力的算法,如果是那种题目,就属于你会就会,不会就很难在几十分钟内做出那种。
    phpfpm
        228
    phpfpm  
    OP
       2020-08-21 10:30:41 +08:00
    @cc029 我啥都面,就怕简历看串了问错题

    @chrunlee emm 不要求运行,但是如果候选人有兴趣调试一下我也不拦着
    @ChanKc max MSI 是 31bit 我记下来了
    说起来问过这么多候选人 Number 的整数的范围是多少几乎没人能答上来,真的 nobody cares 么
    @cassyfar 哈哈哈你们 hr 还管的真宽
    lwlizhe
        229
    lwlizhe  
       2020-08-21 10:33:05 +08:00
    试了一下,最后忘了 reverse……捂脸~
    VeryZero
        230
    VeryZero  
       2020-08-21 10:36:09 +08:00   ❤️ 16
    题目有没有意义见仁见智,不过题主的表达能力似乎需要加强。

    我看了半年题目愣是没搞清需求,心想两个整数相加还能玩出花?

    看了下面的回复和 leetcode 的原题才恍然大悟,原来是两个字符串形式的整数。你看 leetcode 的题面就一目了然。

    另外说说算法面试,从我做切图仔开始算的话,目测干这行 15 年了。

    其实挺理解题主的,我做面试官的时候也经历过这个阶段。吹毛求疵,认为我都懂的东西你没理由不懂,不懂就是菜。

    但是你有没有想过,算法是需要训练的,刷过这题的人觉得很简单,但是没经过算法训练的人别说实现了,想解题思路可能都要一会儿,甚至可能像我这样,搞懂题面都需要时间。

    同时人也是有能力圈的,你出的面试题说明这是你的能力圈,你不能指望别人的能力圈跟你的一样。因为一道题就给人下定论,这本身就是武断和片面的。

    大佬也有被基础绊倒的时候,可能因为忘记了,也可能是知识死角,都很正常。你难道没有遇到过某个知识点你知道,大佬却不知道的情况吗?难道就可以以此说明这个大佬就是菜?连你都不如?

    所以面试是需要多维度考察候选人的,特别是小厂。大厂随你怎么玩为所欲为,反正人多的是。小厂经不起这么折腾,经过大厂截留以后本身就没有多少优秀优选人了,你今天这题刷掉一个,明天那题刷掉一个,你老板会找你谈话的。

    个人喜欢笔试为辅,聊天为主。如果时间充裕甚至不要笔试,就硬聊。一方面可以给机会让候选人展现自己的能力圈,同时还能拓展自己的能力圈,另一方面可以过滤掉纯背题的人。

    说回正题,关于算法和编码能力的关系。从 WEB 后端角度说,个人觉得关系不大。而且我觉得还挺有发言权的,我是中专毕业做的切图仔,意味着我工作前都不知道算法是什么鬼。但并不影响我编码,10 年前我用 C++写了一个软件,数十万行代码,独自一人耗时近 2 年,稳定性行业前列,让我赚到了人生第一桶金。后来我又独自用 Java 撸了一套支付系统。其他 PHP 撸的 CMS,Flutter 撸的 APP 之类这些没啥技术含量的就不细说了。后来我意识到基础的重要性,开始恶补基础和算法。学之前觉得算法应该好难吧,会的人都是高手。后来静下心来一题一题研究,理解并实现了以后发现,原来是这样的,也不太难嘛。毕竟难者不会,会者不难嘛。

    要说对我日常编码有提升吗?说实话,真没什么感觉。该写 bug 照样写。可能面试的时候更自信了吧。。
    phpfpm
        231
    phpfpm  
    OP
       2020-08-21 10:36:48 +08:00
    @ygtq 因为不等价:
    Number(),parseInt(),+a,~~a 里面

    只有~~a 能处理 undefined——前面有人提出下溢出了

    所以还算有点意思吧



    @hitmanx 之前我也考过比如二维折半查找,绝大多数人都没有思路——我不强求,把算法告诉面试者之后让 ta 复述算法实现,都 ok,但是落笔写不出来代码我就有点……不开心了
    phpfpm
        232
    phpfpm  
    OP
       2020-08-21 10:43:11 +08:00
    @VeryZero 感谢回答了这么长……
    表达力这种事情我确实是糟糕,最近面试说话太多脑袋都机械僵硬了
    一方面我没把这个题当做算法题考,逻辑正常+语言有一定基础就 ok

    我倒是不觉得不懂就是菜这种说法,面试还是以找亮点为主。

    时间真的不充裕。我也希望多聊发现候选人的亮点,但是现在本身视频面就很尬,时间排的还满满登登,为了面个试还满大街找会议室很揪心;要么就是晚上面到很晚,整个人都僵化了。

    膜拜大佬,我的经历还需要更多历练。
    Torpedo
        233
    Torpedo  
       2020-08-21 10:43:21 +08:00
    我觉得这种题作为基础的筛选而不是考算法挺好的。

    不管面试者用什么方法,能给出 bugfree 的解,都是对的。作为基础自然要有多重解法,不能限定面试者用什么解法。

    要是想考算法,那就出个只能用算法解的题就好了
    phpfpm
        234
    phpfpm  
    OP
       2020-08-21 11:02:01 +08:00
    @Torpedo 嗯,bugfree 是前提,不过要是直接(a, b) => '' + BigInt(a) + BigInt(b)我就要打 PP 了。
    说起来有一个候选人说自己手写实现过加减乘除我说 ok 你写的优雅一些,结果连 bugfree 都没做到,这就尴尬了。
    VeryZero
        235
    VeryZero  
       2020-08-21 11:02:45 +08:00   ❤️ 1
    对了,还有一些忘说了。

    程序员最重要的其实不是编码能力,而是理解业务的能力。从这方面来说可以使用实战题的方式,给他提出一个业务需求,让他给出实现思路。

    相对于技术差的,不懂业务的更难受。

    你给了他需求,他淡定的一点头就开撸了。一顿操作猛如虎,结果一看全回炉。需求完全没对上,白干。搞笑的是,恩,代码貌似写的还挺好。。这种人你留在团队里就得累死,得时刻盯着他别跑偏,不留又有点可惜。。

    如果懂业务就舒服多了,需求给他,他跟你一通交流,确认无误了开撸。到期交货,虽然代码质量一般,时不时出点 BUG 。但是方向没错,时不时还能有点小惊喜,冒充点额外想法,充当半个产品经理。
    phpfpm
        236
    phpfpm  
    OP
       2020-08-21 11:13:02 +08:00
    @VeryZero 完全同意。你说的理解业务能力 /沟通 /软素质在我之前和之后各有一轮,所以我作为前置的技术面试官就多关注技术能力一些。
    fengmumu
        237
    fengmumu  
       2020-08-21 11:15:00 +08:00
    @VeryZero 最后那个是我没错了。。。。
    v2yooha
        238
    v2yooha  
       2020-08-21 11:18:47 +08:00
    没毛病。将思维逻辑用代码转化为实体是种能力
    phpfpm
        239
    phpfpm  
    OP
       2020-08-21 11:25:07 +08:00
    @fengmumu 哈哈哈哈人人都是产品经理,但是只有产品经理才是产品经理
    XisucksYi
        240
    XisucksYi  
       2020-08-21 11:39:30 +08:00
    我被面試的時候, 多得是直接 Wiki 出來打面試官臉. 你說下憑什麼一定要得到你的"認可"才算能力高?

    很多面試官連 Program execution 的 Wiki 詞條都沒看過, 我可不可以說他的認知連高中生都不如?

    我自學就沒看過書, 我就專門看 Wiki 和 一些工具的官方文檔, 就是為了面試的時候打你們這些不知天高地厚的面試官的臉, 你面試官要是敢跟我爭等著被我打廢吧
    phpfpm
        241
    phpfpm  
    OP
       2020-08-21 11:45:11 +08:00
    @XisucksYi 您太棒了!!!
    muyiluop
        242
    muyiluop  
       2020-08-21 11:45:29 +08:00
    如果招聘要求中有明确提到需要算法能力,那不会做的就是有问题了
    peapods
        243
    peapods  
       2020-08-21 11:57:19 +08:00
    @XisucksYi 哈哈,我也面试过别人,一般都是考察人解决方案的能力。工作里面细枝末叶太多了,很多你不注意的知识点可能真的不翻资料回顾下只留下大概印象,讲不出来。所以不会拿那个特定的知识点卡别人,不行就 996 干的飞起吧。

    但是你这也太暴力了吧,打脸都来了。
    XisucksYi
        244
    XisucksYi  
       2020-08-21 12:00:11 +08:00
    @peapods 很多面試官硬說 GNU Bash 不是編程語言. 我只好 Wiki 出來給他看咯, 可是他還是跟我爭, 如果換你你接下來會怎麼做?
    fengmumu
        245
    fengmumu  
       2020-08-21 12:11:43 +08:00
    @phpfpm 经常和产品商量商量着 然后自己就发现给自己加了很多活。。。。
    ipoh
        246
    ipoh  
       2020-08-21 13:03:27 +08:00   ❤️ 1
    没人发现楼主的解答的时间复杂度是 O(N*N)么?
    这种解答怎么能称为优雅。。。
    phpfpm
        247
    phpfpm  
    OP
       2020-08-21 13:10:39 +08:00
    @ipoh 诶诶诶?怎么就 n 方了
    你放学别走,你说清楚啊
    说溢出的是你 n 方的还是你
    我老老实实遍历一遍咋着了就



    @fengmumu 哈哈哈哈我选择把产品的思路带偏
    一次多点活没事,重点是教育产品要按照技术的方式思考问题。
    (他听不听另说。
    ipoh
        248
    ipoh  
       2020-08-21 13:24:05 +08:00 via Android
    @phpfpm 你先想想嘛,想不出来我再告诉你。算法第一课就是时间复杂度吧,每次做完算法题记得算一下。
    ipoh
        249
    ipoh  
       2020-08-21 13:35:06 +08:00 via Android
    @phpfpm 而且就你这 O(N*N)的解答本身也是问题很大,先留给你自己思考。
    不是代码越短就越优雅,虽然你面试了这么多次这道题,看起来你也并没有怎么认真思考。
    phpfpm
        250
    phpfpm  
    OP
       2020-08-21 13:47:12 +08:00
    @ipoh hhh 再见。
    ipoh
        251
    ipoh  
       2020-08-21 13:54:53 +08:00 via Android
    @phpfpm 拜拜~
    哥最讨厌的就是半瓶子抖机灵,见一个打一个。
    XisucksYi
        252
    XisucksYi  
       2020-08-21 14:21:07 +08:00
    @phpfpm 你不是很喜歡炫技嘛, 那你解釋下 LeetCode 的 #69 題的 O(1) time complex 的思路是什麼, 來我把代碼給你:

    // LLVM-Clang
    int mySqrt(int x)
    {
    if (x < 0)
    {
    return -1;
    }
    if (x == 1 || x == 0)
    {
    return x;
    }
    float tmp = (float)(x);
    const float xhalf = 0.5f * tmp;
    int i = *(int*)(&tmp);
    i = 0x5f375a86 - (i >> 1);
    tmp = *(float*)(&i);
    tmp = tmp * (1.5f - xhalf * tmp * tmp);
    tmp = tmp * (1.5f - xhalf * tmp * tmp);
    tmp = tmp * (1.5f - xhalf * tmp * tmp);
    int ret = (int)(1.0f / tmp);
    if (ret * ret > x)
    {
    return ret - 1;
    }
    return ret;
    }
    XisucksYi
        253
    XisucksYi  
       2020-08-21 14:22:26 +08:00
    @ipoh 代碼越短通常省略的東西越多, 重構也就越難
    ipoh
        254
    ipoh  
       2020-08-21 14:22:54 +08:00 via Android
    @XisucksYi 我不是炫技,我自己水平也很差。
    只不过指出楼主的问题而已
    phpfpm
        255
    phpfpm  
    OP
       2020-08-21 14:34:30 +08:00
    @XisucksYi 这个我早就知道啊,利用浮点数的结构和一个魔术数,还有牛顿法什么的。
    我很好奇你为啥拿这玩意考人。。。
    phpfpm
        256
    phpfpm  
    OP
       2020-08-21 14:35:30 +08:00
    @ipoh 你也没指出啊
    来来来

    接着说 N*N 哪来的
    jiaqiu2003
        257
    jiaqiu2003  
       2020-08-21 14:39:09 +08:00
    function add(str1, str2) {
    const getNum = str => str.split('').reverse().reduce((acc, s, idx) => acc + (s * 10 ** idx), 0);
    return getNum(str1) + getNum(str2) + '';
    }
    add('123', '21'); // Print '144'
    phpfpm
        258
    phpfpm  
    OP
       2020-08-21 14:40:56 +08:00
    @ipoh 我大概猜到你的杠点在哪了,你是说 prefix-string-concat 的实现复杂度是 N 么
    你要是这么聊算法复杂度干脆去看机器码好了
    真有趣。
    ipoh
        259
    ipoh  
       2020-08-21 14:41:11 +08:00 via Android   ❤️ 1
    @XisucksYi
    @phpfpm
    楼主解答的循环里面字符串拼接复杂度是 O(N),加上循环就是 O(N*N)
    其次,对于楼主 O(N*N)的解答,循环里面增加一个终止判断条件平均能节省一半的时间。
    phpfpm
        260
    phpfpm  
    OP
       2020-08-21 14:43:28 +08:00
    @jiaqiu2003 少年 10**idx 是要越整数界的 阿弥陀佛
    XisucksYi
        261
    XisucksYi  
       2020-08-21 14:45:31 +08:00   ❤️ 3
    @phpfpm 事實是不是就是 O(n ^ 2) 呢, 你要是不 care 這種隱藏的耗時的話, 那我隨便寫個 O(4 ^ n) time complex 的函數, 然後我在另一個函數調用一次, 我是不是也可以說這個函數的 time complex 只有 O(1).
    phpfpm
        262
    phpfpm  
    OP
       2020-08-21 14:47:15 +08:00
    @ipoh 是我猜到这个了。
    我招的不是写高性能代码的,这玩意纯属是实现的问题,要是拿这个都算复杂度你可真是掉书袋了。

    @XisucksYi 你同意是 N^2 么?
    ipoh
        263
    ipoh  
       2020-08-21 14:50:21 +08:00
    @phpfpm
    如果你觉得是杠那我确实无话可说

    而且就算用你的解答任然不算优雅,你的解答对于长度相差过大的字符串会有很多无用操作

    相反你觉得啰嗦的那个哥们可能考虑到了这个问题
    "
    啰啰嗦嗦写了一大堆的
    极限是一个 go 的候选人干了七十多行还漏掉一些逻辑
    有人写 if a 长度>b 长度 then .... 我问他 else 写啥
    "
    phpfpm
        264
    phpfpm  
    OP
       2020-08-21 14:51:27 +08:00
    @XisucksYi 哈哈哈哈你俩凑一对吧

    我完全同意在算法的角度这个复杂度就是 N^2

    我完全同意你俩可以做一个优秀的底层算法工程师

    但是我招的如果是你俩这样的人我不会考这种代码,考这种代码适合的候选人我也不会对这个吹毛求疵。

    在哪说哪的话而已。
    phpfpm
        265
    phpfpm  
    OP
       2020-08-21 14:55:40 +08:00
    @ipoh 不 他(七十多行)没有。
    不过还是很感谢你给我提了一个 很好的 hint
    我确实是高级语言写久了对一些底层实现忽视了,
    就好比 prefix-string-concat 如果预先 allocation 内存就可以降低复杂度,这我当然知道。

    但是我是带团队做业务的,我做的事情很 low,带着团队写增删改查如果还要关注这个还要不要效率了。
    luxinfl
        266
    luxinfl  
       2020-08-21 14:58:03 +08:00
    话说做算法题目的网站是啥,没了解过
    jiaqiu2003
        267
    jiaqiu2003  
       2020-08-21 15:02:11 +08:00
    @phpfpm 感谢~
    我再想一个
    ygtq
        268
    ygtq  
       2020-08-21 15:16:51 +08:00
    @phpfpm 不等价就写个函数单独处理 undefine 呗,不喜欢这种~~的写法,有点儿奇淫技巧的感觉,增加阅读障碍,在我看来可读性比少那几行重要得多
    realpg
        269
    realpg  
       2020-08-21 15:18:48 +08:00
    说实话,从没关心过长整数加法是怎么实现的。
    也没想过。

    对于任何一个懂编程的人来说,效率不论,就让你做个这玩意,至少功能实现,做不出来的我觉得就是背书党。
    iweisi
        270
    iweisi  
       2020-08-21 15:27:01 +08:00
    太厉害了,你们公司用户数一定很大吧,并发很高吧
    tikazyq
        271
    tikazyq  
       2020-08-21 15:34:48 +08:00   ❤️ 2
    看了这么多评论,很有感触。稍微说几句个人关于面试的看法吧。

    我本人参加过不少面试,也面试过不少候选人。中文的、英文的、家乡话交流的都有;有坐在咖啡馆的,也有在会议室、办公区域的;有很尊重面试者的、积极主动交流的面试官,也有脸上写满了蔑视、不尊重候选人的面试官;其实面试的目的是为了让雇主找到合适的雇员,让优秀的雇员找到满意的雇主,一个相亲过程而已。男女相亲,阅人多了,真的就那么回事,没必要小题大做。

    楼主的标题取得非常有争议性,主要是通过一个事实(写不出一个算法题)作出了一个令人诧异的推论( coding 能力没有),所以不少 v2er 才这么义愤填膺,群起攻之。如果拿相亲来打比方,楼主发的帖子大概是这样的:“刚相亲了一个女的,竟然没看过爱情动作片,是不是生育能力基本没有了?”。这种近乎偏执的观点可以看出楼主非常自傲,在工作中容易吹毛求疵、追求完美,希望找的伴侣都是姿势丰富、长相甜美、还没有性经历的完美女生。这当然也没什么问题,个人喜好而已。如果真的放在工作中的话,可能简单通过这么一道题就判断对方 coding 能力有不有太过草率。

    面试考察一个候选人是否合格,需要在 1 个小时的时间里通过各个维度来询问,特别是技术面试,除非你对某一个方面有特别强烈的偏好,例如算法能力。除了算法,我觉得其他能力也很重要,例如工程能力、架构能力、职业素养、领导力、创新力等等。那些硅谷公司招的都是创意精英,平均 5 轮面试,一般不会通过一个小小的算法题来否定一个面试者。而且,越是大的公司,越看重的是候选人的潜力,而不是当前能力,培养人才也是通常是大公司成功的关键。

    所以,从这方面来看,我觉得楼主可能还需要提高作为招聘者所应有的素质和眼界。总而言之,你只是为公司招人的,招聘出了问题,买单的都是老板。
    phpfpm
        272
    phpfpm  
    OP
       2020-08-21 15:34:53 +08:00
    @realpg 可以不关心啊这没问题。

    算法我给你掰着手指头告诉你算法,然后让面试者实现——绝大多数应试者无法直接想到竖式加法(或者想到了觉得这个简单的不敢相信),我都会给 hint

    但是给出算法,就看 coding 和逻辑了。
    daj2
        273
    daj2  
       2020-08-21 15:39:04 +08:00 via iPhone
    这问的不就是两个链表合并么……
    phpfpm
        274
    phpfpm  
    OP
       2020-08-21 15:47:28 +08:00
    @tikazyq 认同你的看法。

    之前我也谈了挺多了,这道题我自认为能考察的面还是挺广的,代码不难写能看出来一些 coding 的习惯。
    某个候选人写了
    func count(a, b) {
    __...
    __...
    __var count = 0 // 进位
    }

    相加的函数名字叫做 count,进位还是 count 来表示,emm——有点尬呢

    一道题能拿到尽可能多的信息,快速过滤掉不合适的人,这还算有意义。
    一个小时的技术面试(实际上 schedule 要求的就是 45 分钟)这道题至少要占掉 20 分钟左右——这不是干巴巴的他写着我看着,我和面试者是有互动的,我会反复问问题,从中拿到我要的判断。

    我反思我表达的问题,如果一个人从这个贴子学到了"a+b"是一道好题目,他绝对做不好这个面试官。
    从这道题延伸出来的知识体系,细节考量这个是我从长时间的面试总结出来的经验,这个我也没法在一个帖子中写清楚,需要自己感悟。但是至少——我觉得这道题是为了之后的问题展开做一个很好的扩展,是一个好的破冰口。
    phpfpm
        275
    phpfpm  
    OP
       2020-08-21 15:50:14 +08:00
    @iweisi
    @luxinfl leetcode 可以试试国内版
    @ygtq 我不是专业前端,我没法评价;
    一个知道 ~~ 可以更安全的处理一个变量转为整数的前端研发,究竟会不会选择用这个还是 undefined
    我没有这个判断力。
    yishengyongyi
        276
    yishengyongyi  
       2020-08-21 15:50:46 +08:00
    静静的看着你
    jiaqiu2003
        277
    jiaqiu2003  
       2020-08-21 15:52:17 +08:00
    @phpfpm 麻烦看下这个。进位的那个算是抄袭吧。。。实在没想到好的
    function add(a, b) {
    if (a.length > b.length) {
    return add(b, a);
    }
    const prefix = b.substring(0, b.length - a.length - 1);
    return prefix + `0${a}`.split('').reverse().reduce((acc, s, idx) => {
    const carray = acc.length - idx;
    return s * 1 + b[b.length - idx - 1] * 1 + carray + acc.substring(carray);
    }, '');
    }
    phpfpm
        278
    phpfpm  
    OP
       2020-08-21 15:59:56 +08:00
    @jiaqiu2003 try

    add('9999' +'22')?
    tikazyq
        279
    tikazyq  
       2020-08-21 16:04:37 +08:00
    @phpfpm 至少作为考察基础编程素养你这么做的目的应该能达到了,一些没有多少编程经验的一眼就能识破。

    不过看得出来楼主在算法方面颇有造诣,裸写算法在任何技术面试中能考察很多东西。不过能多全面,我不敢保证,除非这个面试岗位偏算法多一些,那应该就是核心技能。裸写算法的缺点也有,就是花的时间太长了,少则 10 分钟,多则半个小时,这些时间足以考察很多其他方面的能力了。通常我在面对多年工作经验的候选人来说会详细根据对方的项目经历来考察技术背景和经验实力,只需要几个问题深入问下去就多少能了解个大概。一场面试下来大概十几个问题,各个方面都考察了,不合适的一般早就 pass 了。

    当然,各个技术公司的文化都不一样,有重视基础科班能力的,例如算法数据结构设计模式之类的,也有重视培养、职业素质、团队协作能力的。萝卜青菜,各有所爱,其实没有对错。

    PS:楼主这标题可以改一改,这样会写显得很自负,如果总是固步自封,算法写得再好,也会做井底之蛙的。
    jiaqiu2003
        280
    jiaqiu2003  
       2020-08-21 16:18:59 +08:00
    @phpfpm 无限进位。。。又 miss 掉一个点。放弃
    phpfpm
        281
    phpfpm  
    OP
       2020-08-21 16:21:57 +08:00
    @tikazyq emm 我觉得这题考不出来什么算法……不过不想再纠结这题的意义了,评论比较分裂,有人说这题就是考算法,有人说这题根本就不算算法,还有人说这题太 naive 了。

    在顺带,贵 v 站不允许改标题,就这么地吧
    我开始也就是想炫技然后吐个槽,没想到这么多人都围观了。
    tikazyq
        282
    tikazyq  
       2020-08-21 16:26:04 +08:00
    @phpfpm v2 上装逼还是挺危险的,心理不强大者,慎装 /doge
    phpfpm
        283
    phpfpm  
    OP
       2020-08-21 16:28:18 +08:00
    @tikazyq 哈哈哈哈哈能装 b 的网站哪个网站我没去过?我今天来不是作为一个面试官,我是作为一个长者,给 v2 的网友一些人生的经验。
    tikazyq
        284
    tikazyq  
       2020-08-21 16:30:19 +08:00
    @phpfpm 你这儿确实也没啥人生经验,反倒是这个帖子的回复给你的经验教训比较多吧
    phpfpm
        285
    phpfpm  
    OP
       2020-08-21 16:40:20 +08:00
    @tikazyq 没有

    :doge:
    jackmrzhou
        286
    jackmrzhou  
       2020-08-21 16:42:51 +08:00 via iPhone   ❤️ 1
    迷惑行为,这么简单的算法题,这都写不好,还指望处理复杂的业务需求?这有啥好喷的?这种算法题写七八十行,写出来的业务代码能优雅到哪里去?找技术专家确实不该问这种,但是找个写代码的,出个这么简单的算法题看看水平有啥问题。
    liuyx7894
        287
    liuyx7894  
       2020-08-21 16:45:39 +08:00
    菜鸡写了一份,速度很慢哈哈

    class Solution:
    def addStrings(self, num1: str, num2: str) -> str:
    res = []
    carry = 0
    current = (0, 0)
    while current != None:
    current = self.add_last(num1, num2, carry)
    if num1 != '': num1 = num1[0:-1]
    if num2 != '': num2 = num2[0:-1]

    if current != None:
    carry = current[1]
    res.insert(0, str(current[0]))
    if carry > 0:
    res.insert(0, str(carry))
    return ''.join(res)

    def add_last(self, num1, num2, forth):
    if len(num1) == 0 and len(num2) == 0:
    return None
    elif len(num1) == 0 and len(num2) > 0:
    return self.add(num2[-1], forth)
    elif len(num1) > 0 and len(num2) == 0:
    return self.add(num1[-1], forth)
    return self.add(num1[-1], num2[-1], forth)

    def add(self, *nums):
    total = reduce(lambda x, y: int(x) + int(y), nums)
    return total%10, math.floor(total/10) if total >= 10 else 0
    phpfpm
        288
    phpfpm  
    OP
       2020-08-21 16:52:20 +08:00
    @liuyx7894 看起来你对 map-reduce 情有独钟

    anyway 不带缩进的 python 代码可读性有点差诶。。。
    byzf
        289
    byzf  
       2020-08-21 17:07:27 +08:00
    意思是你四个字的 ECMA 都能拼成 EMCA, 还要吐槽别人手写了几百个字符有笔误的.
    xiangbohua
        290
    xiangbohua  
       2020-08-21 17:15:08 +08:00
    我觉得一个团队里面什么人都需要,有的人精通算法基础极其扎实,但是业务他不会,刚好你在找一个业务的人,显然这个人就不行;但是如果你需要一个做业务的人,有些极端的基础知识适当放松一点也没什么问题,当然我不是说基础不重要,一些关键岗位的肯定对于基础要求非常高,否则很容易弄出 Bug 。
    每个技术 leader 都希望自己团队的人,各个算法功力很高,人人汇编写操作系统,而且还有产品经理的素质。这显然要付出很高的代价。
    这就有点过于站在技术层面上思考问题了。
    以上是我的看法
    xiangbohua
        291
    xiangbohua  
       2020-08-21 17:24:21 +08:00
    @phpfpm 面试真的还是要看你想要一个什么样的人,用一个可能永远用不到的算法去考验所以不同岗位的人,那么你大概率会损失很多合适的人,除非你是阿里微软之类,或者你在找一个真的,否则,真没必要这么搞。
    你自己也说大多数人都答不上来?你还没有发现,真的熟练手写你这个问题的人,也许不屑于来你们这面试。
    教书都说要因材施教呢
    phpfpm
        292
    phpfpm  
    OP
       2020-08-21 17:25:20 +08:00
    @byzf 你看我 id 嘛


    @xiangbohua 可是我还是觉得这个题吧 要求不高啊。。。
    phpfpm
        293
    phpfpm  
    OP
       2020-08-21 17:26:15 +08:00
    @xiangbohua 嗯,除非……你说对了。。。
    xiangbohua
        294
    xiangbohua  
       2020-08-21 17:27:11 +08:00
    @VeryZero 这话就很中肯,但是很多面试官都难以做到,我也面试过一些人,也经常陷入这个误区,这个也是一个人水平的体现吧,技术好的人这的就不一定能做好面试。
    xiangbohua
        295
    xiangbohua  
       2020-08-21 17:34:44 +08:00   ❤️ 2
    @tikazyq 楼主画像慢慢清晰了:技术可能还不错、略显傲娇、不乐于承认错误、忽略面试的本质
    xiangbohua
        296
    xiangbohua  
       2020-08-21 17:54:26 +08:00
    @phpfpm 要求高不高每个招人的心里都有不一样的衡量,关键是需求匹配。普通业务人员你要这么招的话,千万别让你老板知道。
    XisucksYi
        297
    XisucksYi  
       2020-08-21 17:57:25 +08:00
    @phpfpm 你搞这些算法什么目的, 你本来就是算法岗位的那你搞没问题, 如果你平时做任务根本不用到这个算法你去研究它干什么?

    我觉得一个正常人对于编程的认知应该是这样的:
    1. 目的, 比如 Web 开发, 区块链开发等
    2. 然后再选工具, 比如 Go, .Net, Istio 等(文档看下抓起来就用, 因为一个语言或者其他工具里的所有功能不是你不一定都用得到的)
    3. 最后才是需要什么知识, 比如 computer network, processor(computing )等

    比如平时的排序算法, 用 built-in 的 sort 就行了, 谁还再去 care 什么 bubble sort, heap sort? 纯粹吃太饱. 这么喜欢研究的话, 那你怎么还用 built-in 的 GC 呢? 自己实现一个就行了呗.

    语言和算法都只是工具, 好的工具就是又好用又简单(屏蔽底层复杂性), 如果什么工具都去 care 下底层实现, 这样做有什么意义呢, 你是想自己也能去实现一个? 挣不了钱而且人生苦短.

    你如果纯粹就是出于兴趣去搞算法, 那你是你自己玩下就好了, 可是你拿去面试者面前炫?

    越是没什么就越爱炫什么.
    Rhonin
        298
    Rhonin  
       2020-08-21 17:58:26 +08:00   ❤️ 2
    一路看下来这个楼主真是爱装,遇到打脸的就东拉西扯,block 得了:)
    xiangbohua
        299
    xiangbohua  
       2020-08-21 18:00:11 +08:00
    @phpfpm 虽然我觉得我工资应该比楼主少,职位可能比楼主第,但是我还是觉得这么面试肯定不行的
    phpfpm
        300
    phpfpm  
    OP
       2020-08-21 18:05:55 +08:00
    @Rhonin
    @xiangbohua
    二位瑞思拜。


    @XisucksYi 我实在是 get 不到你的点。
    1  2  3  4  
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   实用小工具   ·   2988 人在线   最高记录 6679   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 84ms · UTC 12:50 · PVG 20:50 · LAX 04:50 · JFK 07:50
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.