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

工作五年的游戏后端不知道排序算法的复杂度正常吗?

  •  
  •   Rooger ·
    luojiego · 70 天前 · 13545 次点击
    这是一个创建于 70 天前的主题,其中的信息可能已经有所发展或是发生改变。

    最近又要开始招聘了,一直以来,这个问题非常困惑我。有个候选人简历上写着:熟练掌握数据结构和算法。 我问那常见的排序算法有哪些,只说出一个,快速排序。我问那时间复杂度是多少,他说 O(logN)。我无语了。 其实面试了这么多,这个是最让我疼的。毕竟说 O(N),还不是太离谱。

    168 条回复    2022-10-16 09:17:28 +08:00
    1  2  
    billlee
        1
    billlee  
       70 天前 via Android   ❤️ 2
    不正常,稍微有点逻辑都能想到这个至少有 n 吧,至少每个元素要访问一下啊
    hangbale
        2
    hangbale  
       70 天前   ❤️ 3
    肯定有人说正常
    lix7
        3
    lix7  
       70 天前   ❤️ 1
    hhhh 科班出身的话不应该。转行的其实我觉得倒也正常,毕竟干活儿也确实不用自己写快排,但不表示这可以接受
    microxiaoxiao
        4
    microxiaoxiao  
       70 天前 via Android
    不知道就不知道呗。也不影响调用,你越问越紧张。疑人不用,用人不疑。
    villivateur
        5
    villivateur  
       70 天前
    不正常,这种最最基础的问题,我觉得就算一直用不到,也不可能忘掉
    coderluan
        6
    coderluan  
       70 天前   ❤️ 1
    你要是问常见不常见,我说不常见。你问正常不正常,我说很正常。
    sadfQED2
        7
    sadfQED2  
       70 天前 via Android   ❤️ 12
    😂😂所以我简历上从来不敢写数据结构和算法
    yibo2018
        8
    yibo2018  
       70 天前
    后端 5 年,觉得知不知道根本无所谓
    JohnBull
        9
    JohnBull  
       70 天前   ❤️ 7
    我面试那些号称 N 年工作经验的废物们,没几个人能写出二叉树遍历伪码的.
    所以我早就看明白了,现在团队招人优先 211 及以上学校的应届生.
    zoharSoul
        10
    zoharSoul  
       70 天前
    正常 知道不知道有啥影响吗?
    lzgshsj
        11
    lzgshsj  
       70 天前   ❤️ 5
    不正常。不知道的简历上为什么要瞎写。
    不知道就别写什么“熟练掌握数据结构和算法”,写了就要有被问到的准备。
    dog82
        12
    dog82  
       70 天前   ❤️ 2
    大家都是写 CRUD 的,不要互相瞧不起,现在谁会在工作中写排序算法?
    ChefIsAwesome
        13
    ChefIsAwesome  
       70 天前 via Android   ❤️ 14
    正常。但是他写简历里说他熟悉,那不正常。
    我就老实承认,高中数理化我就没几个知识点还记得的,古诗词我也没几个能背出来的。这并不代表我当时考试作弊,也不影响我现在的工作。
    zhady009
        14
    zhady009  
       70 天前   ❤️ 1
    @lzgshsj 同意这点而且 OP 也没问很难的问题
    q474818917
        15
    q474818917  
       70 天前
    @dog82 我还是比较认可这位说的,都是打工仔,何苦为难打工仔呢?招个听话的他不香吗
    Pythoner666666
        16
    Pythoner666666  
       70 天前
    我觉得 面试还是要好好准备下的吧
    icyalala
        17
    icyalala  
       70 天前
    不是正不正常的问题,是你或你的公司接不接受的问题。
    你看某人反转转二叉树都不会呢 (doge)
    yancy0l
        18
    yancy0l  
       70 天前
    科班出生,本科。学校学的时候学的很清楚。毕业面试的时候,准备过一次。工作四年了,现在确实不记得了。但是简历上写了,但是自己不知道,可能是没准备,应该是面试者的问题
    majula
        19
    majula  
       70 天前   ❤️ 1
    不正常。就算是没有接触过计算机技术的人,仅靠朴素的逻辑思维也应该知道,每个元素至少需要访问一次。

    所以我猜对方可能是因为太紧张口误了。以后遇到这种情况,可以试着追问一下,让他简单描述一下算法。
    djoiwhud
        20
    djoiwhud  
       70 天前 via Android
    挺正常的。我读书的时候至少可以用 c 手写五种排序算法。

    工作 12 年,语言级的数据结构用久了,平时很少有机会要自己造排序算法。现在也就可以正常写冒泡排序。忘了不是很正常么?

    主要是他为什么要写在简历上。
    loryyang
        21
    loryyang  
       70 天前
    本科读什么,决定了他在这方面的知识储备。每年校招面试,基本上看简历就能大概知道,面试者对这些基础知识的掌握程度了
    掌握这些东西,不是说工作中都会用到,但能证明,你受过专业的思维训练,能对日常需求进行更好的抽象,在编码过程中,做更清晰的设计,避免写出一大坨面条代码
    我也看了很多人写的代码,质量差距可以说是非常巨大的
    wowcz
        22
    wowcz  
       70 天前
    工作几年的早忘记有几个排序算法了,脑海中也对应不起来哪个排序怎么写的,时间复杂度是啥
    zdt3476
        23
    zdt3476  
       70 天前
    会忘很正常,用不上也正常。不过面试前稍微准备下就好了。
    anonymousar
        24
    anonymousar  
       70 天前
    不正常 这是常识。
    就像一个厨师不可能不记得 蚝油的作用。类似问题。
    anonymousar
        25
    anonymousar  
       70 天前   ❤️ 1
    @icyalala 不要偷换概念 Max Howell 不是不会反转二叉树 概念原理都是知道的 只是没能在白板上 ac 。
    janus77
        26
    janus77  
       70 天前   ❤️ 1
    这种问题 支持的人有支持的原因,不支持也有不支持的理由。其实看你自己就行了,我觉得你自己肯定心里已经有答案只是来找认同而已吧?没必要啊,你是面试官,你想挂他挂就是了,他也不会上来发帖挂你
    lozzow
        27
    lozzow  
       70 天前
    @anonymousar #23 类比应该是蚝油的做作过程和注意事项对蚝油风味的影响
    shawnsh
        28
    shawnsh  
       70 天前 via Android
    常识问题,他计算机基础知识不行。
    Kasumi20
        29
    Kasumi20  
       70 天前   ❤️ 2
    时间复杂度和手写的难度成反比,如果你很难写出来,那它就是 nlogn ,如果你闭着眼睛写出来,那它就是 n^2
    zhaorunze
        30
    zhaorunze  
       70 天前
    gg ,我也一直以为 O(logN) 呢,刚搜了一下好像不是的。我认为找工作的时候不知道不正常,但是工作了半年不打算看看机会的不知道很正常。。。
    Rooger
        31
    Rooger  
    OP
       70 天前
    @majula 追问了,不可能不给人家任何解释的机会。聊了下,他也发现,不可能连一次遍历都没有做完就能排好序。
    Rooger
        32
    Rooger  
    OP
       70 天前
    @q474818917 嗯,的确用这种想法招过人。遇到一位态度挺好,但是没有办法正常完成工作,最后劝退了。影响了候选人,其实也浪费我大量的时间来填他的坑,整整一个月,我都没有怎么好好休息过,弄的我的颈椎难受一周了。说实话,我也不想有太高的要求,但是有时候感觉互相坑了彼此。
    lzgshsj
        33
    lzgshsj  
       70 天前   ❤️ 5
    怎么上面都一本正经的在讨论是不是真的懂不懂复杂度呢。

    计算机能问的题目多了去了,每一个问题有人会,有人不会都是很正常,和几年经验也没什么关系,大多数人都是能写自己工作需要的业务就行。

    在我看来这个问题的本质就是讨论 “简历上该不该写自己不会 /没准备的技能”。

    说严重点,写自己精通 /熟练掌握 xxx 技能,结果连这个技能的基础问题都答不出,算不算简历造假?

    当然,很多公司的 jd 也是随手要求就是精通 /熟练掌握,还以为开的工资又多高呢。

    总之也是双向选择了。
    zooeymango
        34
    zooeymango  
       70 天前
    既然他简历上写了,起码应该准备一下,如果这种简单问题都没答上来,说明根本没怎么准备,面试的态度不是很认证、渴求的状态吧,相应的可能会被企业列在不优先考虑的名单里,但是这种情况我觉得也不少吧,没必要还发帖质疑,好多人面试不准备自己也不知道自己到底想要什么,挺常见的
    bloomy8
        35
    bloomy8  
       70 天前
    正常,但不符合你们的要求
    zhangyichent
        36
    zhangyichent  
       70 天前
    我就记不得了。。。我连快速排序是个什么原理都完全忘了。。。
    MoYi123
        37
    MoYi123  
       70 天前
    不懂没关系, 反正 google5 分钟就能知道答案, 但是吹自己熟练掌握数据结构和算法就不对了.
    lovedebug
        38
    lovedebug  
       70 天前
    这一类死记硬背的知识,不用忘了很正常啊
    lambdaq
        39
    lambdaq  
       70 天前
    本来想怼 LZ 的,结果发现 「候选人简历上写着:熟练掌握数据结构和算法。 」

    啊。。那没事了。该
    Hurriance
        40
    Hurriance  
       70 天前
    如果是有编程环节的话,可以让候选人先写个他会的排序,再让他分析时空复杂度,引导他吧。
    changnet
        41
    changnet  
       70 天前   ❤️ 2
    我也是游戏后端,我也面别人,最讨厌直接问这种问题。平时都是根据业务要求做,不是设计基础组件谁会关注这个,我自己也不知道它复杂度是多少啊,除非我准备跑路刷题。

    面试初中级,排序是必问,但我一般都是问,游戏里某个 xx 排序功能,如果让你来实现,你会用哪种算法。只要他能根据业务采用使用合适的算法,并理解这个算法的效率、稳定性,都算过。那怕实际上不是最优的解决方案
    Leviathann
        42
    Leviathann  
       70 天前
    这种基础算法的复杂度问题一般是 0 容忍
    排序是一个很高频的操作,每个高频操作都应该至少知道 big O
    Arrowing
        43
    Arrowing  
       70 天前
    正常,但是不懂装懂就不太好
    Leonard
        44
    Leonard  
       70 天前   ❤️ 5
    我想到 Homebrew 作者 Max Howell 不会反转二叉树被 Google 拒绝 😂

    这些东西平时用不上,记性不好的人时间久了记错了也没啥,不过还是要看整体水平如何
    pengtdyd
        45
    pengtdyd  
       70 天前
    如果候选者的简历上明确写着《熟练掌握数据结构和算法》,那答不上来就说不过去了。如果没写答不上来,确实情有可原,每个人的经历不同,技能树也点的也不一样,毕竟术业有专攻。但答不出来也从另一个方面反映出了候选者并没有认真的对待自己的简历。
    LuckiSnow
        46
    LuckiSnow  
       70 天前
    对于一个去面试的人来说,不正常,就算工作上用不到,面试前准备下常见的算法和数据结构,对自己和面试官都是起码的尊重,不然问点 OP 提到的基础问题,答不上来,真的双方都很尴尬。
    arthas2234
        47
    arthas2234  
       70 天前
    人有多大胆,地有多大产
    唬住 50K ,唬不住 5K
    vone
        48
    vone  
       70 天前
    所以他的时间复杂度是什么
    pengtdyd
        49
    pengtdyd  
       70 天前
    我曾经遇到过来面试 JAVA 开发,简历上却写着熟悉,js ,html,css ,我就问了几个 js ,html ,css 的基础问题,结果他没答上来,然后就挂了。如果简历上写了然后你又不会,被问到答不上来,是非常减分的行为,简历上别夸大,如果不会的真的不要往上写。
    kkbblzq
        50
    kkbblzq  
       70 天前
    不管正不正常,这样的点在面试的时候出现,就是一个比较大的扣分点,就个人拙见来说:就算是一个比较合格的后端开发,我觉得也应该对复杂度有一个大概的认知;何况还是对性能更敏感的游戏后端。
    xnotepad
        51
    xnotepad  
       70 天前
    刚毕业那会儿知道,现在我也不记得了。。。
    wangritian
        52
    wangritian  
       70 天前
    会调用排序函数就行,但不能容忍瞎吹牛逼
    newmlp
        53
    newmlp  
       70 天前
    知不知道根本无所谓,
    glfpes
        54
    glfpes  
       70 天前
    这玩意如果都不知道,根本不可能做性能优化。
    icyalala
        55
    icyalala  
       70 天前
    @anonymousar Max Howell 自己在 Quora 上写了它不知道二叉树:
    "I wasn’t very clear what a binary tree was. I studied Chemistry not Comp-Sci."
    wupher
        56
    wupher  
       70 天前
    - 日常工作中真记不得了,一般有疑问的时候上网现查。

    - 准备面试应该会先看一回儿,算基本知识吧

    - 其实日常工作和面试使用的技术脱节挺大的,比如说 hashMap
    sunmker
        57
    sunmker  
       70 天前
    我发现我也忘记了,我当时毕业的时候会的,哎不说了,不摸鱼了
    angryfish
        58
    angryfish  
       70 天前
    个人觉得,有几个方面的原因。
    1.曾经数据结构和算法很厉害,但是工作太久了,又没用过,忘光了,没想到面试会被问到这么基础的东西。
    2.这是他随便投的简历,没来得及复习,就被你们喊过去面试了,有点你们常说的“裸考”感觉
    3.他瞎写的技能
    djyde
        59
    djyde  
       70 天前
    我也是经历过从没有受过算法和数据结构训练到刷了不少 easy 到 medium 的题目。工作(业务)中确实很少直接用到算法和数据结构,但它是一个你学了之后会打开你的思路的东西.

    它就像一个工具箱,不一定经常在代码里会用到,但如果你根本没有这些工具,你就失去了解决问题的很多思路。而且别人也很难向你证明习得基本的算法和数据结构对你写代码会有什么帮助。就像我经常看到很多人连打字的指法都是乱来的,我也很难向他们说明正确的打字指法可以如何帮助他们更快地打字。

    有一句话叫 You don't know what you don't know. 无论是算法数据结构还是正则表达式还是正确的打字指法,都是我亲自习得了才懂得它们给我带来的效益。这些效益不是 0 到 1 的差别,所以很多人会选择忽略它们。回过头看我以前对算法的不屑,都觉得自己很愚蠢,即使我到现在都没在工作中直接用到过算法。
    nicebird
        60
    nicebird  
       70 天前
    正常又不正常。很多游戏后端就是逻辑仔,不知道很正常。不正常的是应付面试,背一背就好了。
    vishun
        61
    vishun  
       70 天前   ❤️ 1
    应该是快速排序是用的二分法,二分法是 log(n),所以顺口就说了这个。
    loolac
        62
    loolac  
       70 天前
    正常,这个复杂度写代码时又用不到。 没人会写代码时还要考虑复杂度的,在重构或者优化时才会去考虑算法的效率问题,但实际这个复杂度也用不到。大概只有在评估一个算法的时候才会想到有这个东西。
    frostming
        63
    frostming  
       70 天前
    不说算法有没有用,他简历上写了,问了又不知道,这能怪谁
    god7d
        64
    god7d  
       70 天前
    工作 5 年的话不知道其实是不太应该的,因为在这个工作年限,或多或少要接触到架构方面的工作,不清楚这些基础知识是不能够胜任的
    pkoukk
        65
    pkoukk  
       70 天前
    不正常,非常不正常
    nekoneko
        66
    nekoneko  
       70 天前
    @nicebird #60 我还以为游戏后端需要超强的算法能力呢, 比如说自动寻路(最短路径, 耗时最少等等), 背包整理(大菠萝那种背包), 还有什么神经网络, 遗传算法等等.
    11232as
        67
    11232as  
       70 天前
    工作两年了,算法还能记得怎么写,但估计边界条件那部分会烂得一塌糊涂
    nah
        68
    nah  
       70 天前
    我觉得面工作五年的人还要问排序本身就不正常。
    yisiliu
        69
    yisiliu  
       70 天前   ❤️ 4
    我觉得大家也还是要尊重一点面试的,问的这种题都是最基础的认知,又没有问什么很 tricky 的题目,又不要求去刷 leetcode ,问个排序能说出 O(n) 甚至 O(log n) 是不是未免有点不过大脑了,以至于很怀疑日常真的写代码的时候对于自己代码的认知是不是也是如此。。
    skadi
        70
    skadi  
       70 天前
    肯定是有问题的...
    beneo
        71
    beneo  
       70 天前
    你家 CTO 肯定不知道
    736531683
        72
    736531683  
       70 天前
    如果他会的足够牛逼,非在意这些干嘛呢
    CookCoder
        73
    CookCoder  
       70 天前
    招人是一个玄学课题
    tairan2006
        74
    tairan2006  
       70 天前
    偏理论的问题少问,多问工程性问题
    anonymousar
        75
    anonymousar  
       70 天前
    @icyalala 我记得是他在推回复说 “也不是啥难题 不就是 recursion 什么的” 大概是我记错了
    liuxingdeyu
        76
    liuxingdeyu  
       70 天前
    我觉得不正常,如果不会算法,那不知道正常,如果知道了不会算 O(n),那水平就有点水
    imsoso
        77
    imsoso  
       70 天前
    说明没有准备
    assad
        78
    assad  
       70 天前
    刷个题,做个功课,面试还是必须要准备一下的
    sy20030260
        79
    sy20030260  
       70 天前
    结合公司的招聘情况看了,一般情况遇到这种程度的基础可以 pass 了。但如果短期实在缺干活的人,或者公司能开出的薪资水平本来就比较一般,那还可以试试挖掘面试者其他方面。例如稍微引导一下面试者,如果他能说出快排的基本思路,能通过代码写出基本 bug free 的版本,而且代码风格还不错,那至少说明思维和代码能力不错,属于能实际上手干活的那类人,那还可以往这方面继续考察考察。毕竟面试过程看的不是某个单一问题的回答,而是不同方面能力的综合考察和综合判断
    westoy
        80
    westoy  
       70 天前
    罗翔说过一个段子

    为了预防替考, 很多双一流在高考期间会禁止大一新生出校, 但是对大二的就没什么限制了.............
    yhxx
        81
    yhxx  
       70 天前
    我前几天也被问到了这个。。也是这么说的。。。绝大部分时候这个纯粹是口误吧,继续聊一下应该就意识到了
    ranleng
        82
    ranleng  
       70 天前   ❤️ 1
    我觉得可以记不清是 Big-O 多少,但怎么可能是 O(lgN),基于对比的排序算法都不可能是低于 O(N * lgN) 的
    tudouxiong
        83
    tudouxiong  
       70 天前 via Android
    不正常
    cnoder
        84
    cnoder  
       70 天前
    应该是口误了,简单想一下就知道不会是 logn
    lululau
        85
    lululau  
       70 天前
    好奇你们做游戏开发的都需要自己写排序算法吗,你们用的啥语言开发,标准库里没有现成的排序函数吗
    lmshl
        86
    lmshl  
       70 天前
    我现在大概只能默写出来一种我也说不上来名字的排序算法,大概率是 O(nlogn) 的
    但这并没有什么意义,我觉得真正的竞争力在于,给对方一个 wiki 页面或者伪代码,论文链接,对方能否在有限时间内(比如 48h )学会并实现出来。

    背过这些算法有什么用呢?你们在刷 leetcode 和面试之外的场景,真的有用到这些算法么?给 lc 选手一个 Miller–Rabin primality test 的 介绍,有几个人能仿写出来?
    darkengine
        87
    darkengine  
       70 天前
    我觉得应该给一段代码,让他现场分析时间复杂度和空间复杂度。
    fzdwx
        88
    fzdwx  
       70 天前
    如果我猜的没错的话是 n ^ 2 ?
    ashin
        89
    ashin  
       70 天前
    快速排序是啥我都想不起了-。-咋办
    lumotian
        90
    lumotian  
       70 天前
    说明工作比较稳定,不经常需要出来面试
    SekiBetu
        91
    SekiBetu  
       70 天前
    百度一下就有了的东西,应届生八股文都背熟了
    invalid
        92
    invalid  
       70 天前
    五年游戏前端也记不得几个算法了
    zengguibo
        93
    zengguibo  
       70 天前
    面试的时候造航天飞机,工作了只是个拧螺丝而已
    DerekLin1994
        94
    DerekLin1994  
       70 天前
    @Rooger 为啥我就预不到你这种老板,虽然我是非科班,但干活不比普通的差,可惜面试真不太会准备,不喜欢八股文,当然我也认为基础还是很重要的,毕竟决定能走多远。
    Anarchy
        95
    Anarchy  
       70 天前
    也不算太离谱 nlogn 你突然问然后就记得有个 logn 了。感觉这种属于比较明显记忆出现些错误,可以简单提点下看有没有正确回答。
    mywaiting
        96
    mywaiting  
       70 天前   ❤️ 2
    这有啥,SQLite 作者开始写这货的时候,连 B-tree 也不会,不一样折腾出来了~
    ShinCurry
        97
    ShinCurry  
       70 天前
    面试与笔试不同之处就在于可以沟通交流。在帖子描述的这种情况下,再追加要求说明一下得出复杂度的分析过程,能更好的考察面试者。并不是每个人都能做随时随地思维缜密毫不紧张的,给一些改正的机会总是好的。
    witcat
        98
    witcat  
       70 天前 via iPhone   ❤️ 3
    现在面试答不上来题还要被人背后念叨啊。咋隔三差五就有这种帖子。
    ijrou
        99
    ijrou  
       69 天前
    我觉得不正常,,,
    cassyfar
        100
    cassyfar  
       69 天前
    o(logN) 那说明他是真的不懂 Big O 基本含义。。。等于说不用知道所有数,也能严格排序,这不是预言家吗?
    1  2  
    关于   ·   帮助文档   ·   API   ·   FAQ   ·   我们的愿景   ·   广告投放   ·   感谢   ·   实用小工具   ·   1240 人在线   最高记录 5497   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 60ms · UTC 20:31 · PVG 04:31 · LAX 12:31 · JFK 15:31
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.