m*******0 发帖数: 38 | 1 对方是个老外,上来问research,我说了一通,他说信号不好重新打过来,然后接着说
,貌似他没怎么听懂,最后他说let's move on to the technical part.
然后给了一道题,叫找出所有小于N的Taxicab number,即所有符合以下条件的数n:
n = a^3 + b^3 = c^3 + d^3 (满足两组数(a, b), (c, d)使他们的立方和等于n)。
这题目没见过,想了一下就给了一个straighforward的方法,顺序遍历1到n^{1/3},找
出所有符合条件的组合,可以得到效率O(n^{5/3})。难道还有更好地解法么?
最后他说very good,然后叫我问问题,问了几个就挂了(怀疑是不是这里也有问题,
我说如果能通过的话是不是可以自己选地方?现在想想八字都没一瞥是不是不应该问这
个)。
另外不知道是不是我速度太慢了,但我觉得中间单独想的过程也就一两分钟,然后
coding也很快写完了,但看总时间貌似过的挺快,三四十分钟左右,不确定时间浪费在
哪了。
有谁知道应该是什么原因么? |
s********u 发帖数: 1109 | 2 一般应该是问两道题。我这次二面也是一个题不清楚题意弄了很久,导
致他后面直接问简历,估计是挂了。 |
m*******0 发帖数: 38 | 3 好吧,这个竟然没想到。。。
他有问我能不能improve,我说想不到了,他也没继续问了。。
【在 s********u 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 一般应该是问两道题。我这次二面也是一个题不清楚题意弄了很久,导 : 致他后面直接问简历,估计是挂了。
|
s********u 发帖数: 1109 | 4 看错题,修改掉。
【在 m*******0 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 好吧,这个竟然没想到。。。 : 他有问我能不能improve,我说想不到了,他也没继续问了。。
|
m*******0 发帖数: 38 | 5 又想了一下总时间应该是O(N^{4/3} + NlogN)吧,要对每个n从1~N来验证,每个n验证
的时间是n^{1/3},加上排序总时间就是N^{4/3} + NlogN ?
【在 s********u 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 看错题,修改掉。
|
s********u 发帖数: 1109 | 6 看错题,修改掉。
【在 m*******0 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 又想了一下总时间应该是O(N^{4/3} + NlogN)吧,要对每个n从1~N来验证,每个n验证 : 的时间是n^{1/3},加上排序总时间就是N^{4/3} + NlogN ?
|
m*******0 发帖数: 38 | 7 弱问为什么平方跟三次方不一样? 我也可以使i从1到N遍历找另一个j使i^2 + j^2 = N
的吧?
【在 s********u 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 看错题,修改掉。
|
s********u 发帖数: 1109 | 8 看错题,修改掉。
N
【在 m*******0 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 弱问为什么平方跟三次方不一样? 我也可以使i从1到N遍历找另一个j使i^2 + j^2 = N : 的吧?
|
m*******0 发帖数: 38 | 9 你这个只能得到立方和等于N的数的个数吧?不过他是要找出所有小于N的数n满足存在
两组数(a, b)和(c, d)使他们立方和等于n。所以貌似要把1~N的所有数都check一遍吧?
【在 s********u 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 看错题,修改掉。 : : N
|
s*****r 发帖数: 108 | |
|
|
s********u 发帖数: 1109 | 11 额。。我发现我理解错了
因为你说满足两组数(a, b), (c, d)使他们的立方和等于n
我还以为给一个n,然后让我找所有立方和等于n的。。。
吧?
【在 m*******0 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 你这个只能得到立方和等于N的数的个数吧?不过他是要找出所有小于N的数n满足存在 : 两组数(a, b)和(c, d)使他们立方和等于n。所以貌似要把1~N的所有数都check一遍吧?
|
m*******0 发帖数: 38 | 12 不是很懂你的意思,里面不会涉及到负数的吧,他是要找出从1~N的数中满足存在两组
不同的数是他们的立方和等于要找的那个数。貌似和2sum有点不一样,就是我们要对所
有1~N都测试一遍?
【在 s********u 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 额。。我发现我理解错了 : 因为你说满足两组数(a, b), (c, d)使他们的立方和等于n : 我还以为给一个n,然后让我找所有立方和等于n的。。。 : : 吧?
|
m*******0 发帖数: 38 | 13 对的,做完这题他说时间到了,发现时间过的真快,写代码的时间也就几分钟,不知不
觉就过去了。。。
【在 s*****r 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 就做了一题?
|
m*******0 发帖数: 38 | 14 这样的话我发现还是要O(N^{4/3})的时间的吧,就是对每个n从1到N,用hash的方法验
证是不是有两组数符合条件,这个需要O(n^{1/3}),所以加起来是sum_{n=1}^N n^{1/3
},应该差不多是O(N^{4/3})吧?
【在 s********u 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 额。。我发现我理解错了 : 因为你说满足两组数(a, b), (c, d)使他们的立方和等于n : 我还以为给一个n,然后让我找所有立方和等于n的。。。 : : 吧?
|
s*****r 发帖数: 108 | 15 用暴力只做一题肯定挂 你是说用了四个循环?
不是只枚举一次 0 ~ n^(1/3) 就能找到所有 (a, b) ?
【在 m*******0 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 对的,做完这题他说时间到了,发现时间过的真快,写代码的时间也就几分钟,不知不 : 觉就过去了。。。
|
s********u 发帖数: 1109 | 16 我想了下,至少有O(n^2/3)的方法。就是类似那个求n以内质数那个方法。你开一个0~n
的数组,全部置为0。然后在0~n^1/3之间,对任意一对数,比如i和j,求他们的立方和
k。这时候array[k]++;如果array[k] = 2,那么记录这个k
其实这个题目跟求n以内质数非常接近。你的那个暴力做法,就是从0出发到n,看每个
数是不是质数。但另一种思路就是sieveofErathenese,就是说考虑因子,然后一遍遍
地反过来覆盖。很多时候如果时间效率太差,通常就是用space cost来换。 |
m*******0 发帖数: 38 | 17 对每个n,只需要两层循环枚举i = 1:n^{1/3},j = 1:n^{1/3}就可以了吧,总时间是O
(n^{2/3})。然后加上枚举每个n,总时间就是O(N^{5/3})了啊。
【在 s*****r 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 用暴力只做一题肯定挂 你是说用了四个循环? : 不是只枚举一次 0 ~ n^(1/3) 就能找到所有 (a, b) ?
|
s*****r 发帖数: 108 | 18 只需一层循环枚举
是O
【在 m*******0 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 对每个n,只需要两层循环枚举i = 1:n^{1/3},j = 1:n^{1/3}就可以了吧,总时间是O : (n^{2/3})。然后加上枚举每个n,总时间就是O(N^{5/3})了啊。
|
m*******0 发帖数: 38 | 19 我觉得应该是这样解的,当时外面又套了一个循环,这个没必要,那时候时间太紧,没
想到。。
~n
【在 s********u 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 我想了下,至少有O(n^2/3)的方法。就是类似那个求n以内质数那个方法。你开一个0~n : 的数组,全部置为0。然后在0~n^1/3之间,对任意一对数,比如i和j,求他们的立方和 : k。这时候array[k]++;如果array[k] = 2,那么记录这个k : 其实这个题目跟求n以内质数非常接近。你的那个暴力做法,就是从0出发到n,看每个 : 数是不是质数。但另一种思路就是sieveofErathenese,就是说考虑因子,然后一遍遍 : 地反过来覆盖。很多时候如果时间效率太差,通常就是用space cost来换。
|
s*****r 发帖数: 108 | 20 主要就是做慢了 复杂度分析也不对
边界比如 0,N 有多大等
还有题意可能也没有问清楚 我就很想问他是不是要多次询问 N
根据定义这种数的个数增长应该非常缓慢 可能 N 非常大就几个满足要求的, N1 <<
N2,之内的 taxicab number 却没什么差别
各种原因都导致了挂 |
|
|
s********u 发帖数: 1109 | 21 主要还是没有improve吧,lz的暴力法是O(n^4/3),优化方法是O(n^2/3),这个差的还
挺多的。。
【在 s*****r 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 主要就是做慢了 复杂度分析也不对 : 边界比如 0,N 有多大等 : 还有题意可能也没有问清楚 我就很想问他是不是要多次询问 N : 根据定义这种数的个数增长应该非常缓慢 可能 N 非常大就几个满足要求的, N1 << : N2,之内的 taxicab number 却没什么差别 : 各种原因都导致了挂
|
m*******0 发帖数: 38 | 22 复杂度他同意了,说是对的。然后N有多大跟这道题的解法没什么关系吧?我觉得中间
扯谈的时间估计多了点,一眨眼就时间过了,总共时间就30分钟左右.
【在 s*****r 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 主要就是做慢了 复杂度分析也不对 : 边界比如 0,N 有多大等 : 还有题意可能也没有问清楚 我就很想问他是不是要多次询问 N : 根据定义这种数的个数增长应该非常缓慢 可能 N 非常大就几个满足要求的, N1 << : N2,之内的 taxicab number 却没什么差别 : 各种原因都导致了挂
|
s*****r 发帖数: 108 | 23 我想主要得问清对方要求,比如是否要多次询问
在解的个数增长十分缓慢的情况下 这个优化太费空间 理论上的讨论倒是可以展现些分
析能力
所以我觉得应该先问清楚,然后小数据测试增长速度,再问它喜欢时间还是空间,增长
速度太慢肯定不会用空间换时间
小数据就随便暴力,大数据就暴力预处理+打表
【在 s********u 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 主要还是没有improve吧,lz的暴力法是O(n^4/3),优化方法是O(n^2/3),这个差的还 : 挺多的。。
|
s*****r 发帖数: 108 | 24 和 N 是有关系的,为什么还是和解的增长速度有关,决定了空间换时间还是时间换空间
比如 N = 1e10 和 N = 1e19 之间就差几个解,再大直到超出整型表示范围都没有更多
解呢?
【在 m*******0 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 复杂度他同意了,说是对的。然后N有多大跟这道题的解法没什么关系吧?我觉得中间 : 扯谈的时间估计多了点,一眨眼就时间过了,总共时间就30分钟左右.
|
s********u 发帖数: 1109 | 25 如果觉得稀疏,还是可以打表,用hashtable就行了。
【在 s*****r 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 我想主要得问清对方要求,比如是否要多次询问 : 在解的个数增长十分缓慢的情况下 这个优化太费空间 理论上的讨论倒是可以展现些分 : 析能力 : 所以我觉得应该先问清楚,然后小数据测试增长速度,再问它喜欢时间还是空间,增长 : 速度太慢肯定不会用空间换时间 : 小数据就随便暴力,大数据就暴力预处理+打表
|
s*****r 发帖数: 108 | 26 搜了下这数不叫 taxicab number...面试官好坑... |
s******y 发帖数: 416 | 27 你taxicab number定义没用对
【在 m*******0 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 对方是个老外,上来问research,我说了一通,他说信号不好重新打过来,然后接着说 : ,貌似他没怎么听懂,最后他说let's move on to the technical part. : 然后给了一道题,叫找出所有小于N的Taxicab number,即所有符合以下条件的数n: : n = a^3 + b^3 = c^3 + d^3 (满足两组数(a, b), (c, d)使他们的立方和等于n)。 : 这题目没见过,想了一下就给了一个straighforward的方法,顺序遍历1到n^{1/3},找 : 出所有符合条件的组合,可以得到效率O(n^{5/3})。难道还有更好地解法么? : 最后他说very good,然后叫我问问题,问了几个就挂了(怀疑是不是这里也有问题, : 我说如果能通过的话是不是可以自己选地方?现在想想八字都没一瞥是不是不应该问这 : 个)。 : 另外不知道是不是我速度太慢了,但我觉得中间单独想的过程也就一两分钟,然后
|
z***e 发帖数: 58 | 28 小弟的代码, 复杂度O(n)
void taxiCub(int n)
{
int limit = n;
n =(int)pow(n,(double)1/(double)3)+1;
vector remark = vector(n+1,0);
vector used = vector(2*n*n*n+1,false);
for(int i = 0 ;i < n+1; i++)
{
remark[i] = i*i*i;
}
for(int i = 1 ; i <= n-1;i++)
{
for(int j = i+1;j <= n;j++)
{
int start = i+1;
int end = j-1;
if(start < end)
{
int sum = remark[i] + remark[j];
if(sum > limit) continue;
if(used[sum] == true) continue;
else used[sum] = true;
while(start < end)
{
if(remark[start] + remark[end] < sum)
{
start++;
}
else if(remark[start] + remark[end] > sum)
{
end--;
}
else
{
cout<
start++;
end--;
}
}
}
}
}
} |
s***e 发帖数: 403 | 29 我也不太懂
我当时电面G的时候
先是问了个SQL问题。我简历上SQL的经历是真的,可惜那是7年前被逼着做班级网站的
事情了。所以没答对……
然后是coding,写了一遍之后他要求优化。我就优化了一遍。
然后居然拿到onsite了,不过我已经签了一封offer,就客气的回绝了。
【在 m*******0 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 对方是个老外,上来问research,我说了一通,他说信号不好重新打过来,然后接着说 : ,貌似他没怎么听懂,最后他说let's move on to the technical part. : 然后给了一道题,叫找出所有小于N的Taxicab number,即所有符合以下条件的数n: : n = a^3 + b^3 = c^3 + d^3 (满足两组数(a, b), (c, d)使他们的立方和等于n)。 : 这题目没见过,想了一下就给了一个straighforward的方法,顺序遍历1到n^{1/3},找 : 出所有符合条件的组合,可以得到效率O(n^{5/3})。难道还有更好地解法么? : 最后他说very good,然后叫我问问题,问了几个就挂了(怀疑是不是这里也有问题, : 我说如果能通过的话是不是可以自己选地方?现在想想八字都没一瞥是不是不应该问这 : 个)。 : 另外不知道是不是我速度太慢了,但我觉得中间单独想的过程也就一两分钟,然后
|
f*****2 发帖数: 14 | 30 我今年四五月份面二面的时候也是这道题,当时我给面试官的也是O(n^2/3)的解法,
最后悲剧了,后来问recruiter feedback,说题是解出来了,就是反应太慢了,综合一
面的结果(我一面面的不好,一道初中数学题没答上来)把我拒了.
所以我觉得O(n^2/3)应该是面试官希望得到的答案 |
|
|
c***0 发帖数: 449 | 31 是4-sum的变种吗? 4-sum最小O(n^2), 因为只需要便利1-n^(1/3), 所以这道题O(n^2/
3) |
f*o 发帖数: 654 | 32 你这个是O(n)?
嘿嘿
【在 z***e 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 小弟的代码, 复杂度O(n) : void taxiCub(int n) : { : int limit = n; : n =(int)pow(n,(double)1/(double)3)+1; : vector remark = vector(n+1,0); : vector used = vector(2*n*n*n+1,false); : for(int i = 0 ;i < n+1; i++) : { : remark[i] = i*i*i;
|
n****e 发帖数: 678 | 33 我也是这么想的
n = N^(1/3)
复杂度O(n^3) = O(N)
【在 z***e 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 小弟的代码, 复杂度O(n) : void taxiCub(int n) : { : int limit = n; : n =(int)pow(n,(double)1/(double)3)+1; : vector remark = vector(n+1,0); : vector used = vector(2*n*n*n+1,false); : for(int i = 0 ;i < n+1; i++) : { : remark[i] = i*i*i;
|
n****e 发帖数: 678 | 34 他的算法是对的,
复杂度是O(N)
【在 f*o 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 你这个是O(n)? : 嘿嘿
|
n****e 发帖数: 678 | 35 恩,这个想法好。
~n
【在 s********u 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 我想了下,至少有O(n^2/3)的方法。就是类似那个求n以内质数那个方法。你开一个0~n : 的数组,全部置为0。然后在0~n^1/3之间,对任意一对数,比如i和j,求他们的立方和 : k。这时候array[k]++;如果array[k] = 2,那么记录这个k : 其实这个题目跟求n以内质数非常接近。你的那个暴力做法,就是从0出发到n,看每个 : 数是不是质数。但另一种思路就是sieveofErathenese,就是说考虑因子,然后一遍遍 : 地反过来覆盖。很多时候如果时间效率太差,通常就是用space cost来换。
|
m*******0 发帖数: 38 | 36 对方是个老外,上来问research,我说了一通,他说信号不好重新打过来,然后接着说
,貌似他没怎么听懂,最后他说let's move on to the technical part.
然后给了一道题,叫找出所有小于N的Taxicab number,即所有符合以下条件的数n:
n = a^3 + b^3 = c^3 + d^3 (满足两组数(a, b), (c, d)使他们的立方和等于n)。
这题目没见过,想了一下就给了一个straighforward的方法,顺序遍历1到n^{1/3},找
出所有符合条件的组合,可以得到效率O(n^{5/3})。难道还有更好地解法么?
最后他说very good,然后叫我问问题,问了几个就挂了(怀疑是不是这里也有问题,
我说如果能通过的话是不是可以自己选地方?现在想想八字都没一瞥是不是不应该问这
个)。
另外不知道是不是我速度太慢了,但我觉得中间单独想的过程也就一两分钟,然后
coding也很快写完了,但看总时间貌似过的挺快,三四十分钟左右,不确定时间浪费在
哪了。
有谁知道应该是什么原因么? |
s********u 发帖数: 1109 | 37 一般应该是问两道题。我这次二面也是一个题不清楚题意弄了很久,导
致他后面直接问简历,估计是挂了。 |
m*******0 发帖数: 38 | 38 好吧,这个竟然没想到。。。
他有问我能不能improve,我说想不到了,他也没继续问了。。
【在 s********u 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 一般应该是问两道题。我这次二面也是一个题不清楚题意弄了很久,导 : 致他后面直接问简历,估计是挂了。
|
m*******0 发帖数: 38 | 39 又想了一下总时间应该是O(N^{4/3} + NlogN)吧,要对每个n从1~N来验证,每个n验证
的时间是n^{1/3},加上排序总时间就是N^{4/3} + NlogN ?
【在 s********u 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 一般应该是问两道题。我这次二面也是一个题不清楚题意弄了很久,导 : 致他后面直接问简历,估计是挂了。
|
m*******0 发帖数: 38 | 40 弱问为什么平方跟三次方不一样? 我也可以使i从1到N遍历找另一个j使i^2 + j^2 = N
的吧?
【在 s********u 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 一般应该是问两道题。我这次二面也是一个题不清楚题意弄了很久,导 : 致他后面直接问简历,估计是挂了。
|
|
|
s********u 发帖数: 1109 | 41 看错题,修改掉。
N
【在 m*******0 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 弱问为什么平方跟三次方不一样? 我也可以使i从1到N遍历找另一个j使i^2 + j^2 = N : 的吧?
|
m*******0 发帖数: 38 | 42 你这个只能得到立方和等于N的数的个数吧?不过他是要找出所有小于N的数n满足存在
两组数(a, b)和(c, d)使他们立方和等于n。所以貌似要把1~N的所有数都check一遍吧?
【在 s********u 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 看错题,修改掉。 : : N
|
s*****r 发帖数: 108 | |
s********u 发帖数: 1109 | 44 额。。我发现我理解错了
因为你说满足两组数(a, b), (c, d)使他们的立方和等于n
我还以为给一个n,然后让我找所有立方和等于n的。。。
吧?
【在 m*******0 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 你这个只能得到立方和等于N的数的个数吧?不过他是要找出所有小于N的数n满足存在 : 两组数(a, b)和(c, d)使他们立方和等于n。所以貌似要把1~N的所有数都check一遍吧?
|
m*******0 发帖数: 38 | 45 不是很懂你的意思,里面不会涉及到负数的吧,他是要找出从1~N的数中满足存在两组
不同的数是他们的立方和等于要找的那个数。貌似和2sum有点不一样,就是我们要对所
有1~N都测试一遍?
【在 s********u 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 额。。我发现我理解错了 : 因为你说满足两组数(a, b), (c, d)使他们的立方和等于n : 我还以为给一个n,然后让我找所有立方和等于n的。。。 : : 吧?
|
m*******0 发帖数: 38 | 46 对的,做完这题他说时间到了,发现时间过的真快,写代码的时间也就几分钟,不知不
觉就过去了。。。
【在 s*****r 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 就做了一题?
|
m*******0 发帖数: 38 | 47 这样的话我发现还是要O(N^{4/3})的时间的吧,就是对每个n从1到N,用hash的方法验
证是不是有两组数符合条件,这个需要O(n^{1/3}),所以加起来是sum_{n=1}^N n^{1/3
},应该差不多是O(N^{4/3})吧?
【在 s********u 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 额。。我发现我理解错了 : 因为你说满足两组数(a, b), (c, d)使他们的立方和等于n : 我还以为给一个n,然后让我找所有立方和等于n的。。。 : : 吧?
|
s*****r 发帖数: 108 | 48 用暴力只做一题肯定挂 你是说用了四个循环?
不是只枚举一次 0 ~ n^(1/3) 就能找到所有 (a, b) ?
【在 m*******0 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 对的,做完这题他说时间到了,发现时间过的真快,写代码的时间也就几分钟,不知不 : 觉就过去了。。。
|
s********u 发帖数: 1109 | 49 我想了下,至少有O(n^2/3)的方法。就是类似那个求n以内质数那个方法。你开一个0~n
的数组,全部置为0。然后在0~n^1/3之间,对任意一对数,比如i和j,求他们的立方和
k。这时候array[k]++;如果array[k] = 2,那么记录这个k
其实这个题目跟求n以内质数非常接近。你的那个暴力做法,就是从0出发到n,看每个
数是不是质数。但另一种思路就是sieveofErathenese,就是说考虑因子,然后一遍遍
地反过来覆盖。很多时候如果时间效率太差,通常就是用space cost来换。 |
m*******0 发帖数: 38 | 50 对每个n,只需要两层循环枚举i = 1:n^{1/3},j = 1:n^{1/3}就可以了吧,总时间是O
(n^{2/3})。然后加上枚举每个n,总时间就是O(N^{5/3})了啊。
【在 s*****r 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 用暴力只做一题肯定挂 你是说用了四个循环? : 不是只枚举一次 0 ~ n^(1/3) 就能找到所有 (a, b) ?
|
|
|
s*****r 发帖数: 108 | 51 只需一层循环枚举
是O
【在 m*******0 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 对每个n,只需要两层循环枚举i = 1:n^{1/3},j = 1:n^{1/3}就可以了吧,总时间是O : (n^{2/3})。然后加上枚举每个n,总时间就是O(N^{5/3})了啊。
|
m*******0 发帖数: 38 | 52 我觉得应该是这样解的,当时外面又套了一个循环,这个没必要,那时候时间太紧,没
想到。。
~n
【在 s********u 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 我想了下,至少有O(n^2/3)的方法。就是类似那个求n以内质数那个方法。你开一个0~n : 的数组,全部置为0。然后在0~n^1/3之间,对任意一对数,比如i和j,求他们的立方和 : k。这时候array[k]++;如果array[k] = 2,那么记录这个k : 其实这个题目跟求n以内质数非常接近。你的那个暴力做法,就是从0出发到n,看每个 : 数是不是质数。但另一种思路就是sieveofErathenese,就是说考虑因子,然后一遍遍 : 地反过来覆盖。很多时候如果时间效率太差,通常就是用space cost来换。
|
s*****r 发帖数: 108 | 53 主要就是做慢了 复杂度分析也不对
边界比如 0,N 有多大等
还有题意可能也没有问清楚 我就很想问他是不是要多次询问 N
根据定义这种数的个数增长应该非常缓慢 可能 N 非常大就几个满足要求的, N1 <<
N2,之内的 taxicab number 却没什么差别
各种原因都导致了挂 |
s********u 发帖数: 1109 | 54 主要还是没有improve吧,lz的暴力法是O(n^4/3),优化方法是O(n^2/3),这个差的还
挺多的。。
【在 s*****r 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 主要就是做慢了 复杂度分析也不对 : 边界比如 0,N 有多大等 : 还有题意可能也没有问清楚 我就很想问他是不是要多次询问 N : 根据定义这种数的个数增长应该非常缓慢 可能 N 非常大就几个满足要求的, N1 << : N2,之内的 taxicab number 却没什么差别 : 各种原因都导致了挂
|
m*******0 发帖数: 38 | 55 复杂度他同意了,说是对的。然后N有多大跟这道题的解法没什么关系吧?我觉得中间
扯谈的时间估计多了点,一眨眼就时间过了,总共时间就30分钟左右.
【在 s*****r 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 主要就是做慢了 复杂度分析也不对 : 边界比如 0,N 有多大等 : 还有题意可能也没有问清楚 我就很想问他是不是要多次询问 N : 根据定义这种数的个数增长应该非常缓慢 可能 N 非常大就几个满足要求的, N1 << : N2,之内的 taxicab number 却没什么差别 : 各种原因都导致了挂
|
s*****r 发帖数: 108 | 56 我想主要得问清对方要求,比如是否要多次询问
在解的个数增长十分缓慢的情况下 这个优化太费空间 理论上的讨论倒是可以展现些分
析能力
所以我觉得应该先问清楚,然后小数据测试增长速度,再问它喜欢时间还是空间,增长
速度太慢肯定不会用空间换时间
小数据就随便暴力,大数据就暴力预处理+打表
【在 s********u 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 主要还是没有improve吧,lz的暴力法是O(n^4/3),优化方法是O(n^2/3),这个差的还 : 挺多的。。
|
s*****r 发帖数: 108 | 57 和 N 是有关系的,为什么还是和解的增长速度有关,决定了空间换时间还是时间换空间
比如 N = 1e10 和 N = 1e19 之间就差几个解,再大直到超出整型表示范围都没有更多
解呢?
【在 m*******0 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 复杂度他同意了,说是对的。然后N有多大跟这道题的解法没什么关系吧?我觉得中间 : 扯谈的时间估计多了点,一眨眼就时间过了,总共时间就30分钟左右.
|
s********u 发帖数: 1109 | 58 如果觉得稀疏,还是可以打表,用hashtable就行了。
【在 s*****r 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 我想主要得问清对方要求,比如是否要多次询问 : 在解的个数增长十分缓慢的情况下 这个优化太费空间 理论上的讨论倒是可以展现些分 : 析能力 : 所以我觉得应该先问清楚,然后小数据测试增长速度,再问它喜欢时间还是空间,增长 : 速度太慢肯定不会用空间换时间 : 小数据就随便暴力,大数据就暴力预处理+打表
|
s*****r 发帖数: 108 | 59 搜了下这数不叫 taxicab number...面试官好坑... |
s******y 发帖数: 416 | 60 你taxicab number定义没用对
【在 m*******0 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 对方是个老外,上来问research,我说了一通,他说信号不好重新打过来,然后接着说 : ,貌似他没怎么听懂,最后他说let's move on to the technical part. : 然后给了一道题,叫找出所有小于N的Taxicab number,即所有符合以下条件的数n: : n = a^3 + b^3 = c^3 + d^3 (满足两组数(a, b), (c, d)使他们的立方和等于n)。 : 这题目没见过,想了一下就给了一个straighforward的方法,顺序遍历1到n^{1/3},找 : 出所有符合条件的组合,可以得到效率O(n^{5/3})。难道还有更好地解法么? : 最后他说very good,然后叫我问问题,问了几个就挂了(怀疑是不是这里也有问题, : 我说如果能通过的话是不是可以自己选地方?现在想想八字都没一瞥是不是不应该问这 : 个)。 : 另外不知道是不是我速度太慢了,但我觉得中间单独想的过程也就一两分钟,然后
|
|
|
z***e 发帖数: 58 | 61 小弟的代码, 复杂度O(n)
void taxiCub(int n)
{
int limit = n;
n =(int)pow(n,(double)1/(double)3)+1;
vector remark = vector(n+1,0);
vector used = vector(2*n*n*n+1,false);
for(int i = 0 ;i < n+1; i++)
{
remark[i] = i*i*i;
}
for(int i = 1 ; i <= n-1;i++)
{
for(int j = i+1;j <= n;j++)
{
int start = i+1;
int end = j-1;
if(start < end)
{
int sum = remark[i] + remark[j];
if(sum > limit) continue;
if(used[sum] == true) continue;
else used[sum] = true;
while(start < end)
{
if(remark[start] + remark[end] < sum)
{
start++;
}
else if(remark[start] + remark[end] > sum)
{
end--;
}
else
{
cout<
start++;
end--;
}
}
}
}
}
} |
s***e 发帖数: 403 | 62 我也不太懂
我当时电面G的时候
先是问了个SQL问题。我简历上SQL的经历是真的,可惜那是7年前被逼着做班级网站的
事情了。所以没答对……
然后是coding,写了一遍之后他要求优化。我就优化了一遍。
然后居然拿到onsite了,不过我已经签了一封offer,就客气的回绝了。
【在 m*******0 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 对方是个老外,上来问research,我说了一通,他说信号不好重新打过来,然后接着说 : ,貌似他没怎么听懂,最后他说let's move on to the technical part. : 然后给了一道题,叫找出所有小于N的Taxicab number,即所有符合以下条件的数n: : n = a^3 + b^3 = c^3 + d^3 (满足两组数(a, b), (c, d)使他们的立方和等于n)。 : 这题目没见过,想了一下就给了一个straighforward的方法,顺序遍历1到n^{1/3},找 : 出所有符合条件的组合,可以得到效率O(n^{5/3})。难道还有更好地解法么? : 最后他说very good,然后叫我问问题,问了几个就挂了(怀疑是不是这里也有问题, : 我说如果能通过的话是不是可以自己选地方?现在想想八字都没一瞥是不是不应该问这 : 个)。 : 另外不知道是不是我速度太慢了,但我觉得中间单独想的过程也就一两分钟,然后
|
f*****2 发帖数: 14 | 63 我今年四五月份面二面的时候也是这道题,当时我给面试官的也是O(n^2/3)的解法,
最后悲剧了,后来问recruiter feedback,说题是解出来了,就是反应太慢了,综合一
面的结果(我一面面的不好,一道初中数学题没答上来)把我拒了.
所以我觉得O(n^2/3)应该是面试官希望得到的答案 |
c***0 发帖数: 449 | 64 是4-sum的变种吗? 4-sum最小O(n^2), 因为只需要便利1-n^(1/3), 所以这道题O(n^2/
3) |
f*o 发帖数: 654 | 65 你这个是O(n)?
嘿嘿
【在 z***e 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 小弟的代码, 复杂度O(n) : void taxiCub(int n) : { : int limit = n; : n =(int)pow(n,(double)1/(double)3)+1; : vector remark = vector(n+1,0); : vector used = vector(2*n*n*n+1,false); : for(int i = 0 ;i < n+1; i++) : { : remark[i] = i*i*i;
|
n****e 发帖数: 678 | 66 我也是这么想的
n = N^(1/3)
复杂度O(n^3) = O(N)
【在 z***e 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 小弟的代码, 复杂度O(n) : void taxiCub(int n) : { : int limit = n; : n =(int)pow(n,(double)1/(double)3)+1; : vector remark = vector(n+1,0); : vector used = vector(2*n*n*n+1,false); : for(int i = 0 ;i < n+1; i++) : { : remark[i] = i*i*i;
|
n****e 发帖数: 678 | 67 他的算法是对的,
复杂度是O(N)
【在 f*o 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 你这个是O(n)? : 嘿嘿
|
n****e 发帖数: 678 | 68 恩,这个想法好。
~n
【在 s********u 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 我想了下,至少有O(n^2/3)的方法。就是类似那个求n以内质数那个方法。你开一个0~n : 的数组,全部置为0。然后在0~n^1/3之间,对任意一对数,比如i和j,求他们的立方和 : k。这时候array[k]++;如果array[k] = 2,那么记录这个k : 其实这个题目跟求n以内质数非常接近。你的那个暴力做法,就是从0出发到n,看每个 : 数是不是质数。但另一种思路就是sieveofErathenese,就是说考虑因子,然后一遍遍 : 地反过来覆盖。很多时候如果时间效率太差,通常就是用space cost来换。
|
n*****f 发帖数: 17 | 69 其实还不到O(n^2/3)。枚举了i从1到n^1/3,j就到不了n^1/3了,从中间就跳出了。 |
c********p 发帖数: 1969 | |