小**的HRT电面1面~~回馈农友

楼主上星期收到HR的面试邀请，激动不已٩(๑>◡<๑)۶，还特别感谢了HR姐姐的温馨提示：

[size=12.800000190734863px]In order to prepare for your phone screen, we'd like to suggest that you familiarize yourself with some of those topics:

• stochastic calculus and stochastic control. For example, you should be familiar with Ito formula and HJB.
• linear regression.
• KL divergence.
• Bayesian inference.
  

然后我就预习了一星期的随机跟信息熵╭(╯^╰)╮，还准备好最后提问时问他工作中哪里用到随机的知识了~


还好面试前一晚来地里看一下面经，一看吓一跳，根本就是一些概率和算法题嘛，被HR给坑了o(╥﹏╥)o


地里的农友真的非常给力！题目都非常相似！为了回馈大家攒人品，在此奉上最新的一面面经：


Q1 Throw a dice 100 times. What's the approximate probability of the sum exceeding 400?


Q2.1 X, Y are independent r.v. of standard normal distribution. What's the probability of X > 3Y?
Q2.2 What if X, Y are of uniform(0, 1)?


Q3 Design a sorting algorithm for an almost-sorted n-length array. "almost-sorted" means each element is k-length away from its correct position? What's the time complexity of your algorithm?
楼主毫无计算机背景o(╥﹏╥)o，碰到算法题完全靠intuition，最后这道题pass了。各位大神有没有idea？

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

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

最后面试官介绍了他的团队，只有7个人呐，所以楼主看看自己的背景还是不抱任何希望了~（虽然很后悔最后应该表现的更加热情一些）

第三题我做的话会用提前终止的快排

先解释一下快排：基本idea是，假设数组长度为n，随便取数组中一个数作为pivot，然后把pivot放到正确的位置，并且保证所有比pivot大的都在它之后，比它小的都在它之前——这一步操作是O(n)。然后就变成两个sub problem分治，直到这个subproblem里只包含一个元素为止——平均的情况是会有log(n)层，所以平均时间复杂度是O(nlogn)。

但是值得注意的是，在我们取了pivot之后，假设pivot的位置是m，那么pivot之前的m-1个元素离他们的正确位置最多就差m-1，因为他们的正确位置只可能在pivot前的m-1个位置中；同理，pivot之后的n-m个元素也最多离正确位置差n-m。所以如果我们需要at most k-length away，只需要在m-1（或者n-m）小于k的时候终止前半个（或者后半个）sub problem即可。所以平均的情况应该是会有log(n/k)层，因此时间复杂度是O(nlog(n/k))。

不保证这个做法是最好的做法，欢迎讨论

lz能分享一下最后一题的思路吗？完全下不去手啊。。。

tsl665 发表于 2018-10-29 10:10
第三题我做的话会用提前终止的快排

先解释一下快排：基本idea是，假设数组长度为n，随便取数组中一个数 ...

谢谢谢谢！

exlboy 发表于 2018-10-29 18:21
lz能分享一下最后一题的思路吗？完全下不去手啊。。。

运用半正定矩阵的性质

mergsort:

对于 n 个数，先分两半各自排序。然后并在一起，只有中间2k个数是乱的，对这 2k个数 mergesort 需要 klogk。
Tn <= 2Tn + klogk
递归
Tn <= nlogk

补充内容 (2019-1-8 13:19):
T(n) <= 2T(n/2) + klogk