一亩三分地论坛

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

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

Facebook 电面

[复制链接] |试试Instant~ |关注本帖
mymulife 发表于 2016-7-19 04:19:51 | 显示全部楼层 |阅读模式

2016(1-3月) 码农类 硕士 全职@Facebook - 网上海投 - 技术电面 |Other在职跳槽

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

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

x
两道题
1) 给一个字符串和一个输入的字符,要求移走给定的字符, Leetcode有类似的题,是移走数字0
2) 给一个数字array , 有正有负数。给一个数, 找array中连续的数字,其和是给定的数。leecode应该有类似的题目,但记不清了。是用hash table做的


评分

2

查看全部评分

Badger96 发表于 2016-7-20 00:11:37 | 显示全部楼层
试做一下第二题,应该是lintcode上subarray sum的变形:
public ArrayList<Integer> subarraySum(int[] nums, int target) {
    ArrayList<Integer> res = new ArrayList<>();
    HashMap<Integer, Integer> map = new HashMap<>();. From 1point 3acres bbs
    map.put(0, -1);
    int sum = 0;
    for (int i = 0; i < nums.length; i++) {
        sum += nums[i];
        if (map.containsKey(sum - target)) {
            res.add(map.get(sum - target) + 1);
            res.add(i);
            return res;
        } else {
            map.put(sum, i);
        }. From 1point 3acres bbs
    }    return res;
}
. more info on 1point3acres.com
上面答案是求出符合答案的任意区间即返回的情况。如果要求写出所有符合的区间,那可能要建一个HashMap<Integer, ArrayList<Integer>>,用arraylist来储存所有sum相同的index,每当遇到map.containsKey(sum)的情况就往arraylist里加当前index,而当map.containsKey(sum - target)时就把那个arraylist里的index都for一遍来输出区间结果,如[index1 + 1, i],[index2 + 1, i]等等。


回复 支持 2 反对 0

使用道具 举报

wszk1992 发表于 2016-7-19 18:05:52 | 显示全部楼层
partial_sum 就是 建一个数组sum[n], sum[i]代表从num[0]累加到num[i]的和, sum[j] - sum[i] 就代表从num[i]加到num[j]的和, 这样就转化为2sum这道题了
回复 支持 2 反对 0

使用道具 举报

hongbiao.yang 发表于 2016-7-19 04:35:41 | 显示全部楼层
第2)题用dp,用二维数组记录所有{i..j}的和?
回复 支持 反对

使用道具 举报

glaciersilent 发表于 2016-7-19 05:14:02 | 显示全部楼层
第二题求partial_sum,然后看是否有两个sum差target或者-target,算是lc two sum的变种
回复 支持 反对

使用道具 举报

hongbiao.yang 发表于 2016-7-19 05:36:32 | 显示全部楼层
glaciersilent 发表于 2016-7-19 05:14. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
第二题求partial_sum,然后看是否有两个sum差target或者-target,算是lc two sum的变种

什么是partial_sum
回复 支持 反对

使用道具 举报

chen6145 发表于 2016-7-19 12:41:06 | 显示全部楼层
glaciersilent 发表于 2016-7-19 05:14
第二题求partial_sum,然后看是否有两个sum差target或者-target,算是lc two sum的变种

不理解,暴力不就是n^2嘛。。
回复 支持 反对

使用道具 举报

jy_121 发表于 2016-7-19 13:28:49 | 显示全部楼层
问下楼主第二题要求是找出所有情况还是只要一种即可?谢谢
回复 支持 反对

使用道具 举报

readman 发表于 2016-7-19 20:00:02 | 显示全部楼层
wszk1992 发表于 2016-7-19 18:05
partial_sum 就是 建一个数组sum[n], sum代表从num[0]累加到num的和, sum[j] - sum 就代表从num加到num[j] ...

所以和2sum的关系是.........
回复 支持 反对

使用道具 举报

readman 发表于 2016-7-19 20:02:24 | 显示全部楼层
wszk1992 发表于 2016-7-19 18:05
partial_sum 就是 建一个数组sum[n], sum代表从num[0]累加到num的和, sum[j] - sum 就代表从num加到num[j] ...
. 1point3acres.com/bbs
而且是sum[j] - sum[i-1] 是[i,j]的和吧...
回复 支持 反对

使用道具 举报

wszk1992 发表于 2016-7-19 22:16:36 | 显示全部楼层
readman 发表于 2016-7-19 20:02
而且是sum[j] - sum 是的和吧...

