Amne的OA

刚做完amne的OA，分享一下，攒人品
近3小时，五道题
1. 有一些输入，代表的是会议开始时间starttime，会议结束时间endtime，整体开始时间（0），整体结束时间（t），k调整会议时间的次数。问，在调整次数为k的情况下，最长的单次休息时间为多少。O（n）过的
2. 数据库的题目，网上可以找到，二叉树，写query，输出每个id是根，内部结点还是叶子
3. shell的。必须连到server上写。接收用户输入，求和。建议做之前再熟悉下vim，好久不用，真的好生疏。
4. 题目

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

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

感。楼主扫过题目后，发现只有一道见过的，花了5分钟平复了一下心情，再回头写题，才慢慢找到感觉。
心态很重要心态很重要心态很重要

谢谢楼主分享，请问一下第五题要答呢？感觉nlogn应该是最优的解法了呀，谢谢！

楼主您好，我今天也做了oa，最后一道题我用了NlogN的方法没有过啊，想请教一下你是怎么做的？

tingrany 发表于 2018-11-6 11:26
楼主您好，我今天也做了oa，最后一道题我用了NlogN的方法没有过啊，想请教一下你是怎么做的？

1. 先排个序（nlogn）
2. 然后异向双指针，固定left，right向左移，直到num[left] * nums[right] <= target，则停止，rst += right - left，tag = right；然后left++，right从tag开始左移。大概就是这样

只身回马枪 发表于 2018-11-7 02:34
1. 先排个序（nlogn）
2. 然后异向双指针，固定left，right向左移，直到num[left] * nums[right]

做完后问了好多人，都没有问出来线性的解法，估计nlogn就是最优了吧。估计剩下的部分就是工程上的复杂度优化，而非理论上的复杂度优化了。

只身回马枪 发表于 2018-11-7 02:38
做完后问了好多人，都没有问出来线性的解法，估计nlogn就是最优了吧。估计剩下的部分就是工程上的复杂度 ...

哦哦明白了，你第二步的这个做法比较好，是一个O(n)的复杂度，我的做法是建一个Treemap, 然后loop 所有的元素，复杂度是O(nlogn)，可能是差到这里了。谢谢！