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

第一次发帖,分享两个微软的挂经

  •  1
     
  •   neroleewtf · 147 天前 · 6195 次点击
    这是一个创建于 147 天前的主题,其中的信息可能已经有所发展或是发生改变。
    po 到现在主要是游戏行业后端,现在是 go+redis 这个样子,姑且也算是个 senior 了,到没到 MS 的 senior 的标准还不好说,感觉 system design 这方面还有很多自己不懂的东西。

    其实不太想一直在游戏行业留着,比较想回一个不太加班的科技公司,外加英语好,所以一直比较注意这些机会,但苦于各种原因还一直在游戏行业。

    之前有创业经历,去年创业不太灵的时候 linkedin 收到过微软 HR 的邀请,尝试投递了下然后没有进面试,原因不太清楚。半年后被在微软的同学强烈的意愿下试着让他内推了下,也是给到 HR 之后就没回音了。

    今年微软的又找过来,我提了这个情况,结果这次第一个职位的面试官打电话过来约了面试时间。
    遂开始准备面试。

    第一个职位: https://careers.microsoft.com/us/en/job/1048544

    因为简历主要是游戏后端,所以背景也没啥好说的。简历里写了自己现在项目的游戏(一个回合制卡牌,1202 年还在用自动战斗那种)自己完全负责了战斗系统,而且做到了 x 倍性能优化和 xx%内存占用下降。

    面试的时候这个就多说了下,然后立刻 coding 题。结果第一题就整懵了。

    leet 里微软题库有,但是没复习到。

    input:一个 n*n 矩阵,有一个必然闭合的 1 围成的不规则区域,除了这个区域边缘由 1 组成外,矩阵其他项均为 0 。
    output:把闭合区域内的 0 全部改成 2 输出。

    知道是 DFS 但不太清楚搜索从哪里开始。后来知道是 floodfill 类型的题目(同类题在 leet 里难度算 easy )。在面试官几乎摁着教搜索方向(四方向)和从哪儿开始搜索(矩阵四条边,把外层 0 标记,最后把外层 0 还原,内层 0 置为 2 )之后题目算是答出来了。
    当然当时就知道因为这个不完全算自己的思路,肯定有问题。

    然后挂了。

    当时以为有冷冻期,HR 说可以接着面,提供了一个 M365 的职位。而且追问了我是不是想做全栈,我说是的,确实很想转全栈方向。

    第二个职位: https://careers.microsoft.com/us/en/job/991340

    HR 说 JD 里面要求的语言可以无视,SDE2 也可以无视,看最后能力定职级。遂 ok,约了时间继续面。

    今早 10 点进入面试。差不多介绍战斗系统优化方向到面试 15 分钟左右被打断。

    然后开始追问你们现在游戏服务器每个 node 的日志量,日志怎么收集,服务器状态怎么监控,服务怎么批量部署。我说日志收集处理用 filebeat+kafka,介绍了下基本的部署和监控用的 devops 的工具。
    然后被追问 kafka 单个 broker 能承载的最大日志量。我说这个目前没有做太多研究,这部分就过了。

    然后开始问 SQL 相关,我说我以前有过经验但现在将近两年多没有用过 SQL,主要是 redis 相关。
    问了 sql 语句问题,第一个是(name class score)这样的表,class=A 取 score top5 的学生名字。这个写出来了。
    然后问每个 class 取 score top5 的学生名字。这个在我以前也都比较少用,现在更是不知道,然后这里就过了。

    然后开始问语言的并发,线程怎么创建,我现在主要用 go 就简单介绍了 goroutine 和 channel 的机制,然后被问到 mutex 和 semaphore 的区别,这里也比较好答出来了。

    接下来是一些有关分布式系统部署的问题,ACID 和 CAP 相关概念,CAP 在不同业务需要先满足 CP 还是 AP 。
    然后问了一个问题,一个生成 [严格自增 ID ] 的服务,要在大型分布式系统中做到高可用性如何做。
    我说可以用单个服务器(追问:规模太大时单个服务器不行)
    我说因为实在没做过这方面,游戏后端没有相关业务只能估计一下。当时提到了给每个 node 分配 ID 段的做法,但这不能满足严格自增。
    他要求既严格自增又高 availability,我就不太清楚这里怎么办了。(后来查到其实趋势自增是可以的,包括雪花算法之类的,这些确实不了解。)

    最后 coding 题,此时面试已经是 10 点 38 。
    coding 题是关于 gray code 的,leet 题目: https://leetcode.com/problems/gray-code/ (难度 medium )
    (之前为了这一轮狂刷 leet,这一题我也没刷到。也不要说格雷码的位运算做法之类的,毕竟之前几乎就没听过这个概念)
    和 leet 版不同的是要按二进制输出,(包括高位的 0 )

    观察和试结果了一阵(包括猜测了队列改位之类的,发现不对)大约五六分钟之后我发现了一个规律:

    设 grayCode(n)的输出是一个 string array (或者说 go 的 slice,这里视为可变长度 array )
    那么
    grayCode(n, prefix = "") = grayCode(n-1, prefix + "0").append(reverseGrayCode(n-1, prefix + "1"))
    (不是 go 的语法不要在意)
    为了节省时间请求从网上 copy 一个 go 的 reverse slice 的方法,同意了
    然后基本开始做了

    最后面试进行到 10 点 50,快要 debug 的时候(还是有一些语法错误)面试官:“我也不太了解 go,可以不 debug 了,你给我讲一下你这个的思路”

    然后我讲了一下这个递归执行的流程,他一开始没太看清楚 prefix 我后面加了"0"或者"1",以为我 n=0 时直接返回 prefix 返回的是空。我再带他看代码的时候他才确认我这个做法没有问题。问我时间复杂度我说 O(2^n)。

    10 点 58 左右面试结束。因为早上面试没有请假,客套了几句没有问面试官问题(说接下来有面试机会再问)就结束面试回去上班了。

    下午 6 点 20 左右被 HR 通知挂掉了,原因是 coding 没通过。
    61 条回复    2021-07-16 09:51:57 +08:00
    zlzdbf
        1
    zlzdbf  
       147 天前
    看楼主的描述,是全英文面试吗?
    neroleewtf
        2
    neroleewtf  
    OP
       147 天前
    @zlzdbf 两次都是中文面试
    yifangtongxing28
        3
    yifangtongxing28  
       147 天前   ❤️ 3
    每个大公司的要求都水涨船高,95 后接盘了所有
    maketime4life
        4
    maketime4life  
       147 天前
    楼主刷题量有多少?
    neroleewtf
        5
    neroleewtf  
    OP
       147 天前
    @maketime4life 四百多了,不过因为相当一段时间没看机会,最近一些在重新捡(刷得还挺快,也都能自己写出来),微软题库也启动得比较慢(所以一面出了问题)。第二次的时候微软题库基本刷完
    maketime4life
        6
    maketime4life  
       147 天前
    @neroleewtf #5 这刷题量可以啊,都是顺序刷的吗?
    neroleewtf
        7
    neroleewtf  
    OP
       147 天前
    @maketime4life 并没有,会大致归类,一类题目会归类刷同类型题
    maketime4life
        8
    maketime4life  
       147 天前
    @neroleewtf #7 这样还碰到了没刷过的,只能说运气不好了。。。😂
    casparchen
        9
    casparchen  
       147 天前 via iPhone
    老实讲第一个题没做出来实在不应该,是面试的时候紧张了吗?
    fl2d
        10
    fl2d  
       147 天前
    对不起,我看成了 「分享挂两个微信的经验 」🥲
    Mirage09
        11
    Mirage09  
       147 天前
    出 grey code 挺无聊的…
    albertni
        12
    albertni  
       147 天前 via Android
    你这个 gray code 确实有问题吧,要么 g ( 0 )返回空,要么 g ( 1 )返回[ 00,01 ],都不能严格算正确。除非你 hard code 了 g ( 0 )和 g ( 1 )两个终止条件
    albertni
        13
    albertni  
       147 天前 via Android
    @albertni 啊,又看了一下题,g ( 0 )并没有良好定义,那没事了
    ihainan
        14
    ihainan  
       147 天前
    微软题库有 1300+ 题,楼主这刷得有点猛啊……

    其实格雷码在首页精选题库的腾讯精选 50 里面,不过还是很难保证面试肯定会遇到相同的题。
    neroleewtf
        15
    neroleewtf  
    OP
       147 天前 via Android
    @casparchen 因为之前的经历没有走到面试轮,所以确定面试了才开始刷,面到的时候还没刷到
    neroleewtf
        16
    neroleewtf  
    OP
       147 天前 via Android
    @ihainan 倒是没这么多,leet 的刷完了。要刷 1300+那不可能
    neroleewtf
        17
    neroleewtf  
    OP
       147 天前 via Android
    @ihainan 论坛也在 leet 刷完之后刷了些,但没算刷了多少道
    Cbdy
        18
    Cbdy  
       147 天前 via Android   ❤️ 2
    确实,面试运气很重要,

    不过微软你进去的话也可能碰到那种阿里字节等出来脑子不太拎得清的奋斗逼当老板,建议要和实际的工作团队的老板、同事聊聊,身边有这样的例子,试用期没过又跑路了
    ccde8259
        19
    ccde8259  
       147 天前 via iPhone
    第一题被面试官带进沟里了……心疼
    sadfQED2
        20
    sadfQED2  
       147 天前 via Android
    我和你一样,我也一轮挂。大概 10 分钟问项目,然后就 coding,直接来了道 hard 级别的题目,我第一遍写了个时间 nLogn 的算法,结果面试官不满意,我又写了个时间 n 的算法,结果面试官又说空间不满意,然后我就凉了
    tedd
        21
    tedd  
       147 天前 via iPhone
    看了,然后又看了下大家的回复,看来我这辈子是没戏了。因为第一题连题都看不懂 😂
    wxd92
        22
    wxd92  
       147 天前 via iPhone
    楼主工作几年?
    neroleewtf
        23
    neroleewtf  
    OP
       147 天前   ❤️ 1
    @wxd92 算毕业到现在 6 年吧,中间有两年算是不务正业创业去了
    johnsona
        24
    johnsona  
       147 天前 via iPhone
    @yifangtongxing28 据说早年微软招阿三更离谱 啥都不会的招进去了
    johnsona
        25
    johnsona  
       147 天前 via iPhone
    @sadfQED2 真卷
    ufan0
        26
    ufan0  
       147 天前
    @sadfQED2 #20 有原题吗?想去看看这道 hard 级别是否还有 n 以内的做法。
    bk201
        27
    bk201  
       147 天前
    这算是一面都过不了么,后面岂不是更难
    johnsona
        28
    johnsona  
       147 天前 via iPhone
    第一题 按行遍历 每一行第一次越过黑点就改 2 第二次就不改了 至少做得出来
    Anshi
        29
    Anshi  
       147 天前
    刷了 400 多都没过!!!!
    verzhshq
        30
    verzhshq  
       147 天前
    感谢 加油
    JoStar
        31
    JoStar  
       146 天前
    感谢楼主分享,学习了(虽然我这辈子是与微软无缘了
    albertni
        32
    albertni  
       146 天前 via Android
    @johnsona 你这碰到边界的顶部就 gg 了,边界两侧都是外部,下一行才出现内部格
    blindie
        33
    blindie  
       146 天前 via Android
    @johnsona 你这个算法对于一个没有凹的区域可以 但是涉及有凹的就会有问题。即使改成奇偶数也不能解。第二次越过黑点不能知道是到了外面还是里面。
    Cyron
        34
    Cyron  
       146 天前
    感谢分享经验
    lxy42
        35
    lxy42  
       146 天前
    第一个算法题我觉得可以用 Union Find 来做, 1 组成的矩形是一个集合, 外层的 0 是一个集合, 内层的 0 是一个集合.
    pandachow
        36
    pandachow  
       146 天前
    社招六年给到 Senior 的概率很小

    第二个是隔壁组的 (甚至已经猜到面试官是谁 XD), 这题没秒有点可惜了, 不过有点意外竟然是中文面试...- -
    neroleewtf
        37
    neroleewtf  
    OP
       146 天前
    @lxy42 并不是矩形,封闭不规则区域。
    neroleewtf
        38
    neroleewtf  
    OP
       146 天前
    第一题大概必然是 floodfill 的一个变种,我一开始主要没确定到起始从哪里来搜索。
    hahaayaoyaoyao
        40
    hahaayaoyaoyao  
       146 天前
    横向遍历
    判断列的奇偶数
    记录行的奇偶数(用以下一行的检查,第一次肯定是边界, 用类似 HashMap 的数据结构记录,get(i).get(j).put(true)))

    检查该行下一列状态, 如果是 1 就是边界
    如果列是奇数可能在里边
    如果上一行也是奇数则必定在里边. 否则一定在外边
    Rwing
        41
    Rwing  
       146 天前
    挺好的,运气没到而已,可以再接着面
    albertni
        42
    albertni  
       146 天前 via Android
    @neroleewtf 这题有个取巧的办法,在范围外再加一圈外部格,这样所有外部格必然全联通,之后从左上角开始填色就行了
    exploreexe
        43
    exploreexe  
       146 天前
    看来我这辈子是无缘微软了。。。
    dablwow
        44
    dablwow  
       146 天前
    有人知道第一题的 leet 编号吗
    neroleewtf
        45
    neroleewtf  
    OP
       146 天前 via Android
    @dablwow 其实我说错了。leet 无原题。但 leet 微软题库里 searching 类别里有一道 floodfill 。当时我还没刷到这道题
    neroleewtf
        46
    neroleewtf  
    OP
       146 天前 via Android
    @dablwow 另外 leet 直接搜 floodfill 可以看到一些类似的题和类似思路,相关题目有一两题可以用我面试时面试官给的思路求解
    p1gd0g
        47
    p1gd0g  
       146 天前
    借楼问下,lz 你们直接用 redis 落地吗?内存占用不会很大?
    neroleewtf
        48
    neroleewtf  
    OP
       146 天前 via Android
    @p1gd0g github 搜一下 redislv ( git 里版本很老。)
    neroleewtf
        49
    neroleewtf  
    OP
       146 天前
    @p1gd0g 另外类似思路还有很多别的方案,谷歌一下 redis rockDB 或者 redis TiDB 都有。
    Gea
        50
    Gea  
       146 天前
    怎么和我面的 sde2 水品差这么大,尽管我最后也挂了,但是前几面的题真没这么难。。
    johnsona
        51
    johnsona  
       146 天前 via iPhone
    @blindie 菜哭 摸摸楼主
    lxy42
        52
    lxy42  
       146 天前
    @neroleewtf 笔误. 不是矩形也可以用 Union Find.
    lzuntalented
        53
    lzuntalented  
       146 天前
    第一题是不是可以理解成判断点是否在区域内,
    直接全遍历,每个点都向右辐射到边,遇到奇数个为 1 的点说明在区域内就置为 2
    dongfangshangren
        54
    dongfangshangren  
       146 天前
    @albertni 第一题这个方法是 ok 的,其实不用加外部格,从上下左右 4 条边开始,dfs 搜索染色不规则区域以外的地方(碰到 1 就剪枝),未染色的就是闭合区域了。 其实就是 floodfill 的变种,转换一下思路就可以
    albertni
        55
    albertni  
       146 天前 via Android
    @dongfangshangren 写起来不如单起始点的 floodfill 简单易懂,所以说是小技巧
    neroleewtf
        56
    neroleewtf  
    OP
       146 天前
    @dongfangshangren 这个也是面试官建议的思路。

    其实当时对这个思路有一定怀疑是因为,之前 leet 刷的绝大多数题都不需要这样“返工”,外加自己平时做业务的时候被强力灌输了“不要多次 for,循环尽量放一起”的思路(尽管这个思路来做,他的时间复杂度仍然是不会变的。)

    再加上对搜索起始点的不确定(我也会在想是不是从某一点或者某条边起始才对),渐渐时间就过去了解不出来。

    一面准备匆忙+没刷到 floodfill+一些自己固化的想法综合起来的因素。
    zhzy0077
        57
    zhzy0077  
       146 天前
    楼主说英语比较好的话,愿意来我们组试试吗。我们组对英语有点要求所以一直难招人,换句话说可能面试会容易点 不过在上海,可以微信:MTU4NTA1MTU5MTM=
    vemier
        58
    vemier  
       146 天前
    啊太卷了
    tonytonychopper
        59
    tonytonychopper  
       146 天前 via iPhone
    看了下来,感觉楼主还是得多总结总结,题量不能决定所有
    aviator
        60
    aviator  
       146 天前
    我目前的状态:菜到安详.jpg
    p1gd0g
        61
    p1gd0g  
       146 天前
    @neroleewtf 感谢。之前项目用的 pika,毛病有点多。
    关于   ·   帮助文档   ·   API   ·   FAQ   ·   我们的愿景   ·   广告投放   ·   感谢   ·   实用小工具   ·   3972 人在线   最高记录 5497   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 29ms · UTC 01:57 · PVG 09:57 · LAX 17:57 · JFK 20:57
    ♥ Do have faith in what you're doing.