亚麻实习Timeline以及VO过经

1/17 内推
2/15 OA1 2/17 做完
2/18 OA2 2/22 做完
3/12 VO邀请 选了 3/21 号
3/19 告知当周VO预定完了，重新预定
3/28 VO
4/4 口头Offer
OA1， OA2 都是地里老题，我以前帖子有
下面是VO：
BQ：Tight ddl + stop and evaluate + lower the risk + team collaboration
Coding:
给一个数组和interval，输出新数组是这个数组的interval的sum的序列，例如：
input: (int[] arr = {1, 5, 7, 8, 12}, int interval = 3)
output: res = [13, 20, 27]
暴力解法 O(mn)，稍微优化一下 O(n)

followup: 从 sum 改成 max，需用 max heap 来维持
等了一个星期很慌，好在拿到offer，祝各位上岸

恭喜恭喜！！！请问问了关于简历上面的问题吗？

关注一波，不是很会用max heap怎么找max，目前只能想到 sort + two pointers 来不停打擂台维护。时间 O(nlogn). 希望大佬提供一下思路。。

补充内容 (2019-4-5 16:25):
另外，stop and evaluate + lower the risk 这啥意思。。？？

EdwardSea 发表于 2019-4-5 13:24
恭喜恭喜！！！请问问了关于简历上面的问题吗？

一点都没问，但我看别人VO有问的，所以这个不确定

qianyilun 发表于 2019-4-5 16:24
关注一波，不是很会用max heap怎么找max，目前只能想到 sort + two pointers 来不停打擂台维护。时间 O(nlo ...

这题显然不能sort啊，输入数组的顺序决定了输出，你一sort不全乱了吗。max heap 在 Java 里就是 PriorityQueue。
stop and evaluate 就是问你：“有没有遇到一个情况，你需要停下来想一想，再决定是否继续原来的方向”
lower the risk 就是问：“你是如何降低风险的（可以是做项目，做作业的情况）”

题目还行啊，一眼就是DP

优化成O(n)要怎么做呢老哥

请问楼主找max用heap时间复杂度是又变成O(mn)了吗

也只 发表于 2019-4-6 04:55
请问楼主找max用heap时间复杂度是又变成O(mn)了吗

O(m * log(n)) 其中m是数组长度，n是interval大小

dhwuho 发表于 2019-4-6 04:52
优化成O(n)要怎么做呢老哥

维持一个 sum 值，之后每次递进都减去首项，加上末项