这是我的解题思路,仅供参考。时间复杂度O(n),空间复杂度O(n)
  1. vector<int> rangeSum(vector<int>& nums, int target) {
  2.     vector<int> sum(nums.size() + 1, 0);
  3.     vector<int> res;
  4.     unordered_map<int, int> map;
  5.     sum[0] = 0;
  6.     //得到sum数组, sum[i] 为 num[0]+...+num[i-1]的和, sum[0]为0
  7.     //问题转化为求满足 sum[j] - sum[i] == target 的解 (j>i), 其中 <span style="line-height: 1.5;">sum[j] - sum[i] 即</span><span style="line-height: 1.5;">nums在[i,j-1]的和</span>
复制代码
回复 支持 反对

使用道具 举报

wszk1992 发表于 2016-7-19 22:18:28 | 显示全部楼层
  1. vector<int> rangeSum(vector<int>& nums, int target) {
  2.         vector<int> sum(nums.size() + 1, 0);
  3.         vector<int> res;
  4.         unordered_map<int, int> map;. visit 1point3acres.com for more.
  5.         sum[0] = 0;
  6.         //得到sum数组, sum[i] 为 num[0]+...+num[i-1]的和, sum[0]为0
  7.         //问题转化为求满足 sum[j] - sum[i] == target 的解 (j>i) 即 nums在[i,j-1]的和
  8.         for(int i = 0; i < nums.size(); i++) {
  9.                 sum[i + 1] = sum[i] + nums[i];. 鍥磋鎴戜滑@1point 3 acres
  10.         }
  11.         //使用hashmap, key为sum[i] + target, value为i. 当找到sum[j] == sum[i] + target时返回此时的index
  12.         for(int i = 0; i < sum.size(); i++) {
  13.                 if(map.find(sum[i]) == map.end()) {. from: 1point3acres.com/bbs
  14.                         map[sum[i] + target] = i;
  15.                 }else {
  16.                         res.push_back(map[sum[i]]);
  17.                         res.push_back(i-1);
  18.                         return res;
  19.                 }
  20.         }. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
  21.         return res;. from: 1point3acres.com/bbs
  22. }
复制代码
回复 支持 反对

使用道具 举报

Badger96 发表于 2016-7-19 22:28:07 | 显示全部楼层
第二题subarray sum吧,lintcode有类似的题
回复 支持 反对

使用道具 举报

readman 发表于 2016-7-19 23:05:28 | 显示全部楼层

这个好像是对的..但是你这里的sum

sum 为 num[0]+...+num[i-1]的和


而你上一个帖子说的是
. more info on 1point3acres.com
sum 为 num[0]+...+num的和. 1point 3acres 璁哄潧
. from: 1point3acres.com/bbs
鏉ユ簮涓浜.涓夊垎鍦拌鍧.
...
回复 支持 反对

使用道具 举报

 楼主| mymulife 发表于 2016-7-20 00:57:41 | 显示全部楼层
第二题只要返回true/false就行,不需要都找出来
回复 支持 反对

使用道具 举报

Badger96 发表于 2016-7-20 01:26:13 | 显示全部楼层
mymulife 发表于 2016-7-20 00:57. 1point3acres.com/bbs
第二题只要返回true/false就行,不需要都找出来

那就好,index都不用记了,一个hashset可以
回复 支持 反对

使用道具 举报

readman 发表于 2016-7-20 02:17:22 | 显示全部楼层
Badger96 发表于 2016-7-20 00:11.鐣欏璁哄潧-涓浜-涓夊垎鍦
试做一下第二题,应该是lintcode上subarray sum的变形:
public ArrayList subarraySum(int[] nums, int t ...

这个0,-1的corn case 解决的不错!
回复 支持 反对

使用道具 举报

Badger96 发表于 2016-7-20 02:41:35 | 显示全部楼层
readman 发表于 2016-7-20 02:17
这个0,-1的corn case 解决的不错!
鏉ユ簮涓浜.涓夊垎鍦拌鍧.
谢谢这个专门用来解决第一项即为结果的情况
回复 支持 反对

使用道具 举报

997562971@qq.co 发表于 2016-7-31 07:59:13 | 显示全部楼层
Badger96 发表于 2016-7-20 01:26
那就好,index都不用记了,一个hashset可以

还是要记住index吧。。。比如。arr = [1,2,3] . 所以 sum[] = [1,3,6]. 如果 target = -5 (不能实现)。当int i=0的时候,sum[0]等于1. target-sum[0] 等于6. 在hashset里,就错了。所以还是要HashMap. 感觉。
回复 支持 反对

使用道具 举报

Badger96 发表于 2016-7-31 12:38:17 | 显示全部楼层
997562971@qq.co 发表于 2016-7-31 07:59
还是要记住index吧。。。比如。arr = [1,2,3] . 所以 sum[] = [1,3,6]. 如果 target = -5 (不能实现)。 ...
.鏈枃鍘熷垱鑷1point3acres璁哄潧
i = 0时还没把6添加进hashset啊,i = 3时才会把6加进去。你如果一开始先把后面的sum加进去当然会错了
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-8 10:29

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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