一亩三分地论坛

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

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

Google fulltime 电面

[复制链接] |试试Instant~ |关注本帖
song4you 发表于 2016-2-25 08:38:00 | 显示全部楼层 |阅读模式

2016(1-3月) 码农类 本科 全职@Google - 猎头 - 技术电面 |Otherfresh grad应届毕业生

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

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

x
题目:
// Return sum of integer 1..N, excluding multipliers of any single integers in X.
// Example: N = 10, X = {2}, return 1 + 3 + 5 + 7 + 9 = 25.
// Example 2: N = 10, X = {2, 3}, return 1 + 5 + 7 = 13.
// Assume 1 < N <= 2^31. 1 <= K = X.size() <= 10. X contains only distinct positive prime numbers.

想不到有什么快的方法,先写了个解法O(kn)。 然后问可不可以improve,想好久才想到用等差数列求和公式。 太紧张了, 连公式都不记得,半天也推不出来。应该是跪了。。

本帖被以下淘专辑推荐:

  • · Google|主题: 54, 订阅: 45
echo33 发表于 2016-2-27 03:03:52 | 显示全部楼层
这是数学题啊。。。
就是totalsum - 有一个1prime的那些数的sum + 有两个primes的数的sum - 有3个primes的数的sum + 有4个primes 数的sum。。。。。。一直到k个primes的数

主要就是combination(k, i), i=1,..k
. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
啊,这题做电面太凶残了。。。。
回复 支持 2 反对 0

使用道具 举报

nole 发表于 2016-2-27 15:37:16 | 显示全部楼层
inclusion-exclusion principle
回复 支持 反对

使用道具 举报

hesha0987 发表于 2016-2-25 09:13:42 | 显示全部楼层
请问楼主的等差数列方法是什么? 是 (1+N)N/2 减去 集合里面的数以及他们的倍数 这个吗?
回复 支持 反对

使用道具 举报

 楼主| song4you 发表于 2016-2-25 11:53:01 | 显示全部楼层
hesha0987 发表于 2016-2-25 09:13
请问楼主的等差数列方法是什么? 是 (1+N)N/2 减去 集合里面的数以及他们的倍数 这个吗?

是的, 记得把重复减掉的数加回去就好了。重复的数就是集合里的数两两的乘积。最后还有一个tricky的地方就是要把集合里全部数一起的乘积减掉。这样出来的复杂度是O(2^k)。看起来没有更快, 但是他最后给的那个条件很关键。
这就是个数学题,复习了一堆算法反而被误导了。
回复 支持 反对

使用道具 举报

hesha0987 发表于 2016-2-25 12:20:32 | 显示全部楼层
song4you 发表于 2016-2-25 11:53
是的, 记得把重复减掉的数加回去就好了。重复的数就是集合里的数两两的乘积。最后还有一个tricky的地方 ...

请问为什么最后还要把集合里全部数一起的乘积减掉呢 在做第一次的减法(减去集合里的数的倍数的时候) 就已经能遇到一次 集合里的数相乘的情况了吧?

刚刚想到 可以先sort一下集合来跳过已经减去的数 代码如下:

. Waral 鍗氬鏈夋洿澶氭枃绔,    int res = (1 + N)*N/2;
    sort(X.begin(), X.end());
    for (int i = 0; i < X.size(); i++) {
        for (int j = 1; j*X <= N; j++) {
            if (i > 0 && j == X[i-1])   continue; // avoid nultiple substraction
            
            res -= X*j;
        }
    }
    return res;.鐣欏璁哄潧-涓浜-涓夊垎鍦
这样复杂度是nlogn 好像也蛮慢的。。。。TT
回复 支持 反对

使用道具 举报

hesha0987 发表于 2016-2-25 12:22:29 | 显示全部楼层
hesha0987 发表于 2016-2-25 12:20 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
请问为什么最后还要把集合里全部数一起的乘积减掉呢 在做第一次的减法(减去集合里的数的倍数的时候) 就 ...
. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
贴错代码了。。。是下面这个:. From 1point 3acres bbs
    int res = (1 + N)*N/2;-google 1point3acres
    sort(X.begin(), X.end());. Waral 鍗氬鏈夋洿澶氭枃绔,
    for (int i = 0; i < X.size(); i++) {
        for (int j = 1; j*X <= N; j++) {
            if (i > 0 && j == X[i-1])   continue; // avoid nultiple substraction
            
            res -= X*j;
        }
    }
    return res;
