V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
1069401249
V2EX  ›  职场话题

面试官问了一题剑指 offer 的题目,而我刚好前一天看过

  •  
  •   1069401249 · 2020-03-12 16:37:49 +08:00 · 4060 次点击
    这是一个创建于 1702 天前的主题,其中的信息可能已经有所发展或是发生改变。

    1 问:如何确定单向链表有环

    答:快慢指针

    2 问:找出环入口

    答:用 hash 保存在循环列表,第一个重复的 hash 值就是入口。

    其实我记得书上写的是先计算出环的大小,再用两个偏移指针,我害怕这样回答太标准答案了,让人怀疑。

    ——

    所以,面试中遇到这种标准范文问题该如何回答呢?

    17 条回复    2020-03-13 16:01:54 +08:00
    optional
        1
    optional  
       2020-03-12 16:43:38 +08:00
    面试官又不排斥刷过题。。。刷题本身就是学习啊。
    当然如果只会用嘴描述,不能把思路转化成代码是另外一回事。
    Jacky23333
        2
    Jacky23333  
       2020-03-12 16:43:50 +08:00 via Android
    只要自己是真的理解这道题而不是纯粹背答案,这怕什么
    bbao
        3
    bbao  
       2020-03-12 16:44:17 +08:00
    你不怕你说的答案面试官不会或者没转明白么?该给标准答案就给。
    hebin
        4
    hebin  
       2020-03-12 16:44:38 +08:00   ❤️ 3
    "就这?“,反手就把话语权交给面试官 😄
    wyg1997
        5
    wyg1997  
       2020-03-12 16:47:04 +08:00
    有点巧,我昨天刚做这题。。。不过第 2 个还有空间复杂度 O(1)的做法。
    tonytonychopper
        6
    tonytonychopper  
       2020-03-12 16:47:52 +08:00
    不然你就梭哈,讲出所有解法,不然你就装傻,假装思考然后再回答。
    biantaoGG
        7
    biantaoGG  
       2020-03-12 17:18:09 +08:00
    @hebin 皮还是你皮
    also24
        8
    also24  
       2020-03-12 17:23:24 +08:00 via Android
    想起来一件事儿,小时候有次转学,新学校教导主任丢给我一张数学卷子让我做。

    诚实的我:老师这张卷子我做过。

    教导主任换了一张给我。
    诚实的我:老师这张卷子我也做过。

    教导主任换了第三张卷子给我:你就做这张吧。
    诚实的我:老师这张我恰好没做过。
    qpily
        9
    qpily  
       2020-03-12 18:37:34 +08:00
    环出口不用那么麻烦,快慢指针相交之后,把其中一个指针移到入口,俩指针全都继续 1 步 1 步走,下个相交点就是环入口
    across
        10
    across  
       2020-03-12 18:44:13 +08:00
    当然是答最优解。

    面试官:
    我早知道第一层会被你破解
    现在我们进入第二层
    空间 o(1)查入口有想法吗?
    这你也会?
    好,第三层,为什么这个方法刚好能定位到入口,如何推导的?
    答出来了? 抱歉,我在第五层,所以我又想到了一个问题,
    这个带环的链表怎么复制最高效?
    qpily
        11
    qpily  
       2020-03-12 18:44:52 +08:00
    相交时
    慢指针 x 步 快指针 2x 步
    环头 a 步 环长 b 步
    相交说明快指针比慢指针快整整 n 圈,即 2x - x = nb,x = nb
    也就是慢指针一共走了 nb 步,由于环头 a 步,所以实际上慢指针离入环口就差 a 步,补足 a 步就找到入环口了
    Jimmy2Angel
        12
    Jimmy2Angel  
       2020-03-12 18:46:58 +08:00 via Android
    @hebin 反手给你两道 hard 变型
    scukmh
        13
    scukmh  
       2020-03-12 20:34:36 +08:00
    @also24 其实你前两张没做过对不对。
    musi
        14
    musi  
       2020-03-12 22:12:28 +08:00
    @wyg1997 这头像。。。好巧😂
    8a9a09dw12
        15
    8a9a09dw12  
       2020-03-13 09:23:14 +08:00
    就这?
    p1094358629
        16
    p1094358629  
       2020-03-13 15:30:31 +08:00
    业务部门,平时工作 80%时间在处理业务问题,导致技术积累不深,那么面试的时候又问一些算法类的问题很是头疼,所以有点放弃继续干开发的想法.
    1069401249
        17
    1069401249  
    OP
       2020-03-13 16:01:54 +08:00
    @p1094358629 我也这么想的,但是除了写代码其他的也不会
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   实用小工具   ·   975 人在线   最高记录 6679   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 24ms · UTC 22:26 · PVG 06:26 · LAX 14:26 · JFK 17:26
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.