一亩三分地论坛

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

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

FB电面

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

2016(10-12月) 码农类 硕士 全职@Facebook - 猎头 - 技术电面 |Passfresh grad应届毕业生

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

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

x
1.  leetcode 原题 move zeros  还要求证明算法的正确性。

2. /* product of prime

A = [2,3,5,7] primes
B = [1,2,1,3] numbers of primes
.鐣欏璁哄潧-涓浜-涓夊垎鍦
output: 1, 2, 3, 5, 6, 7, 9, 10, 12, 14,

评分

1

查看全部评分

iPhD 发表于 2016-10-14 11:32:21 | 显示全部楼层
第一题证明算法正确性什么意思?非0元素要保持原有顺序不变吗?. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷

第二题的B数组什么意思?
回复 支持 反对

使用道具 举报

 楼主| pineapple1985 发表于 2016-10-14 11:37:03 | 显示全部楼层
就是为什么你的算法就是正确的。
第二题的B数组的值指的是对应prime number可以相乘的最多次数。
回复 支持 反对

使用道具 举报

 楼主| pineapple1985 发表于 2016-10-14 11:39:31 | 显示全部楼层
第二题还要求用尽量少的空间。在输出的过程中,不能保存已经output的数
回复 支持 反对

使用道具 举报

iPhD 发表于 2016-10-14 11:41:25 | 显示全部楼层
pineapple1985 发表于 2016-10-14 11:39
第二题还要求用尽量少的空间。在输出的过程中,不能保存已经output的数

那第二题就是backtracking喽?
. Waral 鍗氬鏈夋洿澶氭枃绔,
第一题楼主什么方法做的?和LC那题一模一样还是有区别?
回复 支持 反对

使用道具 举报

 楼主| pineapple1985 发表于 2016-10-14 11:43:25 | 显示全部楼层
iPhD 发表于 2016-10-14 11:41
那第二题就是backtracking喽?

第一题楼主什么方法做的?和LC那题一模一样还是有区别?

第一题一模一样。
第二题backtracking是合理的。我用了递归。
回复 支持 反对

使用道具 举报

iPhD 发表于 2016-10-14 11:46:42 | 显示全部楼层
pineapple1985 发表于 2016-10-14 11:43
第一题一模一样。. 1point3acres.com/bbs
第二题backtracking是合理的。我用了递归。

楼主多久收到结果的呀?
回复 支持 反对

使用道具 举报

 楼主| pineapple1985 发表于 2016-10-14 11:51:46 | 显示全部楼层
iPhD 发表于 2016-10-14 11:46
楼主多久收到结果的呀?

面完几个小时后。
回复 支持 反对

使用道具 举报

celtspirit 发表于 2016-10-14 11:53:49 | 显示全部楼层
iPhD 发表于 2016-10-14 11:46
楼主多久收到结果的呀?

能否解释一下backtracking的做法啊。不是很懂那道题是什么意思。 为什么输出会出现1?不是A组数字之间想乘么?
回复 支持 反对

使用道具 举报

 楼主| pineapple1985 发表于 2016-10-14 11:57:05 | 显示全部楼层
1是第一个书。相当于1 = 2^0 * 3^0 * 5^0 * 7^0
回复 支持 反对

使用道具 举报

iPhD 发表于 2016-10-14 12:02:47 | 显示全部楼层
celtspirit 发表于 2016-10-14 11:53
能否解释一下backtracking的做法啊。不是很懂那道题是什么意思。 为什么输出会出现1?不是A组数字之间想 ...
. 1point 3acres 璁哄潧
public void primeProduct(int[] prime, int[] times) {
        if (prime.length == 0) {. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
                System.out.println(1);
                return;
        }. visit 1point3acres.com for more.

        backtrack(prime, times, 1);
}
.鏈枃鍘熷垱鑷1point3acres璁哄潧
private void backtrack(int[] prime, int[] times, int num) {
        for (int i = 0; i < times.length; i++) {
                if (times > 0) {
                        time--;. visit 1point3acres.com for more.
                        num *= prime;
                        System.out.println(num);
                        backtrack(prime, times, num);. more info on 1point3acres.com
                        num /= prime;
                        time++;
                }
        }. from: 1point3acres.com/bbs
}. 1point 3acres 璁哄潧


大家看下这样写对吗?

补充内容 (2016-10-14 12:03):
times ,怎么粘上去就不对了。。
回复 支持 反对

使用道具 举报

 楼主| pineapple1985 发表于 2016-10-14 12:14:58 | 显示全部楼层
iPhD 发表于 2016-10-14 12:02
public void primeProduct(int[] prime, int[] times) {
        if (prime.length == 0) {. Waral 鍗氬鏈夋洿澶氭枃绔,
                System.out.prin ...

如果B里面全是0, 你这个code好像没输出。但是输出应该是1。
另外time应该是times吧? 这个code会不会有重复打印? 我对java语法不熟...
回复 支持 反对

使用道具 举报

iPhD 发表于 2016-10-14 12:17:49 | 显示全部楼层
pineapple1985 发表于 2016-10-14 12:14
如果B里面全是0, 你这个code好像没输出。但是输出应该是1。
另外time应该是times吧? 这个code会不会有 ...

对,要提前打印一个1出来,我写的太急了。

一亩三分地的编辑器有问题,把我代码弄乱了,是times(i).
回复 支持 反对

使用道具 举报

iPhD 发表于 2016-10-14 12:18:24 | 显示全部楼层
pineapple1985 发表于 2016-10-14 12:14
如果B里面全是0, 你这个code好像没输出。但是输出应该是1。
另外time应该是times吧? 这个code会不会有 ...

质数想乘不会有重复结果的
回复 支持 反对

使用道具 举报

minggr 发表于 2016-10-14 12:44:47 | 显示全部楼层
输出没有要求是排好序的吧?

也来一个backtracking的
  1. void prime_product(vector<int> &res, int product, vector<int> &primes, vector<int> &nums, int i)
  2. {   . visit 1point3acres.com for more.
  3.     if (i == (int)primes.size()) {
  4.         res.push_back(product);
  5.         return;
  6.     }
  7.    
  8.     int p = 1;
  9.     for (int j = 0; j <= nums[i]; j++) {
  10.         prime_product(res, product * p, primes, nums, i+1);
  11.         p = p * primes[i];
  12.     }
  13. }

  14. int main(). 鍥磋鎴戜滑@1point 3 acres
  15. {
  16.     vector<int> res;
  17.     vector<int> primes = {2, 3, 5, 7};
  18.     vector<int> nums = {1, 2, 1, 3};

  19.     prime_product(res, 1, primes, nums, 0);

  20.     //Does the output need to be sorted?. 鍥磋鎴戜滑@1point 3 acres
  21.     //sort(res.begin(), res.end());

  22.     for (int i: res)
  23.         cout << i << " ";
  24.     cout << endl;

  25.     return 0;
  26. }
复制代码

补充内容 (2016-10-14 12:46):
别外,这个是不是prime应该无所谓吧,还是另有玄机?
回复 支持 反对

使用道具 举报

littlebearull 发表于 2016-10-14 12:45:23 | 显示全部楼层
iPhD 发表于 2016-10-14 12:18
质数想乘不会有重复结果的
. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
确实会有重复,需要加一个start index,下一次递归时,从i开始,而不是每次都从0开始。
回复 支持 反对

使用道具 举报

minggr 发表于 2016-10-14 12:49:30 | 显示全部楼层
minggr 发表于 2016-10-14 12:44
输出没有要求是排好序的吧?
.1point3acres缃
也来一个backtracking的

啊,了解了,prime才不会产生相同的product
回复 支持 反对

使用道具 举报

helloworld00 发表于 2016-10-14 21:38:43 | 显示全部楼层
第二个说实话没太看懂,  /* 第二题的B数组的值指的是对应prime number可以相乘的最多次数。 */ 如果b数组厘米对应的是prime number可以相乘的次数,是跟自己相乘吗?如果是,那output里的6是怎么来的?
回复 支持 反对

使用道具 举报

 楼主| pineapple1985 发表于 2016-10-14 22:51:30 来自手机 | 显示全部楼层
没排序要求,要求同一个数不能重复输出。空间复杂度要求O(n), n是数组 A, B的长度。所以要求primes都是不同的
回复 支持 反对

使用道具 举报

 楼主| pineapple1985 发表于 2016-10-14 22:53:07 来自手机 | 显示全部楼层
2^1 * 3^1 * 5^0 * 7^0 = 6
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-8 06:54

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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