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

笔试加两轮面试总结

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

    看了这么多面经,也应该来回馈社会了。面的某大厂 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   69 天前 via Android
    机考,是华为?
    Jacky23333
        2
    Jacky23333   69 天前 via Android
    想知道 1 亿个手机号码那道题的怎么做
    kaoshuiwan
        3
    kaoshuiwan   69 天前
    @Jacky23333 用前缀树应该可以吧 TrieTree, 大概 O(11n + 10^11)的复杂度?
    111qqz
        4
    111qqz   69 天前 via Android
    搜索算法是指什么?
    kaoshuiwan
        5
    kaoshuiwan   69 天前
    还得加个排序的耗时 /捂脸, 空间复杂度也有点大
    bbao
        6
    bbao   69 天前
    @Jacky23333

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


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


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

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

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

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

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

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

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

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

    你这不是纯抬扛么同学.
    diveIntoWork
        25
    diveIntoWork   67 天前
    一亿手机号,一行 shell 搞定
    cat $inputfile | tr -s ' ' '\n' | sort -f | uniq -c | sort -r | head -n 10 | awk '{print $2, $1}'
    关于   ·   FAQ   ·   API   ·   我们的愿景   ·   广告投放   ·   感谢   ·   实用小工具   ·   897 人在线   最高记录 5168   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 27ms · UTC 17:45 · PVG 01:45 · LAX 10:45 · JFK 13:45
    ♥ Do have faith in what you're doing.