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

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

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

    面试过程

    今天面试遇到这样一个问题, 有盒子里放了 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 方面的, 工作负责, 物超所值呀...唉, 不, 乐观

    18 条回复    2024-06-01 11:54:17 +08:00
    tianshuang
        1
    tianshuang  
       50 天前
    题号:268 ,难度:简单,参考: https://leetcode.cn/problems/missing-number/description/
    dlzht
        2
    dlzht  
    OP
       50 天前
    @tianshuang 题怎么解我知道, 思考的角度不一样
    iOCZS
        3
    iOCZS  
       50 天前
    如果标注一下是 easy ,也许就容易想了,大力出奇迹。
    如果进位对结果有影响,异或就不太可行,毕竟求和是带进位的异或。
    wuyadaxian
        4
    wuyadaxian  
       50 天前
    别在意,如果面试官给我说这个数很大,我可能会考虑为 bigint 。
    有些情况下求和相减的时间和空间复杂度可能并不是很好。
    sagaxu
        5
    sagaxu  
       50 天前   ❤️ 1
    面试官:“我偶然看过的题你必须都会”
    zhuisui
        6
    zhuisui  
       50 天前
    你这四个答案在空间复杂度的层面,都是没有区别的,都需要 n ,而面试官的答案是 log(n)。
    对于 n, 面试官的算法中,求和占用的空间是 n*(n+1)/2 ,二进制位数是 log2(n*(n+1)/2)

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

    面试官说你想复杂了我觉得不够提示明确,直接说这个算法不好得了。
    dlzht
        7
    dlzht  
    OP
       50 天前
    @iOCZS 是的, 或者直接说数和集合, 用具体的物件反抽象, 然后再抽象回去, 理解就可能会有变形了. 感谢兄弟提醒"进位"的问题!
    dlzht
        8
    dlzht  
    OP
       50 天前
    @wuyadaxian 是, 具体到某个问题, 很多时候只要能解决就够了, 哈哈哈
    dlzht
        9
    dlzht  
    OP
       50 天前
    @sagaxu 我也能理解, 嘿嘿, 小事
    dlzht
        10
    dlzht  
    OP
       49 天前
    @zhuisui 我没有很明白你的意思, 可能是我理解有误. 空间方面, 需要保存原来的数字(假设 int)的方案, 即第 1 和第 4, bit 相比与 int, 应该是更有优势的, 因为缺少的数字不多. 求和的方式在连续数字上更有优势, 直接用求和公式.
    zhuisui
        11
    zhuisui  
       49 天前
    @dlzht 不管第一还是第四,你都需要 n 个空位去存储这 n 个数字,不论是 number 还是 bit 。求和需要的 bit 位数上面说了。
    这个题要求的就是 1-n 的连续数字,不是别的情况。
    BanGanExpert
        12
    BanGanExpert  
       49 天前
    我当初做这道题也是第一时间想到位进制的异或,反而没想到加法,不过加法还要考虑溢出,主要这种一下就想到就是掩码相关的作用,题主第一时间没相当应该是位运算很少用。而“笨拙”的遍历,本质是你要把数都访问一遍,肯定会都会遍历 1 遍,很多时候考虑的关键操消耗,比如排序就是比较次数,不代表这个数你没访问总共 n 次呀。
    dlzht
        13
    dlzht  
    OP
       49 天前
    @BanGanExpert 确实平时刷题不多, 位运算用得也少, 见笑见笑
    dode
        14
    dode  
       49 天前
    线性代数里有矩阵,数据结构,稀疏矩阵怎么存储


    线段树是一种二叉搜索树,与区间树相似,它将一个区间划分成一些单元区间,每个单元区间对应线段树中的一个叶结点。
    使用线段树可以快速的查找某一个节点在若干条线段中出现的次数,时间复杂度为 O(logN)。而未优化的空间复杂度为 2N ,实际应用时一般还要开 4N 的数组以免越界,因此有时需要离散化让空间压缩。
    dode
        15
    dode  
       49 天前
    数很大的话,求和不会溢出吗
    rainbowismagic
        16
    rainbowismagic  
       49 天前
    大学时候学过荷兰三色国旗那个算法,感觉这一类都是类似的。边遍历边调整位置。
    me1onsoda
        17
    me1onsoda  
       49 天前
    抬个杠,既然说 n 很大,那么加起来有没有可能溢出呢
    dlzht
        18
    dlzht  
    OP
       49 天前
    @me1onsoda @dode 是可能会有溢出问题
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   实用小工具   ·   2612 人在线   最高记录 6679   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 25ms · UTC 06:10 · PVG 14:10 · LAX 23:10 · JFK 02:10
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.