一亩三分地论坛

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

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

Yahoo电面

[复制链接] |试试Instant~ |关注本帖
hkc593 发表于 2016-7-2 11:55:53 | 显示全部楼层 |阅读模式

2016(7-9月) 码农类 博士 全职@Yahoo - Other - HR筛选 |Otherfresh grad应届毕业生

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

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

x
给一个array,都是正整数,没有重复,问是否存在一个subsequence其和等于target.例如:{1,2,5,6,10,12,17}, target=15. 应该返回true, 因为有{1,2,12}或{5,10}. 应该是跪了,实在没想出什么好的解

. From 1point 3acres bbs

评分

1

查看全部评分

本帖被以下淘专辑推荐:

frozencookie 发表于 2016-7-5 14:07:32 | 显示全部楼层
不是背包么...背包的大小是target,物品价值和重量相等,复杂度n*m
回复 支持 1 反对 0

使用道具 举报

lookbackinanger 发表于 2016-7-4 04:42:58 | 显示全部楼层
感觉是backpack问题啊
回复 支持 1 反对 0

使用道具 举报

waikai 发表于 2016-7-2 12:26:42 | 显示全部楼层
谢谢lz的面经。lz怎么做的啊,复杂度O(n^2)么?我也想不着好方法
回复 支持 反对

使用道具 举报

glaciersilent 发表于 2016-7-2 13:09:00 | 显示全部楼层
这不是combination sum么?还是对复杂度有要求?
回复 支持 反对

使用道具 举报

glory007 发表于 2016-7-2 13:25:03 | 显示全部楼层
多谢分享啊!
回复 支持 反对

使用道具 举报

gxiverson_1 发表于 2016-7-2 13:50:20 | 显示全部楼层
waikai 发表于 2016-7-2 12:26
谢谢lz的面经。lz怎么做的啊,复杂度O(n^2)么?我也想不着好方法

O(n^2)显然搞不定吧,subset sum是NP-Complete的吧
回复 支持 反对

使用道具 举报

blackrose 发表于 2016-7-2 14:04:11 | 显示全部楼层
难道不是连续的subarray么。。。。。
回复 支持 反对

使用道具 举报

gxiverson_1 发表于 2016-7-2 14:07:26 | 显示全部楼层
blackrose 发表于 2016-7-2 14:04
难道不是连续的subarray么。。。。。

楼主例子里的就不连续啊,连续的就简单了。。。
回复 支持 反对

使用道具 举报

blackrose 发表于 2016-7-2 14:11:44 | 显示全部楼层
gxiverson_1 发表于 2016-7-2 14:07
楼主例子里的就不连续啊,连续的就简单了。。。
. more info on 1point3acres.com
不连续就是combination sum了。或者就是pick coins 的变形
回复 支持 反对

使用道具 举报

八和九生 发表于 2016-7-2 14:13:21 | 显示全部楼层
如果只是返回有没有,boolean的话。那么可以用recursive 吧,感觉类似google 的面试题:coins change
先排个序,然后判断
{1,2,5,6,10,12,17}, 有没有15
等同于{2,5,6,10,12,17}, 有没有14-google 1point3acres
{5,6,10,12,17}, 有没有12
{6,10,12,17}, 有没有7
返回上一层的false
{5,10,12,17}, 有没有6
返回上上一层的false
{5,6,10,12,17}, 有没有12.
返回true。

backtracking


