在国外一跟老外吵架口语立刻就不够用了

一亩三分地论坛

 找回密码
 Sign Up 注册获取更多干货
E轮2.5亿美元融资
K12教育独角兽一起作业
北京-诚聘人工智能/教育/大数据岗
坐标湾区
Games Startup
招聘游戏开发工程师
游戏初创公司招聘工程师、UIUX Designer和游戏策划
码农求职神器Triplebyte:
不用海投
内推多家公司面试
把贵司招聘信息放这里
查看: 4437|回复: 35
收起左侧

Yahoo电面

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

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

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

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

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

评分

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的吧
Mobile Apps Category (English)728x90
回复 支持 反对

使用道具 举报

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
楼主例子里的就不连续啊,连续的就简单了。。。
.留学论坛-一亩-三分地
不连续就是combination sum了。或者就是pick coins 的变形
回复 支持 反对

使用道具 举报

八和九生 发表于 2016-7-2 14:13:21 | 显示全部楼层
如果只是返回有没有,boolean的话。那么可以用recursive 吧,感觉类似google 的面试题:coins change
先排个序,然后判断. 围观我们@1point 3 acres
{1,2,5,6,10,12,17}, 有没有15
等同于{2,5,6,10,12,17}, 有没有14. 1point3acres
{5,6,10,12,17}, 有没有12
{6,10,12,17}, 有没有7
返回上一层的false. 留学申请论坛-一亩三分地
{5,10,12,17}, 有没有6.本文原创自1point3acres论坛
返回上上一层的false
{5,6,10,12,17}, 有没有12.
返回true。
. visit 1point3acres for more.
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跑了一下,感觉没问题。
. visit 1point3acres for more.
  1. public static boolean hasTarget(ArrayList<Integer> list, int target){
  2.                 if(list.contains(target)). from: 1point3acres
  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;. from: 1point3acres
  17.         }
复制代码

补充内容 (2016-7-2 14:37):. 1point 3acres 论坛
test的部分也粘贴进去了= = 不好意思
回复 支持 反对

使用道具 举报

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

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

使用道具 举报

八和九生 发表于 2016-7-2 14:46:37 | 显示全部楼层
waikai 发表于 2016-7-2 14:43
这样和dfs区别不大吧,还是2^m时间复杂度 m = target?不知道理解对了没
. visit 1point3acres for more.
我认为应该是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……
应该是C^n 的时间复杂度(我们假 ...
. Waral 博客有更多文章,
好像有办法 target^2啊。你等我写下贴上讨论下
回复 支持 反对

使用道具 举报

八和九生 发表于 2016-7-2 14:56:50 | 显示全部楼层
waikai 发表于 2016-7-2 14:54. From 1point 3acres bbs
好像有办法 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};
  5.                 int t = 4;
  6.                 Sooo r = new Sooo();
  7.                
  8.                 System.out.println(r.find(num, t));
  9.         }
  10. }
  11. class Sooo {. 牛人云集,一亩三分地
  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.                        
  20.                         ArrayList<Integer> tmp = new ArrayList<>();
  21.                         for (Integer prvRes : rec) {. visit 1point3acres for more.
  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.                         }. more info on 1point3acres
  26.                        
  27.                         //merge
  28.                         ArrayList<Integer> newList = new ArrayList<>();
  29.                         int a = 0; int b = 0;
  30.                         while (a < tmp.size() || b < rec.size()) {
  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);. 1point 3acres 论坛
  35.                                         a++;
  36.                                 }else {
  37.                                         newList.add(l2);
  38.                                         b++;
  39.                                 }.1point3acres网
  40.                         } //O(m)
  41.                         rec = newList;. from: 1point3acres
  42.                 }
  43.                 return rec.contains(m);
  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))。。。我这不考虑边界的习惯估计是好不了了。。。
回复 支持 反对

使用道具 举报

本版积分规则

提醒:发帖可以选择内容隐藏,部分板块支持匿名发帖。请认真读完以下全部说明:

■隐藏内容方法: [hide=200]你想要隐藏的内容比如面经[/hide]
■意思是:用户积分低于200则看不到被隐藏的内容
■可以自行设置积分值,不建议太高(200以上太多人看不到),也不建议太低(那就没必要隐藏了)
■建议只隐藏关键内容,比如具体的面试题目、涉及隐私的信息,大部分内容没必要隐藏。
■微信/QQ/电子邮件等,为防止将来被骚扰甚至人肉,以论坛私信方式发给对方最安全。
■匿名发帖的板块和方法:http://www.1point3acres.com/bbs/thread-405991-1-1.html

关闭

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

手机版|小黑屋|一亩三分地论坛声明

custom counter

GMT+8, 2018-5-23 21:26

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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