一亩三分地论坛

 找回密码
 获取更多干货,去instant注册!

扫码关注一亩三分地公众号
查看: 683|回复: 20
收起左侧

刚结束的PocketGem电面,竟然又碰到了新题

[复制链接] |试试Instant~ |关注本帖
niyanwen212 发表于 2015-11-11 06:16:42 | 显示全部楼层 |阅读模式

2015(10-12月) 码农类 硕士 全职@PoketGem - 内推 - 技术电面 |Failfresh grad应届毕业生

注册一亩三分地论坛,查看更多干货!

您需要 登录 才可以下载或查看,没有帐号?获取更多干货,去instant注册!

x
刚刚结束了pocketgem的电面,人生第一次技术面试,三哥,人还可以,就是听不太懂他说什么,第一反应是twosum,他说subarry不止两个数,悲剧……然后打算用dfs,他说这样不对,之后我就懵逼了。。。不太知道怎么做了,题目截下来了,求讨论做法
求加米
. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴

Find the minimum length subarray, from a given array, such that sum of elements of the subarray equals to S, a given value.
I/P: [2, 3, 4, 5], 9
O/P: [4, 5]


评分

4

查看全部评分

yyz999 发表于 2015-11-11 09:56:18 | 显示全部楼层
zyy6799 发表于 2015-11-11 09:53
一般来说为何复杂度是O(N)呐? 不应该是O(N^2)么?

没负数用two pointer 每个pointer都最多移动n次,当然是O(n). from: 1point3acres.com/bbs

补充内容 (2015-11-11 09:58):
你的名字是zyy么,哈哈,正好和我相反
话说蛋疼的ProcketGems二面放了我鸽子之后至今没有给我Reschedule,忒不靠谱
回复 支持 1 反对 0

使用道具 举报

yongmat 发表于 2015-11-11 09:35:10 | 显示全部楼层
我的思路应该是比较笨的,不过也应该可以解的出来。
设原数组为nums, 先重新创建一个数组sums,长度和nums相同。
sums[0] = nums[0]
sums[n] = sums[n-1] + nums[n]
这样赋值后,sums[i]就代表的意义就是从nums[0]开始,一直加到nums[i]的和。
首先扫一sums看看里面是否存在target,如果存在的话,把序号用最小值min记下来。没有的话把min记成nums.length
然后用i,j两个变量循环, 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
for(int i = 0; i < sums.length - 1; i++){
   for(int j = i + 1; j < i + min + 1 && j < sums.length; j++){
        if(sum[j] - sum[i] == target){
             if( j - i < min)
                  min = j - i;. from: 1point3acres.com/bbs
       }
    }
}
中间的判断条件可能有一些问题,马上要下班了,也不细推了,大概就是那个意思。
这办法八成属于在leetcode里能造成time limit的,献丑了。
回复 支持 1 反对 0

使用道具 举报

zyy6799 发表于 2015-11-11 06:43:56 | 显示全部楼层
PAT PAT... 三个说话是这样的。。。
Two pointers?
回复 支持 反对

使用道具 举报

inkhay 发表于 2015-11-11 08:06:31 | 显示全部楼层
实在不行就俩for-loop 强行解吧-google 1point3acres
明天电面看到新题 实在心痛 多谢lz
回复 支持 反对

使用道具 举报

xiaoyucool 发表于 2015-11-11 08:48:56 | 显示全部楼层
先sort,然后开个新数组 sum, sum[i] 对应 nums[0] +...+ nums[i-1]
然后二分查找来找最短数组。. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
印象中leetcode里面有个类似的题,似乎可以借鉴下思路。
回复 支持 反对

使用道具 举报

inkhay 发表于 2015-11-11 09:07:41 | 显示全部楼层
xiaoyucool 发表于 2015-11-11 08:48. 1point 3acres 璁哄潧
先sort,然后开个新数组 sum, sum 对应 nums[0] +...+ nums
然后二分查找来找最短数组。
印象中leetcode ...

不好意思问一下哈,为什么对应的是nums[0]+  。。。 + nums[i-1]
这题里答案的subarray不一定是从nums[0]开始的啊,我觉得按照这个思路是用二维数组,对应位置关系,那还是相当于是两个for-loop循环找到所有subarray求最小啊。。。
不知道我是不是理解错了你说的意思
回复 支持 反对

使用道具 举报

lzyfriday 发表于 2015-11-11 09:19:17 | 显示全部楼层
用DFS应该可以啊。找到所有可能的subarray然后取其中最短的吧。
回复 支持 反对

使用道具 举报

348210207 发表于 2015-11-11 09:27:36 | 显示全部楼层
这题要不是每个都从头开始或者数组必须连续的话就是dfs。估计烙印当时每太听清你说啥吧。。。。。
回复 支持 反对

使用道具 举报

yyz999 发表于 2015-11-11 09:50:41 | 显示全部楼层
xiaoyucool 发表于 2015-11-11 08:48.鐣欏璁哄潧-涓浜-涓夊垎鍦
先sort,然后开个新数组 sum, sum 对应 nums[0] +...+ nums
然后二分查找来找最短数组。
印象中leetcode ...

subarray应该不能sort吧
. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴. From 1point 3acres bbs
如果没有负数,two pointer 大了移动左边,小了移动右边,update最短长度。有负数估计就得n^2了
回复 支持 反对