回复 支持 反对

使用道具 举报

 楼主| song4you 发表于 2016-2-25 13:23:36 | 显示全部楼层
hesha0987 发表于 2016-2-25 12:20.1point3acres缃
请问为什么最后还要把集合里全部数一起的乘积减掉呢 在做第一次的减法(减去集合里的数的倍数的时候) 就 ...

啊。是我解释错了。不是所有数一起的乘积。 应该是每种情况的乘积, 如果集合里有三个数, 那就是两两乘积,三三乘积。 如果有四个数, 那就还有四四乘积。 而且是加, 不是减。。sorry.
假设n>30. 2,3,5的乘积是30, 这个最开始的时候被减掉了三次。 要加回两次来。

你这个算法也是O(kn)吧,他的第三个条件是n可以达到2^31, x.size到10, worst case 是10*2^31。他的算法worst case是2^10
回复 支持 反对

使用道具 举报

duduhaha 发表于 2016-2-25 13:36:33 | 显示全部楼层
这题不简单啊。。
回复 支持 反对

使用道具 举报

stefan0428 发表于 2016-2-25 14:32:02 | 显示全部楼层
可不可以先求出总和 然后根据X 求出小于N的所有丑数, 然后在减掉
回复 支持 反对

使用道具 举报

hesha0987 发表于 2016-2-26 02:13:09 | 显示全部楼层
song4you 发表于 2016-2-25 13:23.鐣欏璁哄潧-涓浜-涓夊垎鍦
啊。是我解释错了。不是所有数一起的乘积。 应该是每种情况的乘积, 如果集合里有三个数, 那就是两两乘 ...

我目前想到的是:
要减去的部分是:集合里面每个数进行等比数列求和
最后要加上的部分是:集合里面的数进行组合求和 Ck2+Ck3+...+Ckk. (忽略格式)
但是依然无法证明这是o(2^k)
回复 支持 反对

使用道具 举报

zddllc 发表于 2016-2-26 04:35:59 | 显示全部楼层
感觉就是leetcode的 super ugly number.
求出小于n的super ugly number, 然后求和的时候不考虑这些ugly number就可以了
回复 支持 反对

使用道具 举报

 楼主| song4you 发表于 2016-2-26 06:05:15 | 显示全部楼层
hesha0987 发表于 2016-2-26 02:13
我目前想到的是:. Waral 鍗氬鏈夋洿澶氭枃绔,
要减去的部分是:集合里面每个数进行等比数列求和
最后要加上的部分是:集合里面的数 ...

你把他看成how many subsets in a set with k elements就是2^k了。准确的说是Θ((2^k)-k), 也就是O(2^k)

补充内容 (2016-2-26 06:41):
我可能描述得不好, 把你confused了。
. From 1point 3acres bbs
主要的步骤就是
1. 1...n求和 (sum)
2. 遍历x所有子集,空集和1个元素的子集除外
   2.1 求出每个子集的所有元素的product
   2.2 从sum里减掉该product和他的倍数
. Waral 鍗氬鏈夋洿澶氭枃绔,
补充内容 (2016-2-26 06:52):
=_=|| 步骤是错的。请忽略
回复 支持 反对

使用道具 举报

hesha0987 发表于 2016-2-26 07:25:12 | 显示全部楼层
song4you 发表于 2016-2-26 06:05. visit 1point3acres.com for more.
你把他看成how many subsets in a set with k elements就是2^k了。准确的说是Θ((2^k)-k), 也就是O(2^k)
...

楼主真聪明啊!顿悟了。。那我想的那个公式化简之后应该就是2^k吧。。。。 数学差真心塞。。
回复 支持 反对

使用道具 举报

ohuohuo 发表于 2016-2-26 07:49:02 | 显示全部楼层
song4you 发表于 2016-2-26 06:05
. 1point3acres.com/bbs你把他看成how many subsets in a set with k elements就是2^k了。准确的说是Θ((2^k)-k), 也就是O(2^k)
...

要除开只有一个元素的子集?那如果x={2,3}, 子集{2}就不算在里面了?也不对啊

补充内容 (2016-2-26 07:51):
子集{2},{3}都没有了,集合本身算不算子集呢?如{2,3}
回复 支持 反对

使用道具 举报

 楼主| song4you 发表于 2016-2-26 13:17:05 | 显示全部楼层
