记一次小小面试中发生的那一点点波澜

[dlzht]

面试过程

今天面试遇到这样一个问题, 有盒子里放了 n 个球, 上面标记有 1 到 n, 比如 1-9, 现在从里面取出一个, 怎么知道取出的是哪个?

听完问题我停顿了一下, 看下取出球上的标号就可以了吧? 肯定不是, 这么简单还考察什么. 我挠挠头问了下, 是不是不能看取出的球, 而只能看剩下的. 得到的是肯定的答复, 只能看剩下的部分.

那就开始解答吧, 按照我的习惯, 一般是把最直观能想到的方法先抛出来, 然后进一步找优化的思路, 所以给出了第一个方案:

1. 把盒子看作集合, 遍历 1-n, 看看哪个不在集合里, contains 方法是 false 就可以了

然后脑子里在想的是, 是不是从内存使用方面去考虑, 我联想到了 flag 的判断, 比如 linux 的文件权限, 读写执行, 所以我马上给出了第二个方案:

2. 1-n, 比如 1-9, 可以用一个 int 表示盒子里的情况, 最开始是最低的 9 个为都是 1, 取走一个, 某一位就变成 0 了, 找到最低位的 0 在哪个位置就可以了

因为依稀记得之前写 Rust 是用过 trailing_ones(计算尾部有几个 1), 结合上面的 flag 思路, 就很顺利地给出了这个改进方案.

面试官停顿了一会, 说有没有其他的方法, 如果这个 n 很大呢.

我马上想, 数量很大, 难道是问布隆过滤器么, 也不对啊, 布隆过滤器不一定能给出正确答案吧. 所以我觉得面试官的这个提示可能是因为我用了 int, 但我不确定, 所以我给出了第三个答案的时候附加了一个小条件.

3. 如果要精确地找出是哪个球的话, 考虑到 int 的位长, 在 n 可能很大的情况下, 可以用位图去记录盒子的情况

但显然我的答案不是面试官期待的, 问我还有没有其他的方法. 难不成要从真实的球的问题, 这时我脑海里又浮现了"几堆砝码, 其中一堆少一个", 或者"很大的文件, 怎么有效处理"之类的问题, 分而治之.

所以我就试探着问了下, 盒子里面有小盒子吗? 因为我想先分成批次, 然后找到需要处理的那一批, 最后单独处理那一批, 这样也算是一种优化. 但依然不对路子, 面试官给了否定的回答, 没有子盒子.

我又想了想, 之前第二种方案, 我是把“取走”这个操作看作 bit 置为 0 的操作. 如果是一个已知的数集合, “取走”就是去掉一个数, 哦, 这个我知道, 所以给出了第四个方案.

4. 遍历 1-n(当时这边说错了), 然后遍历剩下的, 做异或操作, 最后剩下的就算取走球的标号

我当时思绪有点多, 属于是多线程并发了, 讲得不太清楚, 把遍历 1-n, 说成了求和. 当时面试官怎么说的, 具体不太记得清了, 没有肯定, 也没有否定, 只是让我想想有没有其他的方法.

我想了一会, 没找到下一步的方向, 只能暂且作罢了, 不过心里还是记着. 最后面试结束, 在"你还有什么想问"环节, 我就问这个球问题的解法是什么.

5. 面试官说我想得有些复杂了, 给出的答案是, 先计算 1-n 的和, 然后计算剩下球标号的和, 两个相减就可以了

这样我就明白了, 这其实和第四个想法是一样的, 不过我的做法可能更有效率, 嘿嘿(不过说错了, 我的锅, 唉). 虽然一时间有点语塞的感觉, 和面试官说, 我上面的解法和这个是一个意思, 面试官好像说了下不置可否的嗯, 到此也就结束了这场面试.

一些想法

其实给出第二种方案前, 我也飘过用异或去解的想法, 不过脑子里一过, 这种方法也需要“笨拙”的遍历, 所以没有先说这种方案, 是我的问题么?...

这次面试并不成功, 有些问题我回答的不好, 比如讲一下 Java 内存模型, 我没有答上来. 一方面我想转向 Rust, Java 方面准备地不充分; 另一方面, 刚刚开始面试, 还得查漏补缺.

