一亩三分地论坛

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

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

Facebook intern二面血崩崩崩

[复制链接] |试试Instant~ |关注本帖
markieff 发表于 2016-3-11 10:04:09 | 显示全部楼层 |阅读模式

2016(7-9月) 码农类 硕士 实习@Facebook - 内推 - 技术电面 |Otherfresh grad应届毕业生

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

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

x
10 分钟前结束的二面,感觉真是血崩的不能再血崩。。. 1point 3acres 璁哄潧

白人小哥,infrastructure组的,做storage的,感觉就要崩。。
就一题,给定一个array:[3,7,5]---unique, primes,
求所有的可能的乘积

一开始我说用类似subset的方法做,乘一个,放回数列里,再拿出来乘下一个,类似:. From 1point 3acres bbs
. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
        for(int i : S) {
            List<List<Integer>> tmp = new ArrayList<>();
. from: 1point3acres.com/bbs             for(List<Integer> sub : res) {
                List<Integer> a = new ArrayList<>(sub);
                a.add(i);. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
                tmp.add(a);
            }
            res.addAll(tmp);
        }.1point3acres缃

然后小哥说take too much memory,不让写代码,先优化一下。。然后,然后,
就开始血崩了。。完全不知道怎么优化
一开始说那我们直接brute force吧,memory占用还是一样的。。
然后就试各种办法试了半个小时。。. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
最后小哥说,你可以用bit map做,用不同的bit value表示不同的combination。。
表示完全没想到,然后问了几个问题就挂了,真是血崩的一天。。. from: 1point3acres.com/bbs


评分

1

查看全部评分

singledog2016 发表于 2016-3-11 11:27:44 | 显示全部楼层
public class Solution {-google 1point3acres
    public List<Integer> productsOfPrimes(int[] primes) {
        List<Integer> list = new ArrayList<>();
        if (nums == null || nums.length == 0) {
            return list;
        }. From 1point 3acres bbs
        Arrays.sort(primes);
        int n = nums.length;
        for (int i = 0; i < (1 << n); i++) {
            int product = 1;
            int mask = 1;
            for (int j = 0; j < n; j++) {
                if ((mask & i) != 0) {
                    product *= nums[j];
                }.鏈枃鍘熷垱鑷1point3acres璁哄潧
                mask <<= 1;
            }
            list.add(product);. Waral 鍗氬鏈夋洿澶氭枃绔,
        }
        return list;
    }
}

评分

1

查看全部评分

回复 支持 1 反对 0

使用道具 举报

xiaozhuxiaozhu 发表于 2016-3-11 10:17:42 | 显示全部楼层
用dfs不行么??
回复 支持 反对

使用道具 举报

 楼主| markieff 发表于 2016-3-11 10:24:15 | 显示全部楼层
xiaozhuxiaozhu 发表于 2016-3-11 10:17. 鍥磋鎴戜滑@1point 3 acres
用dfs不行么??

按他的说法不行,memory的开销太大了
回复 支持 反对

使用道具 举报

xiaozhuxiaozhu 发表于 2016-3-11 10:26:04 | 显示全部楼层
markieff 发表于 2016-3-11 10:24
按他的说法不行,memory的开销太大了

bit map怎么做啊?

补充内容 (2016-3-11 10:39):
我sb了。。leetcode原题
回复 支持 反对

使用道具 举报

 楼主| markieff 发表于 2016-3-11 10:31:54 | 显示全部楼层

比如你的array长度是4,你就用从1到15来表示所有的combination (2^n)
arr: 1,2,3,4. Waral 鍗氬鏈夋洿澶氭枃绔,
1: 0,0,0,1
2: 0,0,1,0
3: 0,0,1,1
...
这样下去,为1的位置表示take, 0表示not take,这样就能算出所有的乘积

评分

1

查看全部评分

回复 支持 反对

使用道具 举报

xiaozhuxiaozhu 发表于 2016-3-11 10:33:59 | 显示全部楼层
markieff 发表于 2016-3-11 10:31
比如你的array长度是4,你就用从1到15来表示所有的combination (2^n)
arr: 1,2,3,4
1: 0,0,0,1

你有代码么?同学
回复 支持 反对

使用道具 举报

xiaozhuxiaozhu 发表于 2016-3-11 10:35:08 | 显示全部楼层
markieff 发表于 2016-3-11 10:31
比如你的array长度是4,你就用从1到15来表示所有的combination (2^n)
arr: 1,2,3,4
1: 0,0,0,1

