远程面试一个 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 兜底，肯定能得到一个数组。然后看是不是比原数组更短。 测试了几组数感觉没什么大问题。
然后，我就被灭了……算法和刷题确实做得少，我估计大概有动态规划什么的可以得到最优解？ 但是我就想知道，我的做法有没有什么问题，以及我连面试机会都没了算是啥水平……
求轻拍。
 | 1 smdbh Aug 24, 2019 垃圾公司。正常的套路应该是你给个算法，一般是 n2 级别，然后被面试官不断提问，然后改进么 |
 | 2 geelaw Aug 24, 2019 via iPhone 这个是一个简单题目，是楼主自己想复杂了 答案 = 在最后的数的二进制展开里有多少个 1 |
| 3 @geelaw #2 刚看了一下楼主的解法，也是对的 - - 然而转换成二进制的方法比常见的要麻烦好多。我觉得面试者希望的算法应该是对原来的数组排序后直接算出答案，不要经过算出目标值的过程（因为可能要引入大整数计算）。 方法是反复替换数组里的一对 a 为一个 a+1，直到数组里的数互不相同，此时数组的长度就是答案。 |
 | 4 mypchas6fans OP @smdbh 大概没说清楚？是线上 coding 测试。 |
| 5 mypchas6fans OP @geelaw 感谢，确实是这两种思路应该更快 |
 | 6 minmini Aug 24, 2019 via Android 现在 QA 也要面算法了吗？看来要时不时去刷点题了 |
 | 7 1608637229 Aug 24, 2019 最短就是转换二进制后看有几个 1。转换成二进制后这个数字有几个 1 组成就是最短了。 |
Select Language