没有想吐槽什么, 我理解现在的现实就是这么个情况, 面试官和面试者都不容易(肯定有 v 友两个角色都当过), 表达清楚自己的意思不容易, 两个人要踩到同节奏上也不容易, 理解另一个想法更是需要广阔的视野和敏锐的知觉.

v 友求助, 嘿嘿

我也不容易呀, 饭碗肯定是没有了. 厚着脸皮一笑, 嘿嘿, v 友们有没有可以捞一捞的, Rust 或者 Java 方面的, 工作负责, 物超所值呀...唉, 不, 乐观

[tianshuang]

题号：268 ，难度：简单，参考： https://leetcode.cn/problems/missing-number/description/

[dlzht]

@tianshuang 题怎么解我知道, 思考的角度不一样

[iOCZS]

如果标注一下是 easy ，也许就容易想了，大力出奇迹。
如果进位对结果有影响，异或就不太可行，毕竟求和是带进位的异或。

[wuyadaxian]

别在意，如果面试官给我说这个数很大，我可能会考虑为 bigint 。
有些情况下求和相减的时间和空间复杂度可能并不是很好。

[sagaxu]

面试官：“我偶然看过的题你必须都会”

[zhuisui]

你这四个答案在空间复杂度的层面，都是没有区别的，都需要 n ，而面试官的答案是 log(n)。
对于 n, 面试官的算法中，求和占用的空间是 n*(n+1)/2 ，二进制位数是 log2(n*(n+1)/2)

至于时间复杂度，都一样，是 n.

面试官说你想复杂了我觉得不够提示明确，直接说这个算法不好得了。

[dlzht]

@iOCZS 是的, 或者直接说数和集合, 用具体的物件反抽象, 然后再抽象回去, 理解就可能会有变形了. 感谢兄弟提醒"进位"的问题!

[dlzht]

@wuyadaxian 是, 具体到某个问题, 很多时候只要能解决就够了, 哈哈哈

[dlzht]

@sagaxu 我也能理解, 嘿嘿, 小事

[dlzht]

@zhuisui 我没有很明白你的意思, 可能是我理解有误. 空间方面, 需要保存原来的数字(假设 int)的方案, 即第 1 和第 4, bit 相比与 int, 应该是更有优势的, 因为缺少的数字不多. 求和的方式在连续数字上更有优势, 直接用求和公式.

[zhuisui]

@dlzht 不管第一还是第四，你都需要 n 个空位去存储这 n 个数字，不论是 number 还是 bit 。求和需要的 bit 位数上面说了。
这个题要求的就是 1-n 的连续数字，不是别的情况。

[BanGanExpert]

我当初做这道题也是第一时间想到位进制的异或，反而没想到加法，不过加法还要考虑溢出，主要这种一下就想到就是掩码相关的作用，题主第一时间没相当应该是位运算很少用。而“笨拙”的遍历，本质是你要把数都访问一遍，肯定会都会遍历 1 遍，很多时候考虑的关键操消耗，比如排序就是比较次数，不代表这个数你没访问总共 n 次呀。

[dlzht]

@BanGanExpert 确实平时刷题不多, 位运算用得也少, 见笑见笑

[dode]

线性代数里有矩阵，数据结构，稀疏矩阵怎么存储


线段树是一种二叉搜索树，与区间树相似，它将一个区间划分成一些单元区间，每个单元区间对应线段树中的一个叶结点。
使用线段树可以快速的查找某一个节点在若干条线段中出现的次数，时间复杂度为 O(logN)。而未优化的空间复杂度为 2N ，实际应用时一般还要开 4N 的数组以免越界，因此有时需要离散化让空间压缩。

[dode]

数很大的话，求和不会溢出吗

[rainbowismagic]

大学时候学过荷兰三色国旗那个算法，感觉这一类都是类似的。边遍历边调整位置。

[me1onsoda]

抬个杠，既然说 n 很大，那么加起来有没有可能溢出呢

[dlzht]

@me1onsoda @dode 是可能会有溢出问题