那你这题返回什么值呢?
回复 支持 反对

使用道具 举报

 楼主| markieff 发表于 2016-3-11 10:35:23 | 显示全部楼层
xiaozhuxiaozhu 发表于 2016-3-11 10:33. from: 1point3acres.com/bbs
你有代码么?同学

我没写,他最后马上要面试结束的时候和我说的。。
回复 支持 反对

使用道具 举报

xiaozhuxiaozhu 发表于 2016-3-11 10:36:41 | 显示全部楼层
markieff 发表于 2016-3-11 10:35
我没写,他最后马上要面试结束的时候和我说的。。
. more info on 1point3acres.com
这为什么 省空间啊
回复 支持 反对

使用道具 举报

singledog2016 发表于 2016-3-11 10:37:55 | 显示全部楼层
就是一个int bitmap, 从0到31位分别对应primes[] 中 第0到31个prime. 1表示选中,0表示不选。然后bitmap从0到max(全部为1)。 每一个数字,把set bits对应的数字乘起来。
关键有点麻烦是如果超过32个数,或者64 对long来说。就得用一个array of  int. 对吧?有啥更方便点的方法针对数字较多的情况?
回复 支持 反对

使用道具 举报

xiaozhuxiaozhu 发表于 2016-3-11 10:38:51 | 显示全部楼层
markieff 发表于 2016-3-11 10:35
我没写,他最后马上要面试结束的时候和我说的。。
. visit 1point3acres.com for more.
我煞笔了。。。。这题leetcode原题。。。
回复 支持 反对

使用道具 举报

 楼主| markieff 发表于 2016-3-11 10:38:58 | 显示全部楼层
. from: 1point3acres.com/bbs
对,省空间
回复 支持 反对

使用道具 举报

 楼主| markieff 发表于 2016-3-11 10:40:29 | 显示全部楼层
singledog2016 发表于 2016-3-11 10:37
就是一个int bitmap, 从0到31位分别对应primes[] 中 第0到31个prime. 1表示选中,0表示不选。然后bitmap从0 ...

对,是这个意思
额,我还没想过超了的话怎么办。。
回复 支持 反对

使用道具 举报

singledog2016 发表于 2016-3-11 11:34:45 | 显示全部楼层
其实不用sort, 这个是subset那题改的,忘了删那行。
回复 支持 反对

使用道具 举报

xiaozhuxiaozhu 发表于 2016-3-11 11:37:15 | 显示全部楼层
singledog2016 发表于 2016-3-11 11:34
其实不用sort, 这个是subset那题改的,忘了删那行。

对的,这题leetcode原题。。
lz说bit map, 我以为是那个int [256]的东西。。
后来才明白,他说的是bit minipulation
回复 支持 反对

使用道具 举报

xiaozhuxiaozhu 发表于 2016-3-11 12:08:59 | 显示全部楼层
singledog2016 发表于 2016-3-11 11:34.鏈枃鍘熷垱鑷1point3acres璁哄潧
其实不用sort, 这个是subset那题改的,忘了删那行。

代码会多加一个1 到结果里面。
回复 支持 反对

使用道具 举报

singledog2016 发表于 2016-3-11 13:36:08 | 显示全部楼层
xiaozhuxiaozhu 发表于 2016-3-11 12:08
代码会多加一个1 到结果里面。

那改成i = 1 : ... 就行了,这样没有空集了。
回复 支持 反对

使用道具 举报

primbo 发表于 2016-3-12 06:35:27 | 显示全部楼层
vector<int> primMutiply(vector<int> nums){
    vector<int> res;
    int len = nums.size();
    int n = 1<<len;
    for(int i = 1;i<n;i++){
        int mut = 1;
        for(int j =0;j<len,(i>>j)!=0;j++){
            if(((i>>j)&1) ==1) mut *=nums[j];. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
        }
        res.push_back(mut);
    }
    return res;
}
回复 支持 反对

使用道具 举报

Henry要工作 发表于 2016-3-13 00:27:53 | 显示全部楼层
xiaozhuxiaozhu 发表于 2016-3-11 10:26
bit map怎么做啊?

补充内容 (2016-3-11 10:39):

是哪一题??谢谢
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-5 21:22

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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