微软7.4新鲜五轮面筋

刚刚才面完五轮面试连环面的最后一面。微软面试水平还是很高的。最后一面是码农的总管，我本以为会出什么难题。结果出了一道看似很简单的题，但做了才发现，真的是直戳我的痛点（edge/corner case）。总体感觉学到了很多，高频题一道没考到，面筋里面的题也没撞到。总体来说，我觉得还是踏踏实实的把自己的缺点一个个的攻克。

Tech Screen：n个人，求有多少个两两组合之间的距离小于k的数量。要求O n^2

1. find Kth in 2 sorted array.

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

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

两个可行点，最后O(1) 查找第三个点是不是在里面。

补充内容 (2019-7-6 14:59):
tech screen主要用n^2找出合法的两两距离。然后再用hashtable记录每个点的对应可行点，再用n^2找出每两个可行点，最后O(1) 查找第三个点是不是在里面。

skybreaker 发表于 2019-7-5 04:51
第四题binary search？因为递增的差距是一样的且是sort好的，所以可以通过index来判断现在这个数是不是对的 ...

对的，其他同学参考这位同学思路

maxstack, 好麻烦的一道题

都是好同志 发表于 2019-7-5 14:58
对的，其他同学参考这位同学思路

如果是binary search，假如选择的是mid的是正确的值，可你并不知道到底是该忘右走还是左边走吧，还是要都扫一遍。

先加2分。
第4面没太明白，递增数列如何用lg(n)来判断？想来想去只有O(n)。

lilianleo 发表于 2019-7-4 10:51
先加2分。
第4面没太明白，递增数列如何用lg(n)来判断？想来想去只有O(n)。

我跟你想法一样，想来想去都是O（n），等看看楼主怎么说。我太菜了。

谢谢面经。第四题的这个递增数列是要满足相邻元素之间单调递增一么？

软家的这些老司机估计也没有接触多少新题目，倒是一些基础的东西搞得滚瓜烂熟而且还加点自己的想法在里面。

第四题是固定递增一个数K

zorrowei 发表于 2019-7-4 11:39
谢谢面经。第四题的这个递增数列是要满足相邻元素之间单调递增一么？

递增k，差距都是一样的

最后一题是不是描述有问题，递增数列里面有一个数不是递增的吧，要不然如果是一个递减数列，输出都是o（n）

Tech Screen 的题好像见过，是利口的题吗？