V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
The Go Programming Language
http://golang.org/
Go Playground
Go Projects
Revel Web Framework
Goat121
V2EX  ›  Go 编程语言

两个面试题求助,有关 slice 和字符串的

  •  
  •   Goat121 · 2022-02-22 23:55:35 +08:00 · 2378 次点击
    这是一个创建于 1003 天前的主题,其中的信息可能已经有所发展或是发生改变。
    今天被问到两个面试题
    1.一个 slice 有 10000 个元素,要删除前面 9999 个,求最佳方案
    我答的是取第 10000 个元素的值,新建一个 slice 赋值,之前的 slice 没有引用会被 gc 回收
    面试官说这个方案是最差的,因为这样做之前的 slice 依然被引用不会回收,反而增加大量引用效率变差。
    这里没理解是为什么,有大佬能讲解一下吗?

    2.两个千万级长度的字符串,要比较其中的重复文本出现频率,即相似度,给出解决方案
    这题只能想到暴力遍历,没答上来,求大佬给个解决方案
    12 条回复    2022-03-04 21:37:46 +08:00
    cmdOptionKana
        1
    cmdOptionKana  
       2022-02-23 00:01:44 +08:00
    makdon
        2
    makdon  
       2022-02-23 00:04:57 +08:00
    1. 同不懂,我也觉得应该会被回收
    2. 如果只是相似度的话,可以做相似度哈希,例如 simdhash
    BeautifulSoap
        3
    BeautifulSoap  
       2022-02-23 00:43:20 +08:00   ❤️ 1
    想了下发现第一个问题如果 lz 没有记错了的话,那就是面试官自己有问题

    他想测的是 slice 取区间会导致底层的 array 依旧被引用无法释放引发内存泄漏的知识点。比如 s[90:100] 这样取 slice 的区间的话,新生成的 slice 实际上指向的还是原切片 s 的底层数组,所以会引发内存泄漏

    但这面试官自己提的问题就有问题,10000 个元素只保留最后一个元素,谁会傻兮兮得用 s[9999:10000] 这种写法,直接 s[9999] 取值赋给新 slice 就行了(也就是 lz 说的这方法),这种方法不会造成内存泄漏,是面试官自己思维定势了。当然面试官可能想说的只是你没提 “需要将原 slice=nil 置 nil” 也有可能
    heimeil
        4
    heimeil  
       2022-02-23 02:35:12 +08:00
    newLen := len(arr[9999:])
    copy(arr[0:newLen], arr[9999:])
    arr = arr[0:newLen]

    可能是要重复利用底层的数组吧,避免后续频繁申请和释放底层数组的内存
    https://go.dev/play/p/ETH4u-QfgtN
    tousfun
        5
    tousfun  
       2022-02-23 08:18:46 +08:00 via iPhone
    第二题是寻找最长子序列吗
    lllllIIIlll
        6
    lllllIIIlll  
       2022-02-23 11:36:44 +08:00
    @BeautifulSoap 请教个问题,如果不将原 slice=nil ,gc 不会正常回收这部分内存吗?不是已经没有到原 slice 的引用了吗?
    radioactive
        7
    radioactive  
       2022-02-23 11:39:45 +08:00
    BeautifulSoap
        8
    BeautifulSoap  
       2022-02-23 12:21:07 +08:00 via Android
    @lllllIIIlll 引用原 slice 的变量不置 nil ,不还是被原变量引用着吗,就算你没用到
    Goat121
        9
    Goat121  
    OP
       2022-02-23 16:35:40 +08:00
    @BeautifulSoap 谢谢 应该就是当时表达的问题,我就是觉得我对这个的理解应该没错啊
    Goat121
        10
    Goat121  
    OP
       2022-02-23 16:37:17 +08:00
    @makdon @radioactive 谢谢 我去看看这个
    monetto
        11
    monetto  
       2022-02-23 20:22:23 +08:00
    @radioactive 现在面试都已经这么卷了吗....真不敢想象
    mengzhuo
        12
    mengzhuo  
       2022-03-04 21:37:46 +08:00
    1. 应该是```s[0] = s[9999]; s = s[1:]``` 吧
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   实用小工具   ·   1052 人在线   最高记录 6679   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 23ms · UTC 19:15 · PVG 03:15 · LAX 11:15 · JFK 14:15
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.