补充内容 (2016-7-2 14:38):
public static boolean hasTarget(ArrayList<Integer> list, int target){
                if(list.contains(target))
                        return true;

                for(int i=0; i<list.size();...
回复 支持 反对

使用道具 举报

waikai 发表于 2016-7-2 14:25:22 | 显示全部楼层
gxiverson_1 发表于 2016-7-2 13:50
O(n^2)显然搞不定吧,subset sum是NP-Complete的吧

啊,我考虑错了。想说的是 0(m^2)   target = m
回复 支持 反对

使用道具 举报

八和九生 发表于 2016-7-2 14:36:47 | 显示全部楼层
写了段代码,拿eclipse跑了一下,感觉没问题。

  1. public static boolean hasTarget(ArrayList<Integer> list, int target){
  2.                 if(list.contains(target))
  3.                         return true;
  4.                
  5.                         System.out.println(list.size() + " " + target);
  6.                 for(int i=0; i<list.size(); i++){
  7.                         if(list.indexOf(i) < target){
  8.                                 int temp = list.get(i);
  9.                                 list.remove(i);
  10.                                 if(hasTarget(list, target - temp))
  11.                                         return true;
  12.                                 else
  13.                                 list.add(i, temp);.鐣欏璁哄潧-涓浜-涓夊垎鍦
  14.                         }
  15.                 }
  16.                 return false;
  17.         }
复制代码

补充内容 (2016-7-2 14:37):. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
test的部分也粘贴进去了= = 不好意思
回复 支持 反对

使用道具 举报

waikai 发表于 2016-7-2 14:43:59 | 显示全部楼层
八和九生 发表于 2016-7-2 14:36
写了段代码,拿eclipse跑了一下,感觉没问题。

. From 1point 3acres bbs这样和dfs区别不大吧,还是2^m时间复杂度 m = target?不知道理解对了没
回复 支持 反对

使用道具 举报

八和九生 发表于 2016-7-2 14:46:37 | 显示全部楼层
waikai 发表于 2016-7-2 14:43
这样和dfs区别不大吧,还是2^m时间复杂度 m = target?不知道理解对了没

我认为应该是2^n 的时间复杂度。 n是数组的长度
回复 支持 反对

使用道具 举报

waikai 发表于 2016-7-2 14:48:19 | 显示全部楼层
八和九生 发表于 2016-7-2 14:46
我认为应该是2^n 的时间复杂度。 n是数组的长度
.鐣欏璁哄潧-涓浜-涓夊垎鍦
不用呀。比如【1,2,4,33,44,543,..., 23432】 求target 是 6,数组里大于6的就不用考虑了,所以说target^2

补充内容 (2016-7-2 15:18):
错了错了。我想说我写的应该是target^2
回复 支持 反对

使用道具 举报

八和九生 发表于 2016-7-2 14:51:46 | 显示全部楼层
waikai 发表于 2016-7-2 14:48
不用呀。比如【1,2,4,33,44,543,..., 23432】 求target 是 6,数组里大于6的就不用考虑了,所以说ta ...

你要是那么考虑的话,还有一种[1,2,3,4,5,6...100.] taget = 12345……
应该是C^n 的时间复杂度(我们假设N是小于target的所有数值吧= = )

N^2 或者 target^2肯定到不了啊…… 如果是N^2那是挺快的。backtracking是C^N, C的N次方
回复 支持 反对

使用道具 举报

waikai 发表于 2016-7-2 14:54:04 | 显示全部楼层
八和九生 发表于 2016-7-2 14:51
你要是那么考虑的话,还有一种[1,2,3,4,5,6...100.] taget = 12345…… . Waral 鍗氬鏈夋洿澶氭枃绔,
应该是C^n 的时间复杂度(我们假 ...

好像有办法 target^2啊。你等我写下贴上讨论下
回复 支持 反对

使用道具 举报

八和九生 发表于 2016-7-2 14:56:50 | 显示全部楼层
waikai 发表于 2016-7-2 14:54
好像有办法 target^2啊。你等我写下贴上讨论下

好的啊,你写好了私信我地址,我还不着急睡呢
回复 支持 反对

使用道具 举报

waikai 发表于 2016-7-2 15:02:57 | 显示全部楼层
八和九生 发表于 2016-7-2 14:56
好的啊,你写好了私信我地址,我还不着急睡呢
  1. import java.util.*;

  2. class Test {. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
  3.         public static void main(String[] args) {
  4.                 int[] num = {1,2,5,6,10,17};. 1point 3acres 璁哄潧
  5.                 int t = 4;.鐣欏璁哄潧-涓浜-涓夊垎鍦
  6.                 Sooo r = new Sooo();
  7.                 . 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
  8.                 System.out.println(r.find(num, t));
  9.         }
  10. }
  11. class Sooo {. 1point3acres.com/bbs
  12.         public boolean find(int[] nums, int m) {
  13.                 ArrayList<Integer> rec = new ArrayList<Integer>();
  14.                 Arrays.sort(nums);
  15.                 if (m == 0) return false;
  16.                 rec.add(0);
  17.                 for (int e : nums) {
  18.                         if (e > m) break; //O(m)
  19.                         . Waral 鍗氬鏈夋洿澶氭枃绔,
  20.                         ArrayList<Integer> tmp = new ArrayList<>();
  21.                         for (Integer prvRes : rec) {
  22.                                 int newRes = prvRes + e;
  23.                                 if (newRes > m || tmp.size() + rec.size() > m+1) break; //O(m+1)
  24.                                 if (!tmp.contains(newRes) && !rec.contains(newRes)) tmp.add(newRes);
  25.                         }
  26.                        
  27.                         //merge. 1point3acres.com/bbs
  28.                         ArrayList<Integer> newList = new ArrayList<>();
  29.                         int a = 0; int b = 0;
  30.                         while (a < tmp.size() || b < rec.size()) {. visit 1point3acres.com for more.
  31.                                 int l1 = a < tmp.size() ? tmp.get(a): Integer.MAX_VALUE;
  32.                                 int l2 = b < rec.size() ? rec.get(b) : Integer.MAX_VALUE;
  33.                                 if (l1 < l2) {
  34.                                         newList.add(l1);
  35.                                         a++;
  36.                                 }else {
  37.                                         newList.add(l2);
  38.                                         b++;
  39.                                 }
  40.                         } //O(m)
  41.                         rec = newList;
  42.                 }
  43.                 return rec.contains(m);. visit 1point3acres.com for more.
  44.         }
  45. }
复制代码
回复 支持 反对

使用道具 举报

waikai 发表于 2016-7-2 15:10:02 | 显示全部楼层
八和九生 发表于 2016-7-2 14:56
好的啊,你写好了私信我地址,我还不着急睡呢
.1point3acres缃
写完才发现,用booolean[m+1]会好很多。应该明白我的意思。就是不停的更新一个boolean[m+1]的数组,一直更新到nums里面的数 i > m为止,也就是更新最多m次。就是O(m(m+1))

补充内容 (2016-7-2 15:21):
更新最多 x = min(N, target) 次。。时间复杂度是就是O(x(m+1))。。。我这不考虑边界的习惯估计是好不了了。。。
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2017-1-18 01:23

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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