May 2009 - May 2017 论坛八周年-你的足迹,我的骄傲


一亩三分地论坛

 找回密码
 获取更多干活,快来注册

一亩三分地官方iOS手机应用下载
查看: 3425|回复: 27
收起左侧

Facebook intern二面血崩崩崩

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

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

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

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

x
10 分钟前结束的二面,感觉真是血崩的不能再血崩。。. visit 1point3acres.com for more.

白人小哥,infrastructure组的,做storage的,感觉就要崩。。. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
就一题,给定一个array:[3,7,5]---unique, primes,
求所有的可能的乘积

一开始我说用类似subset的方法做,乘一个,放回数列里,再拿出来乘下一个,类似:.鏈枃鍘熷垱鑷1point3acres璁哄潧

        for(int i : S) {
            List<List<Integer>> tmp = new ArrayList<>();
            for(List<Integer> sub : res) {
                List<Integer> a = new ArrayList<>(sub);
                a.add(i);. Waral 鍗氬鏈夋洿澶氭枃绔,
                tmp.add(a);
            }. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
            res.addAll(tmp);
        } 鏉ユ簮涓浜.涓夊垎鍦拌鍧.

然后小哥说take too much memory,不让写代码,先优化一下。。然后,然后,
就开始血崩了。。完全不知道怎么优化
一开始说那我们直接brute force吧,memory占用还是一样的。。
然后就试各种办法试了半个小时。。
最后小哥说,你可以用bit map做,用不同的bit value表示不同的combination。。
表示完全没想到,然后问了几个问题就挂了,真是血崩的一天。。


评分

1

查看全部评分

singledog2016 发表于 2016-3-11 11:27:44 | 显示全部楼层
关注一亩三分地公众号:
Warald_一亩三分地
public class Solution {. more info on 1point3acres.com
    public List<Integer> productsOfPrimes(int[] primes) {.鐣欏璁哄潧-涓浜-涓夊垎鍦
        List<Integer> list = new ArrayList<>();
.1point3acres缃        if (nums == null || nums.length == 0) {
            return list;
        }
        Arrays.sort(primes);. 1point3acres.com/bbs
        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];
                }
                mask <<= 1;
            }
            list.add(product);.鐣欏璁哄潧-涓浜-涓夊垎鍦
        }
        return list;-google 1point3acres
    }
}

评分

1

查看全部评分

回复 支持 1 反对 0

使用道具 举报

xiaozhuxiaozhu 发表于 2016-3-11 10:17:42 | 显示全部楼层
关注一亩三分地微博:
Warald
用dfs不行么??
回复 支持 反对

使用道具 举报

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

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

使用道具 举报

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

bit map怎么做啊?
. From 1point 3acres bbs
补充内容 (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
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. visit 1point3acres.com for more.
比如你的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:36:41 | 显示全部楼层
markieff 发表于 2016-3-11 10:35
我没写,他最后马上要面试结束的时候和我说的。。

这为什么 省空间啊
回复 支持 反对

使用道具 举报

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
我没写,他最后马上要面试结束的时候和我说的。。

我煞笔了。。。。这题leetcode原题。。。
回复 支持 反对

使用道具 举报

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

对,省空间
回复 支持 反对

使用道具 举报

 楼主| 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.鏈枃鍘熷垱鑷1point3acres璁哄潧
其实不用sort, 这个是subset那题改的,忘了删那行。

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

使用道具 举报

xiaozhuxiaozhu 发表于 2016-3-11 12:08:59 | 显示全部楼层
singledog2016 发表于 2016-3-11 11:34
其实不用sort, 这个是subset那题改的,忘了删那行。
. more info on 1point3acres.com
代码会多加一个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++){.1point3acres缃
        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;. visit 1point3acres.com for more.
}
回复 支持 反对

使用道具 举报

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

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

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

使用道具 举报

本版积分规则

关闭

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

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

custom counter

GMT+8, 2017-5-24 10:45

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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