查看: 3647|回复: 26
收起左侧

🐶家VO过经

|只看干货
匿名用户-498  发表于 2022-5-20 14:13:54 |阅读模式
本楼: 👍   100% (5)
 
 
0% (0)   👎

2022(4-6月) 码农类General 硕士 全职@Google - 猎头 - Onsite  | 🙁 Negative 😣 HardPass | 在职跳槽

注册一亩三分地论坛,查看更多干货!

您需要 登录 才可以下载或查看附件。没有帐号?注册账号

x
面的L4,除了第四轮,LZ自问都答得无懈可击(尤其第五轮,followup做完我觉得起码能拿strong hire),第4轮LZ觉得是个lnh或者nh,但recruiter都说feedback very positive,所以我觉得可能三姐还是放过我了,然而送HC竟然被down level了,连recruiter都说不可思议,还好最后靠team match的大腿给掰回来了

第一轮,BQ,感觉是中东人
  • fav project,
  • 如何与工作风格不同的人共事(翻译:其实就是问如果同事wfh或者不同时区,你怎么办,我围绕促进communication efficiency来答,感觉这题必问),
  • 有没有与disagree with manager的情况,
  • how to work with difficult colleague,
  • tight deadline


第二轮,国人小哥,
  • 第一题,尓契吧强化版,找出所有bad commit。我在地里看过这题,但是一直没看到有人说明白题意,所以这里详细说下。简单来说,input是两个integer,low和high,代表的是一开始的commit和最后的commit。你还有一个API isWorse(a, b) 可以比较两个commit a和b是不是恶化了。简单来说,就是给你一个数值单调递减的array(e.g. 999887776555322211),然后找出所有比前一个数字小的下标,只是这个下标不是0开始,而是low,然后最后是high,中间的下标数字连续。用binary search即可,如果binary search里右边没有比左边差,那么这个区间必定没有worse commit,直接返回,否则取中点,看中点是不是worse commit, 是的话加到answer里,再两边binary search
  • 第二题散雾幺



第三轮,国人小姐姐
  • 幺耳酒散,套了个炸弹的壳,一开始是1个的情况,然后扩展到多个炸弹。BFS秒
  • followup是炸弹无限制,问到达终点最少要多少个。用dijkstra解,用一个2darray 存每个点的optimal k,初始化为inf,然后起点的k为0。然后queue = [(0, start)],每次heappop queue的一个点的时
    您好!
    本帖隐藏的内容需要积分高于 188 才可浏览
    您当前积分为 0。
    使用VIP即刻解锁阅读权限或查看其他获取积分的方式
    游客,您好!
    本帖隐藏的内容需要积分高于 188 才可浏览
    您当前积分为 0。
    VIP即刻解锁阅读权限查看其他获取积分的方式
    ollowup是宝藏被上锁了,有小写,小写是钥匙,大小写是对应的,譬如钥匙a可以解锁宝藏A。还是求到达终点的最短路径,还是要求收集所有的宝藏,但是要收集宝藏意味着先找到钥匙
  • 这两题的思路都很像,就是基本的bfs套路,记录的状态除了访问过的格子,还有已经收集过的宝藏/钥匙,我是用bitmask做的,因为宝藏/钥匙 at most 26个,刚好可以用一个int来代表所有状态(估计这就是出题者的目的),而且宝藏的字母不是连续的,也就是说可能会有A,C但没有B的情况,bitmask刚好可以handle这种情况。碰到宝藏时要看有没有对应的钥匙,然后到终点时要判断是不是收集到所有的宝藏。

评分

参与人数 5大米 +14 收起 理由
fred9582 + 1 很有用的信息!
iampolo + 1 给你点个赞!
清道神君 + 10
zzhong1 + 1 赞一个
plain1994 + 1 给你点个赞!

查看全部评分


上一篇:开花堡 店面
下一篇:暑期实习压哨Snap Inc SWE
本楼: 👍   100% (2)
 
 
0% (0)   👎
全局: 👍   100% (9)
 
 
0% (0)    👎
回复

使用道具 举报

本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   97% (72)
 
 
2% (2)    👎
Random permutation感觉可以用tree preorder iterator的思路,相当于iterate一遍所有permutation。时间是amortized O(m)空间是O(mlogn), m是array的长度,n是getRandom被call的次数。