ohuohuo 发表于 2016-2-26 07:49. 鍥磋鎴戜滑@1point 3 acres
要除开只有一个元素的子集?那如果x={2,3}, 子集{2}就不算在里面了?也不对啊. 鍥磋鎴戜滑@1point 3 acres

补充内容 (2016-2-26 07:5 ...

恩啊。 算的。 除空集和单元素子集, 都算。 空集不用说了, 单元素子集是因为之前减掉了,所以不用继续考虑。
回复 支持 反对

使用道具 举报

 楼主| song4you 发表于 2016-2-26 13:24:42 | 显示全部楼层
hesha0987 发表于 2016-2-26 07:25. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
楼主真聪明啊!顿悟了。。那我想的那个公式化简之后应该就是2^k吧。。。。 数学差真心塞。。

我数学也好差。。我现在半天也还是推不出他给我的solution的general公式。 ╮(╯_╰)╭
回复 支持 反对

使用道具 举报

 楼主| song4you 发表于 2016-2-26 13:31:37 | 显示全部楼层
stefan0428 发表于 2016-2-25 14:32
可不可以先求出总和 然后根据X 求出小于N的所有丑数, 然后在减掉

丑数是只能被2,3,5整除吧。 x里可以是任意质数,7,11,13,17...都可以。 只减丑数的话会漏掉很多吧
回复 支持 反对

使用道具 举报

 楼主| song4you 发表于 2016-2-26 13:41:55 | 显示全部楼层
zddllc 发表于 2016-2-26 04:35. 1point3acres.com/bbs
感觉就是leetcode的 super ugly number.. visit 1point3acres.com for more.
求出小于n的super ugly number, 然后求和的时候不考虑这些ugly nu ...

我看了下leetcode上的解法,好像最快是O(n*lgk)? 在这题给的条件1 < N <= 2^31; 1 <= K = X.size() <= 10里, 当n>10,000; k>1 的时候,O(n*lgk)还是要比O(2^k)慢
回复 支持 反对

使用道具 举报

 楼主| song4you 发表于 2016-2-26 14:12:12 | 显示全部楼层
ohuohuo 发表于 2016-2-26 07:49
要除开只有一个元素的子集?那如果x={2,3}, 子集{2}就不算在里面了?也不对啊

补充内容 (2016-2-26 07:5 ...

他只给我推演了k=3的公式:

sum = n*(n+1)/2

Sum of prime multipliers:. more info on 1point3acres.com
primeSum1 = x[0] * (m*(m+1)/2) where m = n / x[0]
primeSum2 = x[1] * (m*(m+1)/2) where m = n / x[1]. 鍥磋鎴戜滑@1point 3 acres
primeSum3 = x[2] * (m*(m+1)/2) where m = n / x[2]
primeSum = primeSum1 + primeSum2+primeSum3
. 鍥磋鎴戜滑@1point 3 acres
sum of repeatedly removed Multipliers
p1 = x[0]*x[1] * (m*(m+1)/2) where m = n / p
p2 = x[0]*x[2] * (m*(m+1)/2) where m = n / p
p3 = x[1]*x[2] * (m*(m+1)/2) where m = n / p
p = p1 + p2 + p3   (exclude the one greater than n). visit 1point3acres.com for more.

commonMultiplier = (x[0]*x[1]*x[2])* (m*(m+1)/2) where m = n / commonMultiplier . Waral 鍗氬鏈夋洿澶氭枃绔,
.鐣欏璁哄潧-涓浜-涓夊垎鍦
Result:. From 1point 3acres bbs
sum = sum - primeSum + p - commonMultiplier . 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
-google 1point3acres
我也不知道为什么最后要减掉三个数的乘积, 但是这个公式在k=3的时候结果是对的。k>3的时候会有问题,这个公式应该有个general form。 不知道有没有大神能推出来。我推出来的公式只在k<6的时候正确。。o(╯□╰)o
回复 支持 反对

使用道具 举报

 楼主| song4you 发表于 2016-2-27 03:52:46 | 显示全部楼层
echo33 发表于 2016-2-27 03:03
这是数学题啊。。。
. visit 1point3acres.com for more.就是totalsum - 有一个1prime的那些数的sum + 有两个primes的数的sum - 有3个primes的 ...

我去。 膜拜大神!!我按你的公式写出来了! 我试了下worst case, 这个公式秒出答案, kn等了好几分钟。。我果然数学太渣了。。。
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-3 20:08

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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