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

笔试加两轮面试总结

  •  
  •   xzpjerry731 · 2020-03-29 12:26:02 +08:00 · 5560 次点击
    这是一个创建于 1461 天前的主题,其中的信息可能已经有所发展或是发生改变。

    看了这么多面经,也应该来回馈社会了。面的某大厂 py

    刚刚结束二面,不知道凉了没有。有个插曲,昨夜八九点发二面的通知让在昨晚 11 点前预约面试时间,我早早睡去没看到,早上打电话临时补约了下,估计给二面面试官不好的映像了,全程冷冷的 T_T

    第 0 轮机考

    • 转圈圈叫号,号码不符合条件的出列,看谁最后留下
    • n 个一样的桶叠在一起,给你桶的容积,每个桶的初始水量和从最上面倒入的水,算到最下面那桶会溢出多少。
    • 给你一个二叉树,左右交替打印每一层的节点值,第一层从左到右,第二层从右到左。。。。。。

    第 1 轮电面

    • 简历项目细节
    • csrf 相关
    • cookie 相关
    • 链表和数组相关
    • 哈希表相关
    • 问我掌握的数据结构和算法
    • 字符串匹配相关
    • 每种树的应用场景

    第 2 轮视频面

    • 我最有成就的项目和细节(问的很深)
    • xss
    • 问我掌握的排序算法
    • 快排原理
    • 问我掌握的搜索算法
    • bash 文本操作命令
    • linux IPC
    • 缓冲区溢出攻击
    • 给我一个包含一亿条手机号的文件,让我找出出现次数前十的号码

    一面面试官对我评价是基础扎实,二面面试官表示还需要加深(感觉凉了)

    25 条回复    2020-03-31 16:52:38 +08:00
    pwrliang
        1
    pwrliang  
       2020-03-29 12:29:36 +08:00 via Android
    机考,是华为?
    Jacky23333
        2
    Jacky23333  
       2020-03-29 12:48:08 +08:00 via Android
    想知道 1 亿个手机号码那道题的怎么做
    kaoshuiwan
        3
    kaoshuiwan  
       2020-03-29 12:56:52 +08:00
    @Jacky23333 用前缀树应该可以吧 TrieTree, 大概 O(11n + 10^11)的复杂度?
    111qqz
        4
    111qqz  
       2020-03-29 13:01:45 +08:00 via Android
    搜索算法是指什么?
    kaoshuiwan
        5
    kaoshuiwan  
       2020-03-29 13:01:59 +08:00
    还得加个排序的耗时 /捂脸, 空间复杂度也有点大
    bbao
        6
    bbao  
       2020-03-29 13:03:37 +08:00
    @Jacky23333

    1 亿个手机号,需要用到归并排序;
    分 100 ( N)个文件,每个文件平均分配手机号;每个文件里面取前 10 名;
    然后根据最终结果合并,再排序后前 10 名就是最终结果了;
    xzpjerry731
        7
    xzpjerry731  
    OP
       2020-03-29 13:19:48 +08:00
    @pwrliang #1 不是,现在大厂都搞机考吧。


    @Jacky23333 #2 我一开始用优先队列做,是能做的,但是做完后他让我不要用别的模块,然后我就不会了。


    @kaoshuiwan #3 我感觉这里用字典树好像没啥用吧,找出现次数第一可能可以,前十个我感觉不太行。

    @111qqz #4 我反正就按数据类型分类回答,如果是二叉树怎么怎么地,数组的话怎么怎么地,字符串的话怎么怎么地

    @bbao #6 感觉上可以嘢,我也有往这个方向想,但是没有想到每个文件取前十最后再汇总,学到了学到了
    kizunai
        8
    kizunai  
       2020-03-29 13:30:40 +08:00   ❤️ 1
    睡这么早,一看就是不能加班的
    pwrliang
        9
    pwrliang  
       2020-03-29 13:40:53 +08:00 via Android
    一亿个手机号单机内存放的下,用 map 计数然后用 quick select 找 top 10?
    find
        10
    find  
       2020-03-29 13:49:41 +08:00 via iPhone
    一亿,手机号,每个手机号 11 char,也就一个 G,map 内存可以装 。二叉树,就一个 bfs
    meteor957
        11
    meteor957  
       2020-03-29 14:10:22 +08:00
    csrf 相关
    cookie 相关 有详细问题吗
    hq136234303
        12
    hq136234303  
       2020-03-29 14:35:23 +08:00
    java?
    xzpjerry731
        13
    xzpjerry731  
    OP
       2020-03-29 14:45:12 +08:00
    @kizunai #8 哈哈哈哈哈,也不是不能,就这几天准备面试从早学到晚有点疲劳

    @pwrliang #9 我也有说到这个,但是后来觉得会很耗时吧

    @find #10 您的意思是把手机号当字符串存二叉树里?然后怎么统计呢?

    @meteor957 一开始是让我讲一讲原理,后来问了一些细节的问题我记不起来了,好像 cookie 问了 http-only

    @hq136234303 #12 第一行写着 py 呀
    mrgeneral
        14
    mrgeneral  
       2020-03-29 15:36:19 +08:00
    看题目感觉是校招题目,但是还有简历项目,这种有社会经历的不都是问项目和从业方向相关的吗?
    xzpjerry731
        15
    xzpjerry731  
    OP
       2020-03-29 16:41:26 +08:00
    @mrgeneral #14 是校招啦
    xupefei
        16
    xupefei  
       2020-03-29 18:30:35 +08:00 via iPhone
    手机号可以用前缀树存,把计数放在叶子结点。最后返回 top k 叶子结点。

    用前缀树的好处是空间小:手机号有 11 位,每位十个数字,空间绝对不超过 10^11,就算输入 100 亿个手机号也一样。
    luomu24
        17
    luomu24  
       2020-03-29 22:24:07 +08:00
    校招项目问得这么细吗,没有项目的哭了。
    Allianzcortex
        18
    Allianzcortex  
       2020-03-30 05:38:11 +08:00
    @Jacky23333 应该是先回答 Trie,再加深多路归并,再多机器延伸到 MapReduce/RDD
    aguesuka
        19
    aguesuka  
       2020-03-30 11:41:08 +08:00 via Android
    一亿也就 100m,算上手机号长度大约是 1 个 g,全保存到 map 里。排序用优先队列,复杂度是 O(nm)n 是手机号数量,m 是前 m 个手机。
    aguesuka
        20
    aguesuka  
       2020-03-30 11:43:23 +08:00 via Android
    @bbao 这个方法是有问题的,每个文件必须取全部才能保证数据的正确性
    bbao
        21
    bbao  
       2020-03-30 13:56:22 +08:00
    @aguesuka 如果其他文件连前 10 都排不上,我要这个数据没用;如果在其他文件排到了前十之后,整体文件汇总求和再重新排序取前十,没有问题;
    aguesuka
        22
    aguesuka  
       2020-03-30 17:10:31 +08:00 via Android
    @bbao 举个例子,只有 10 个手机号出现了 2 次,其它所有都是 1 次,你的算法能把这 10 个手机号都找出来吗?
    rannie
        23
    rannie  
       2020-03-30 17:38:02 +08:00
    10 亿手机号用 bit set 存就行
    bbao
        24
    bbao  
       2020-03-31 09:21:41 +08:00
    @aguesuka 海量数据有海量数据的计算方法; 10 个数据有 10 个数据的计算方法;
    我给你加一个限制; 64M 内存的机器; 1 亿手机号,你看看你的计算方式能算,还是我的计算方式能算;
    手机号再多一些,10 亿手机号,是你的更快一些,还是我的更快。

    你这不是纯抬扛么同学.
    diveIntoWork
        25
    diveIntoWork  
       2020-03-31 16:52:38 +08:00
    一亿手机号,一行 shell 搞定
    cat $inputfile | tr -s ' ' '\n' | sort -f | uniq -c | sort -r | head -n 10 | awk '{print $2, $1}'
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   我们的愿景   ·   实用小工具   ·   5767 人在线   最高记录 6543   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 36ms · UTC 06:10 · PVG 14:10 · LAX 23:10 · JFK 02:10
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.