巨硬6.16HE超详细面经加timeline

Timeline：

四月初，有个recruiter在LinkedIn上联系， 问要不要参加五月的HE。那时候刚打算换工作，没准备，就拒绝了。

四月底， 又一个recruiter在LinkedIn上联系，问要不要面微软6月28的HE。我就说想参加五月的，她说五月都关了。我就问最早的什么时候，她说六月七号。就选了这场。她说现在链接还没放出来，到时候出了再联系我。五月中旬再联系的时候只给了我6.16，6.21和6.28的选项。最后申请了6.16。

5月19号收到oa，周日做了。三个题都是地里小伙伴分享的原题，那几周的oa应该都是那三个题。第二天hr说过了，然后约了45分钟，告诉我怎么准备，并说面试前一周sheduler会联系我。

6月10号周五没收到任何消息，给hr发邮件，周末收到了scheduler的邮件，让我确认availability，面试前一天下午发链接。

6月15号下午收到视频链接。

6月16号四轮VO，四个人都是来自Azure下的一个大组，具体就不说了。


第一轮， 应该是大boss，他说他管50多个人，人也比较nice。先bq了十五分钟，然后做题。题目是给你rand(p, q)，可以随机生成[p, q]之间的整数，让你写一个myrand(m, n)，要求能够生成n个[1, m]之间的整数，每个整数必须不同。我先说每次用rand（1，m）取一个随机数，然后都存在set里，下次如果再摇到重复的，就再摇。他问我时间复杂度是什么，我说空间是O(n)，时间当m和n很接近的时候就很慢。他打开canvas，画了一个坐标轴，横坐标是n，纵坐标是使用rand（1，m）的次数。假设m是固定值10，n从1增大到m，画出曲线。我列了n=1，2，3时候需要的次数，他就说曲线是指数的，问我能不能优化。我说生成一个size为m的数组，第一次使用rand（1，m）来产生数组的下标，取到的数和最后一个数字交换位置，相当于把取到的数字剔除掉。第二次使用rand（1，m - 1）来产生数组的下标，依次类推。他问时间和空间复杂度，我说O（1）和O（m）。他问能不能再优化。想了一下并不需要产生一个size为m的数组，因为每次你都是交换被选中的和最

您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

inter，所以可以用一个TreeMap去maintain子数组，key是数组的值，value是对应的行。每次求diff的时候用first()和last()取最值。然后用removeLast()移除最小值，同时找到是哪一个pointer。再然后把新的pointer指向的值插入。要注意的是key可能有duplicate，你得自己写个comparator，当key相等的时候，例如可以比较row number（随便比较什么可以，只要不相等）。这样的话时间复杂度应该是O（n*klogk），感觉再优化的空间不大了。

补充内容 (2022-06-23 21:54 +8:00):
根据@p2world大佬提示，确实是leetcode原题留散而。面试官把描述中的list of list改成了matrix，range改成了difference，难怪我用这几个关键词没有搜到。看了一下答案，确实是用k个pointer解决的，时间复杂度是O(n*k*logk)

补充内容 (2022-06-24 05:46 +8:00):
上面的包裹审了一天都没通过，重新发了一个

兄弟，我没太理解你说的“第二轮，题目是散巴铃（Insert Delete GetRandom O(1)），多了一个搜索”的搜索指的是啥？查到某个数字在不在里面？那这不就是看在不在hashmap里，这code不就是一行（如果用的是arr+hashmap的方法做的话）。还是说我哪里理解错了lol

60考的算法题就已经这么难了吗？级别越高的是考的难度越大吗，还是BQ和System Design相关的问题更复杂一些？多谢大佬解读，给大佬加米

TerryYu 发表于 2022-6-25 21:48
路散而 是 选最小区间的，和这题好像有些不同吧

高赞的题解里说这个题的一个解法是转化为最小区间，所以应该是一样的

楼主买的什么level？包裹贴看不了

不知道是不是我理解有问题 ，第三题 记录每列的最大值-最小值 然后把所有列的diff加一起 可以嘛

感谢楼主分享，第三题的思路和解法能不能再详细说说？这个思路理解了，具体实现的话怎么去移动最小的pointer指向下一个数？已加米，感谢，顺便恭喜楼主喜提offer，不容易！

匿名者 发表于 2022-6-22 19:47
楼主买的什么level？包裹贴看不了

包裹帖还在审核，我是一年加三个月工作经验，给的60

您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

第一题原题是那个？ 我好像做过的。

小栗子喔 发表于 2022-6-22 21:42
第一题原题是那个？ 我好像做过的。

第一题leetcode好像没有原题，地里的面经有

第三题是路散而