V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
V2EX 提问指南
mypchas6fans
V2EX  ›  问与答

请教一个笔试题以及评价标准

  •  
  •   mypchas6fans · 2019-08-24 13:10:31 +08:00 · 1738 次点击
    这是一个创建于 1678 天前的主题,其中的信息可能已经有所发展或是发生改变。

    远程面试一个 QA 职位,给了一道 codility 的题,限时 60 分钟

    内容记得不是很确切,关键词叫 binarian,大意是给一个正整数数组,对每个 i 取 2^i 然后求和,比如[0,1,2,3]得到 1+2+4+8=15,然后问有没有更短的数组得到 15 这个目标值。

    我用了 20 多分钟写了个 python,基本思路是算出目标值,然后简单的贪心算法,如 15 对 2 取对数然后向下取整得到 3,15-2^3=7,继续递归加起来。反正有 2^0=1 兜底,肯定能得到一个数组。然后看是不是比原数组更短。 测试了几组数感觉没什么大问题。

    然后,我就被灭了……算法和刷题确实做得少,我估计大概有动态规划什么的可以得到最优解? 但是我就想知道,我的做法有没有什么问题,以及我连面试机会都没了算是啥水平……

    求轻拍。

    7 条回复    2019-08-24 17:05:39 +08:00
    smdbh
        1
    smdbh  
       2019-08-24 13:24:22 +08:00
    垃圾公司。正常的套路应该是你给个算法,一般是 n2 级别,然后被面试官不断提问,然后改进么
    geelaw
        2
    geelaw  
       2019-08-24 13:52:47 +08:00 via iPhone
    这个是一个简单题目,是楼主自己想复杂了

    答案 = 在最后的数的二进制展开里有多少个 1
    geelaw
        3
    geelaw  
       2019-08-24 14:05:45 +08:00 via iPhone
    @geelaw #2 刚看了一下楼主的解法,也是对的 - - 然而转换成二进制的方法比常见的要麻烦好多。我觉得面试者希望的算法应该是对原来的数组排序后直接算出答案,不要经过算出目标值的过程(因为可能要引入大整数计算)。

    方法是反复替换数组里的一对 a 为一个 a+1,直到数组里的数互不相同,此时数组的长度就是答案。
    mypchas6fans
        4
    mypchas6fans  
    OP
       2019-08-24 14:30:20 +08:00
    @smdbh 大概没说清楚?是线上 coding 测试。
    mypchas6fans
        5
    mypchas6fans  
    OP
       2019-08-24 14:33:39 +08:00
    @geelaw 感谢,确实是这两种思路应该更快
    minmini
        6
    minmini  
       2019-08-24 14:43:13 +08:00 via Android
    现在 QA 也要面算法了吗?看来要时不时去刷点题了😨
    1608637229
        7
    1608637229  
       2019-08-24 17:05:39 +08:00
    最短就是转换二进制后看有几个 1。转换成二进制后这个数字有几个 1 组成就是最短了。
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   我们的愿景   ·   实用小工具   ·   951 人在线   最高记录 6543   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 25ms · UTC 21:49 · PVG 05:49 · LAX 14:49 · JFK 17:49
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.