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 的大作中提到】
: 一般应该是问两道题。我这次二面也是一个题不清楚题意弄了很久，导
: 致他后面直接问简历，估计是挂了。
|
s********u
发帖数: 1109 | 4 看错题，修改掉。
【在 m*******0 的大作中提到】
: 好吧，这个竟然没想到。。。
: 他有问我能不能improve，我说想不到了，他也没继续问了。。
|
m*******0
发帖数: 38 | 5 又想了一下总时间应该是O(N^{4/3} + NlogN)吧，要对每个n从1～N来验证，每个n验证
的时间是n^{1/3}，加上排序总时间就是N^{4/3} + NlogN ?
【在 s********u 的大作中提到】
: 看错题，修改掉。
|
s********u
发帖数: 1109 | 6 看错题，修改掉。
【在 m*******0 的大作中提到】
: 又想了一下总时间应该是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 的大作中提到】
: 看错题，修改掉。
|
s********u
发帖数: 1109 | 8 看错题，修改掉。
N
【在 m*******0 的大作中提到】
: 弱问为什么平方跟三次方不一样？ 我也可以使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 的大作中提到】
: 看错题，修改掉。
:
: N
|
s*****r
发帖数: 108 | |
|
|
s********u
发帖数: 1109 | 11 额。。我发现我理解错了
因为你说满足两组数(a, b), (c, d)使他们的立方和等于n
我还以为给一个n，然后让我找所有立方和等于n的。。。
吧？
【在 m*******0 的大作中提到】
: 你这个只能得到立方和等于N的数的个数吧？不过他是要找出所有小于N的数n满足存在
: 两组数(a, b)和(c, d)使他们立方和等于n。所以貌似要把1～N的所有数都check一遍吧？
|
m*******0
发帖数: 38 | 12 不是很懂你的意思，里面不会涉及到负数的吧，他是要找出从1～N的数中满足存在两组
不同的数是他们的立方和等于要找的那个数。貌似和2sum有点不一样，就是我们要对所
有1～N都测试一遍？
【在 s********u 的大作中提到】
: 额。。我发现我理解错了
: 因为你说满足两组数(a, b), (c, d)使他们的立方和等于n
: 我还以为给一个n，然后让我找所有立方和等于n的。。。
:
: 吧？
|
m*******0
发帖数: 38 | 13 对的，做完这题他说时间到了，发现时间过的真快，写代码的时间也就几分钟，不知不
觉就过去了。。。
【在 s*****r 的大作中提到】
: 就做了一题？
|
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 的大作中提到】
: 额。。我发现我理解错了
: 因为你说满足两组数(a, b), (c, d)使他们的立方和等于n
: 我还以为给一个n，然后让我找所有立方和等于n的。。。
:
: 吧？
|
s*****r
发帖数: 108 | 15 用暴力只做一题肯定挂 你是说用了四个循环？
不是只枚举一次 0 ~ n^(1/3) 就能找到所有 (a, b) ?
【在 m*******0 的大作中提到】
: 对的，做完这题他说时间到了，发现时间过的真快，写代码的时间也就几分钟，不知不
: 觉就过去了。。。
|
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 的大作中提到】
: 用暴力只做一题肯定挂 你是说用了四个循环？
: 不是只枚举一次 0 ~ n^(1/3) 就能找到所有 (a, b) ?
|
s*****r
发帖数: 108 | 18 只需一层循环枚举
是O
【在 m*******0 的大作中提到】
: 对每个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 的大作中提到】
: 我想了下，至少有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 的大作中提到】
: 主要就是做慢了 复杂度分析也不对
: 边界比如 0，N 有多大等
: 还有题意可能也没有问清楚 我就很想问他是不是要多次询问 N
: 根据定义这种数的个数增长应该非常缓慢 可能 N 非常大就几个满足要求的， N1 <<
: N2，之内的 taxicab number 却没什么差别
: 各种原因都导致了挂
|
m*******0
发帖数: 38 | 22 复杂度他同意了，说是对的。然后N有多大跟这道题的解法没什么关系吧？我觉得中间
扯谈的时间估计多了点，一眨眼就时间过了，总共时间就30分钟左右.
【在 s*****r 的大作中提到】
: 主要就是做慢了 复杂度分析也不对
: 边界比如 0，N 有多大等
: 还有题意可能也没有问清楚 我就很想问他是不是要多次询问 N
: 根据定义这种数的个数增长应该非常缓慢 可能 N 非常大就几个满足要求的， N1 <<
: N2，之内的 taxicab number 却没什么差别
: 各种原因都导致了挂
|
s*****r
发帖数: 108 | 23 我想主要得问清对方要求，比如是否要多次询问
在解的个数增长十分缓慢的情况下 这个优化太费空间 理论上的讨论倒是可以展现些分
析能力
所以我觉得应该先问清楚，然后小数据测试增长速度，再问它喜欢时间还是空间，增长
速度太慢肯定不会用空间换时间
小数据就随便暴力，大数据就暴力预处理+打表
【在 s********u 的大作中提到】
: 主要还是没有improve吧，lz的暴力法是O(n^4/3)，优化方法是O(n^2/3)，这个差的还
: 挺多的。。
|
s*****r
发帖数: 108 | 24 和 N 是有关系的，为什么还是和解的增长速度有关，决定了空间换时间还是时间换空间
比如 N = 1e10 和 N = 1e19 之间就差几个解，再大直到超出整型表示范围都没有更多
解呢？
【在 m*******0 的大作中提到】
: 复杂度他同意了，说是对的。然后N有多大跟这道题的解法没什么关系吧？我觉得中间
: 扯谈的时间估计多了点，一眨眼就时间过了，总共时间就30分钟左右.
|
s********u
发帖数: 1109 | 25 如果觉得稀疏，还是可以打表，用hashtable就行了。
【在 s*****r 的大作中提到】
: 我想主要得问清对方要求，比如是否要多次询问
: 在解的个数增长十分缓慢的情况下 这个优化太费空间 理论上的讨论倒是可以展现些分
: 析能力
: 所以我觉得应该先问清楚，然后小数据测试增长速度，再问它喜欢时间还是空间，增长
: 速度太慢肯定不会用空间换时间
: 小数据就随便暴力，大数据就暴力预处理+打表
|
s*****r
发帖数: 108 | 26 搜了下这数不叫 taxicab number...面试官好坑... |
s******y
发帖数: 416 | 27 你taxicab number定义没用对
【在 m*******0 的大作中提到】
: 对方是个老外，上来问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 的大作中提到】
: 对方是个老外，上来问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 的大作中提到】
: 小弟的代码， 复杂度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 的大作中提到】
: 小弟的代码， 复杂度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 的大作中提到】
: 你这个是O（n）？
: 嘿嘿
|
n****e
发帖数: 678 | 35 恩，这个想法好。
~n
【在 s********u 的大作中提到】
: 我想了下，至少有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 的大作中提到】
: 一般应该是问两道题。我这次二面也是一个题不清楚题意弄了很久，导
: 致他后面直接问简历，估计是挂了。
|
m*******0
发帖数: 38 | 39 又想了一下总时间应该是O(N^{4/3} + NlogN)吧，要对每个n从1～N来验证，每个n验证
的时间是n^{1/3}，加上排序总时间就是N^{4/3} + NlogN ?
【在 s********u 的大作中提到】
: 一般应该是问两道题。我这次二面也是一个题不清楚题意弄了很久，导
: 致他后面直接问简历，估计是挂了。
|
m*******0
发帖数: 38 | 40 弱问为什么平方跟三次方不一样？ 我也可以使i从1到N遍历找另一个j使i^2 + j^2 = N
的吧？
【在 s********u 的大作中提到】
: 一般应该是问两道题。我这次二面也是一个题不清楚题意弄了很久，导
: 致他后面直接问简历，估计是挂了。
|
|
|
s********u
发帖数: 1109 | 41 看错题，修改掉。
N
【在 m*******0 的大作中提到】
: 弱问为什么平方跟三次方不一样？ 我也可以使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 的大作中提到】
: 看错题，修改掉。
:
: N
|
s*****r
发帖数: 108 | |
s********u
发帖数: 1109 | 44 额。。我发现我理解错了
因为你说满足两组数(a, b), (c, d)使他们的立方和等于n
我还以为给一个n，然后让我找所有立方和等于n的。。。
吧？
【在 m*******0 的大作中提到】
: 你这个只能得到立方和等于N的数的个数吧？不过他是要找出所有小于N的数n满足存在
: 两组数(a, b)和(c, d)使他们立方和等于n。所以貌似要把1～N的所有数都check一遍吧？
|
m*******0
发帖数: 38 | 45 不是很懂你的意思，里面不会涉及到负数的吧，他是要找出从1～N的数中满足存在两组
不同的数是他们的立方和等于要找的那个数。貌似和2sum有点不一样，就是我们要对所
有1～N都测试一遍？
【在 s********u 的大作中提到】
: 额。。我发现我理解错了
: 因为你说满足两组数(a, b), (c, d)使他们的立方和等于n
: 我还以为给一个n，然后让我找所有立方和等于n的。。。
:
: 吧？
|
m*******0
发帖数: 38 | 46 对的，做完这题他说时间到了，发现时间过的真快，写代码的时间也就几分钟，不知不
觉就过去了。。。
【在 s*****r 的大作中提到】
: 就做了一题？
|
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 的大作中提到】
: 额。。我发现我理解错了
: 因为你说满足两组数(a, b), (c, d)使他们的立方和等于n
: 我还以为给一个n，然后让我找所有立方和等于n的。。。
:
: 吧？
|
s*****r
发帖数: 108 | 48 用暴力只做一题肯定挂 你是说用了四个循环？
不是只枚举一次 0 ~ n^(1/3) 就能找到所有 (a, b) ?
【在 m*******0 的大作中提到】
: 对的，做完这题他说时间到了，发现时间过的真快，写代码的时间也就几分钟，不知不
: 觉就过去了。。。
|
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 的大作中提到】
: 用暴力只做一题肯定挂 你是说用了四个循环？
: 不是只枚举一次 0 ~ n^(1/3) 就能找到所有 (a, b) ?
|
|
|
s*****r
发帖数: 108 | 51 只需一层循环枚举
是O
【在 m*******0 的大作中提到】
: 对每个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 的大作中提到】
: 我想了下，至少有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 的大作中提到】
: 主要就是做慢了 复杂度分析也不对
: 边界比如 0，N 有多大等
: 还有题意可能也没有问清楚 我就很想问他是不是要多次询问 N
: 根据定义这种数的个数增长应该非常缓慢 可能 N 非常大就几个满足要求的， N1 <<
: N2，之内的 taxicab number 却没什么差别
: 各种原因都导致了挂
|
m*******0
发帖数: 38 | 55 复杂度他同意了，说是对的。然后N有多大跟这道题的解法没什么关系吧？我觉得中间
扯谈的时间估计多了点，一眨眼就时间过了，总共时间就30分钟左右.
【在 s*****r 的大作中提到】
: 主要就是做慢了 复杂度分析也不对
: 边界比如 0，N 有多大等
: 还有题意可能也没有问清楚 我就很想问他是不是要多次询问 N
: 根据定义这种数的个数增长应该非常缓慢 可能 N 非常大就几个满足要求的， N1 <<
: N2，之内的 taxicab number 却没什么差别
: 各种原因都导致了挂
|
s*****r
发帖数: 108 | 56 我想主要得问清对方要求，比如是否要多次询问
在解的个数增长十分缓慢的情况下 这个优化太费空间 理论上的讨论倒是可以展现些分
析能力
所以我觉得应该先问清楚，然后小数据测试增长速度，再问它喜欢时间还是空间，增长
速度太慢肯定不会用空间换时间
小数据就随便暴力，大数据就暴力预处理+打表
【在 s********u 的大作中提到】
: 主要还是没有improve吧，lz的暴力法是O(n^4/3)，优化方法是O(n^2/3)，这个差的还
: 挺多的。。
|
s*****r
发帖数: 108 | 57 和 N 是有关系的，为什么还是和解的增长速度有关，决定了空间换时间还是时间换空间
比如 N = 1e10 和 N = 1e19 之间就差几个解，再大直到超出整型表示范围都没有更多
解呢？
【在 m*******0 的大作中提到】
: 复杂度他同意了，说是对的。然后N有多大跟这道题的解法没什么关系吧？我觉得中间
: 扯谈的时间估计多了点，一眨眼就时间过了，总共时间就30分钟左右.
|
s********u
发帖数: 1109 | 58 如果觉得稀疏，还是可以打表，用hashtable就行了。
【在 s*****r 的大作中提到】
: 我想主要得问清对方要求，比如是否要多次询问
: 在解的个数增长十分缓慢的情况下 这个优化太费空间 理论上的讨论倒是可以展现些分
: 析能力
: 所以我觉得应该先问清楚，然后小数据测试增长速度，再问它喜欢时间还是空间，增长
: 速度太慢肯定不会用空间换时间
: 小数据就随便暴力，大数据就暴力预处理+打表
|
s*****r
发帖数: 108 | 59 搜了下这数不叫 taxicab number...面试官好坑... |
s******y
发帖数: 416 | 60 你taxicab number定义没用对
【在 m*******0 的大作中提到】
: 对方是个老外，上来问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 的大作中提到】
: 对方是个老外，上来问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 的大作中提到】
: 小弟的代码， 复杂度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 的大作中提到】
: 小弟的代码， 复杂度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 的大作中提到】
: 你这个是O（n）？
: 嘿嘿
|
n****e
发帖数: 678 | 68 恩，这个想法好。
~n
【在 s********u 的大作中提到】
: 我想了下，至少有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 | |