class RandomPermutation:

    def __init__(self, arr):
        self.stack = [(arr, 0)]

    def getRandom(self):
        while self.stack:
            arr, i = self.stack.pop()
            if i == len(arr):
                return arr
            nextIndexes = list(range(i, len(arr)))
            random.shuffle(nextIndexes)
            for j in nextIndexes:
                arr[i],arr[j] = arr[j],arr[i]
                self.stack.append((arr[:], i+1))
                arr[i],arr[j] = arr[j],arr[i]
        return -1
回复

使用道具 举报

本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   94% (1235)
 
 
5% (75)    👎
random permutation的时间要求是什么?另外是要求每一次都random吗? 这个要确保用过了不能再用,真的挺难的。
如果空间上要求不许记录已经用过的permutation,那么就要确保random的算法能恰好randomly的遍历每一个permutation。。
上网搜了一下,shuffle出一个random的permutation,是有个有名字的算法的。唯一能想到的是,先generate出来这一个permutation,然后再next permutation。
每一次都random,还不重复,感觉有点找茬的意思。
回复

使用道具 举报

本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   100% (9)
 
 
0% (0)    👎
每轮都是45min的面试吗?
回复

使用道具 举报

本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   100% (9)
 
 
0% (0)    👎
请问一下楼主第二轮badcommit,(e.g. 999887776555322211)这里的binary search是不是先以9为target找到一个bad commit 8,然后再以8为target找到第二个commit 7。最后时间复杂度相当于是O(klogN), k是bad commit的数量。
回复

使用道具 举报

地里的匿名用户
匿名用户-22E  发表于 2022-5-20 20:24:11
本楼: 👍   0% (0)
 
 
0% (0)   👎
三姐那个第一题如果不可以用O(n), 那就生成随机index,index的range从0到n, n--。每次把这个index的对应的数移动到末尾。最后再加上正负标售。
根据现有描述我现在只能想到这个思路。也不知道对不对
回复

使用道具 举报

本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   66% (2)
 
 
33% (1)    👎
问一下“靠team match的大腿掰回来了” 意思是最后没有被downlevel嘛? 这是怎么做到的呀。。我的recruiter说HC的决定是没办法改的
回复

使用道具 举报

地里的匿名用户
匿名用户-498  发表于 2022-5-21 00:33:18
本楼: 👍   0% (0)
 
 
0% (0)   👎
plain1994 发表于 2022-5-19 23:35
每轮都是45min的面试吗?

是的
回复

使用道具 举报

地里的匿名用户
匿名用户-498  发表于 2022-5-21 00:38:35
本楼: 👍   0% (0)
 
 
0% (0)   👎
plain1994 发表于 2022-5-20 00:07
请问一下楼主第二轮badcommit,(e.g. 999887776555322211)这里的binary search是不是先以9为target找到一 ...

这些数字只是一个虚拟的数字,只是为了表示这是一个递减的数组,函数的input是两个数字low和high,相当于这堆commits的最小和最大的id(连续的)
999887776555322211,那么我应该返回第一个8,7,6,5,3,2,1的index,分别是3,5,8,9……(假设我low是从0开始算)
回复

使用道具 举报

本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   97% (252)
 
 
2% (6)    👎
pususu2001 发表于 2022-5-20 06:23
Random permutation感觉可以用tree preorder iterator的思路,相当于iterate一遍所有permutation。时间是am ...

这不还是On空间吗,要求是不能用On空间
回复

使用道具 举报

地里的匿名用户
匿名用户-D62  发表于 2022-5-21 00:47:14
本楼: 👍   0% (0)
 
 
0% (0)   👎
LZ几年经验啊?如果比较少可能被downlevel吧
回复

使用道具 举报

您需要登录后才可以回帖 登录 | 注册账号
隐私提醒:
  • ☑ 禁止发布广告,拉群,贴个人联系方式:找人请去🔗同学同事飞友,拉群请去🔗拉群结伴,广告请去🔗跳蚤市场,和 🔗租房广告|找室友
  • ☑ 论坛内容在发帖 30 分钟内可以编辑,过后则不能删帖。为防止被骚扰甚至人肉,不要公开留微信等联系方式,如有需求请以论坛私信方式发送。
  • ☑ 干货版块可免费使用 🔗超级匿名:面经(美国面经、中国面经、数科面经、PM面经),抖包袱(美国、中国)和录取汇报、定位选校版
  • ☑ 查阅全站 🔗各种匿名方法

本版积分规则

>
快速回复 返回顶部 返回列表