使用道具 举报

zyy6799 发表于 2015-11-11 09:53:48 | 显示全部楼层
yyz999 发表于 2015-11-11 09:50
subarray应该不能sort吧
. Waral 鍗氬鏈夋洿澶氭枃绔,
如果没有负数,two pointer 大了移动左边,小了移动右边,update最短长度。有 ...

一般来说为何复杂度是O(N)呐? 不应该是O(N^2)么?
回复 支持 反对

使用道具 举报

zyy6799 发表于 2015-11-11 10:02:04 | 显示全部楼层
yyz999 发表于 2015-11-11 09:56. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
没负数用two pointer 每个pointer都最多移动n次,当然是O(n)

补充内容 (2015-11-11 09:58):

哈哈哈!对,zyy!!话说这家对女生貌似很松。男生的话就要多给力了。。。。。
回复 支持 反对

使用道具 举报

ryancooper 发表于 2015-11-11 10:20:41 | 显示全部楼层
和正数负数没有关系。在iteration期间maintain一个hashtable,key是在当前i之前所有出现过的前缀和,value是前缀和对应的最靠近i的下标。. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
  1. def solve(arr, t):
  2.         table, minLen, s, e, acc = {0:-1}, len(arr) + 1, -1, -1, 0
  3.         for i in xrange(len(arr)):
  4.                 acc += arr[i]
  5.                 if acc - t in table and minLen > i - table[acc - t]:
  6.                         minLen = i - table[acc - t]
  7.                         e, s = i, table[acc - t] + 1
  8.                 table[acc] = i-google 1point3acres
  9.         return (s, e)
复制代码
回复 支持 反对

使用道具 举报

yoooda 发表于 2015-11-11 11:13:21 | 显示全部楼层
这个 sum( n )= sum(n-1) + num(n) 的方法很精妙啊。
但我在想如果原题要求的结果不一定是连续subarray,而是任意的sub set的话呢?
现在唯一能想到的就是BruteForce生成所有sub set,然后找里面求和等于value的最短的set。. Waral 鍗氬鏈夋洿澶氭枃绔,
不知各位高手们有没有跟聪明算法??
回复 支持 反对

使用道具 举报

 楼主| niyanwen212 发表于 2015-11-11 12:06:23 | 显示全部楼层
xiaoyucool 发表于 2015-11-11 08:48
先sort,然后开个新数组 sum, sum 对应 nums[0] +...+ nums
然后二分查找来找最短数组。
印象中leetcode ...

三哥明确说了不能sort
回复 支持 反对

使用道具 举报

 楼主| niyanwen212 发表于 2015-11-11 12:07:23 | 显示全部楼层
348210207 发表于 2015-11-11 09:27
这题要不是每个都从头开始或者数组必须连续的话就是dfs。估计烙印当时每太听清你说啥吧。。。。。

他说了不能用dfs,他最后说用window size这样子,貌似是leetcode里面那题的做法,209
回复 支持 反对

使用道具 举报

 楼主| niyanwen212 发表于 2015-11-11 12:07:39 | 显示全部楼层
yyz999 发表于 2015-11-11 09:50. 1point3acres.com/bbs
subarray应该不能sort吧

如果没有负数,two pointer 大了移动左边,小了移动右边,update最短长度。有 ...
.鐣欏璁哄潧-涓浜-涓夊垎鍦
哎对,就是这个做法
回复 支持 反对

使用道具 举报

ryancooper 发表于 2015-11-11 12:34:14 | 显示全部楼层
niyanwen212 发表于 2015-11-11 12:07
哎对,就是这个做法

这个只能针对无负数情况,有负数的话不一定work,因为没有了单调性的保证
回复 支持 反对

使用道具 举报

liaoqi343359 发表于 2015-11-11 12:39:02 | 显示全部楼层
用一个滑动窗口做这道题,record记录最左边的坐标       
. more info on 1point3acres.com
public int minLen(int[] array, int target){
                 int record = 0;. more info on 1point3acres.com
                 int sum = 0;
                 int min = Integer.MAX_VALUE;.鐣欏璁哄潧-涓浜-涓夊垎鍦
                 for(int i = 0; i < array.length; i++){
                     sum += array[i]; . more info on 1point3acres.com
                      while(sum > target){
                         sum  -=  array[record++];
                     }
                      if(sum == target){
                               min = Math.min(min,i-record+1);
                             }
                 }
                 return min;

         }
回复 支持 反对

使用道具 举报

nevermor 发表于 2015-11-11 12:45:03 | 显示全部楼层
两根指针从头扫就可以了,如果和比目标小就移后面的指针,比目标大就移前面的,找到一个解就记录下两根指针位置,后面的解比较一下长度,o(n)时间
回复 支持 反对

使用道具 举报

本版积分规则

请点这里访问我们的新网站:一亩三分地Instant.

Instant搜索更强大,不扣积分,内容组织的更好更整洁!目前仍在beta版本,努力完善中!反馈请点这里

关闭

一亩三分地推荐上一条 /5 下一条

手机版|小黑屋|一亩三分地论坛声明 ( 沪ICP备11015994号 )

custom counter

GMT+8, 2016-12-8 05:30

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

快速回复 返回顶部 返回列表