Coursera OA1 - 新题面经

做之前准备了一天的OA面经，然而开始做后来了两道完全没准备到的题目。。
1. Longest SubArray.
    输入int[] a以及int k, 要返回longest subarray使得该array的sum不大于k. 只要返回最大的长度即可。一开始理解错了题意以为是像subset这样可以从array中任意挑元素组成新array。ran了几个test case发现

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

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

，早点拿offer。。。 Never Say Never....

第一题感觉上是leetcode原题。

楼主是烈士

yaoguoxing 发表于 2016-9-18 07:56
第一题感觉上是leetcode原题。

好像有点区别。。这道题没有指定integer是positive的，这就有点麻烦了，而且sum <= k，LC325是 ==k. 这题如果用TreeMap或者HashMap+PriorityQueue的话也要O(n2), 我是用双指针类似brute force做的。。求请教有没有更好的方法。。。

楼主这是哪一天的面筋啊？

dsdgjhbxewj1121 发表于 2016-9-18 09:28
楼主这是哪一天的面筋啊？

就是今天的面经，两个小时前做的

我翔不哭，摸摸头！

awpdtx 发表于 2016-9-18 09:33
就是今天的面经，两个小时前做的

9/17的oa目前似乎已经有三个版本了

awpdtx 发表于 2016-9-18 08:44
好像有点区别。。这道题没有指定integer是positive的，这就有点麻烦了，而且sum

感觉上双指针移动 O(n) 就够？ 超了左边移动，没超右边移动，重合了一起移动，记录最大指针距离

maxio110 发表于 2016-9-22 22:12
感觉上双指针移动 O(n) 就够？ 超了左边移动，没超右边移动，重合了一起移动，记录最大指针距离

这个two pointer要求array里的数得都是正数啊