忐忑的G电面 - 未名空间MITBBS历史存档

a*32013-01-23 08:01

1 楼

除了之前问我project的一些东西，code我就做了一题，是不是有点悲剧？
code是x^y，x和y都是正整数。
我开始以为是大家都练过的pow，然后说了一下思路，准备写。
面试官说先写最简单的，我就快速写了个O(n)的。
然后他问这个work吗？我想了下，说有可能overflow，就把result从int改为long。
他又问这个work吗？我想了下，long还有可能overflow，就说可以用多个long来表示结
果。
他遂提示用BigInteger，然后让我实现BigInteger类。
我的脑子这时有点卡壳，过了一阵才明白需要实现BigInteger的相乘。
中间还有点误解他的意思，经过提示才写出来。
最近rp不灵，面试时总是碰见没见过的题，不过也是因为自己实力不强，碰见不熟悉的
题就容易露怯。

l*a2013-01-23 08:01

2 楼

就一题BigInteger相乘不算悲剧。
一开始面试官用^表示有误导之嫌。

j*22013-01-23 08:01

3 楼

你用的什么语言？biginteger要自己写？

【在 a********3 的大作中提到】

: 除了之前问我project的一些东西，code我就做了一题，是不是有点悲剧？
: code是x^y，x和y都是正整数。
: 我开始以为是大家都练过的pow，然后说了一下思路，准备写。
: 面试官说先写最简单的，我就快速写了个O(n)的。
: 然后他问这个work吗？我想了下，说有可能overflow，就把result从int改为long。
: 他又问这个work吗？我想了下，long还有可能overflow，就说可以用多个long来表示结
: 果。
: 他遂提示用BigInteger，然后让我实现BigInteger类。
: 我的脑子这时有点卡壳，过了一阵才明白需要实现BigInteger的相乘。
: 中间还有点误解他的意思，经过提示才写出来。

w*a2013-01-23 08:01

4 楼

怎么G店面都喜欢考big int? 我今天的也考了，不过我是加法。

j*22013-01-23 08:01

5 楼

我记得幂函数只要平方就行了，大数平方能不能比大数乘法简单点？还是还是必须写个
general的乘法啊？

w*a2013-01-23 08:01

6 楼

那相当于这道题就是大数乘法和pow的结合题咯，那你一次店面做了两题还描述了
project，不算悲剧，BLESS

h*o2013-01-23 08:01

7 楼

这个是求x的y次幂吗？
biginteger 从来没用过啊。。。
你是用什么语言啊？
java也有这个吗？

【在 a********3 的大作中提到】

: 除了之前问我project的一些东西，code我就做了一题，是不是有点悲剧？
: code是x^y，x和y都是正整数。
: 我开始以为是大家都练过的pow，然后说了一下思路，准备写。
: 面试官说先写最简单的，我就快速写了个O(n)的。
: 然后他问这个work吗？我想了下，说有可能overflow，就把result从int改为long。
: 他又问这个work吗？我想了下，long还有可能overflow，就说可以用多个long来表示结
: 果。
: 他遂提示用BigInteger，然后让我实现BigInteger类。
: 我的脑子这时有点卡壳，过了一阵才明白需要实现BigInteger的相乘。
: 中间还有点误解他的意思，经过提示才写出来。

f*e2013-01-23 08:01

8 楼

每个int存范围在10^8的10进制数，相乘超过这个范围的补到下一个int。

【在 h*********o 的大作中提到】

: 这个是求x的y次幂吗？
: biginteger 从来没用过啊。。。
: 你是用什么语言啊？
: java也有这个吗？

a*32013-01-23 08:01

9 楼

我用的java，要求自己实现BigInteger，虽然我记得java也有个类叫BigInteger

a*32013-01-23 08:01

10 楼

不是实现整个BigInteger，他说只用实现能完成pow函数的function就行，我写了
constructor和multiply function。

t*h2013-01-23 08:01

11 楼

是string吗？还是数组

【在 a********3 的大作中提到】

: 除了之前问我project的一些东西，code我就做了一题，是不是有点悲剧？
: code是x^y，x和y都是正整数。
: 我开始以为是大家都练过的pow，然后说了一下思路，准备写。
: 面试官说先写最简单的，我就快速写了个O(n)的。
: 然后他问这个work吗？我想了下，说有可能overflow，就把result从int改为long。
: 他又问这个work吗？我想了下，long还有可能overflow，就说可以用多个long来表示结
: 果。
: 他遂提示用BigInteger，然后让我实现BigInteger类。
: 我的脑子这时有点卡壳，过了一阵才明白需要实现BigInteger的相乘。
: 中间还有点误解他的意思，经过提示才写出来。

j*y2013-01-23 08:01

12 楼

这题目还要考　big integer的相乘, 其实感觉挺难的
vector power(vector &a, vector & b)
{
int m = a.size() - 1;
int n = b.size() - 1;
vector result(m + n + 1, 0);
for(int i = 0; i < result.size(); ++i)
{
int power = m + n - i;
for(int k = 0; k <= power; ++k)
{

if(power - k > n)
{
continue;
}
if(k > m)
{
break;
}
result[i] += a[m - k] * b[n -(power - k)];
}
}
int remainder = 0;
for(int i = result.size() - 1; i > -1 ; --i)
{
int x = a[i] + remainder;
a[i] = x % 10;
remainder = x / 10;
}
while(remainder > 0)
{
result.insert(result.begin(), remainder % 10);
remainder = remainder / 10;
}
return result;
}
vector power(vector x, int y)
{
if(y == 1)
{
return x;
}
if(y & 0x1 == 0)
{
vector tmp = power(x, y >> 2);
return power(tmp, tmp);
}
else
{
return power(x, power(x, y - 1));
}
}
vector power(int x, int y)
{
vector vx;
while(x > 0)
{
vx.insert(vx.begin(), x % 10);
x = x / 10;
}
return power(vx, y);
}

【在 a********3 的大作中提到】

: 除了之前问我project的一些东西，code我就做了一题，是不是有点悲剧？
: code是x^y，x和y都是正整数。
: 我开始以为是大家都练过的pow，然后说了一下思路，准备写。
: 面试官说先写最简单的，我就快速写了个O(n)的。
: 然后他问这个work吗？我想了下，说有可能overflow，就把result从int改为long。
: 他又问这个work吗？我想了下，long还有可能overflow，就说可以用多个long来表示结
: 果。
: 他遂提示用BigInteger，然后让我实现BigInteger类。
: 我的脑子这时有点卡壳，过了一阵才明白需要实现BigInteger的相乘。
: 中间还有点误解他的意思，经过提示才写出来。

j*22013-01-23 08:01

13 楼

大数乘法在leetcode里是被我归为大题类得。。。

【在 j*****y 的大作中提到】

: 这题目还要考　big integer的相乘, 其实感觉挺难的
: vector power(vector &a, vector & b)
: {
: int m = a.size() - 1;
: int n = b.size() - 1;
: vector result(m + n + 1, 0);
: for(int i = 0; i < result.size(); ++i)
: {
: int power = m + n - i;
: for(int k = 0; k <= power; ++k)

l*a2013-01-23 08:01

14 楼

用字符串也可以吧？

【在 a********3 的大作中提到】

: 不是实现整个BigInteger，他说只用实现能完成pow函数的function就行，我写了
: constructor和multiply function。

B*t2013-01-23 08:01

15 楼

power(vector, int)里return的两个power都应该是mult吧。。。

【在 j*****y 的大作中提到】

: 这题目还要考　big integer的相乘, 其实感觉挺难的
: vector power(vector &a, vector & b)
: {
: int m = a.size() - 1;
: int n = b.size() - 1;
: vector result(m + n + 1, 0);
: for(int i = 0; i < result.size(); ++i)
: {
: int power = m + n - i;
: for(int k = 0; k <= power; ++k)

j*y2013-01-23 08:01

16 楼

是的，多谢，改过来了 :)

【在 B********t 的大作中提到】

: power(vector, int)里return的两个power都应该是mult吧。。。

a*32013-01-23 08:01

17 楼

我没写这么完整，之前也没做过大数相乘的题目。。。
刚看到leetcode上有string版本的大数相乘。。。

【在 j*****y 的大作中提到】

: 这题目还要考　big integer的相乘, 其实感觉挺难的
: vector power(vector &a, vector & b)
: {
: int m = a.size() - 1;
: int n = b.size() - 1;
: vector result(m + n + 1, 0);
: for(int i = 0; i < result.size(); ++i)
: {
: int power = m + n - i;
: for(int k = 0; k <= power; ++k)

g*n2013-01-23 08:01

18 楼

如果从低位开始存取的话，下面这段代码好像可以简单一点?
for(int i = 0; i < result.size(); ++i)
{
int power = m + n - i;
for(int k = 0; k <= power; ++k)
{

if(power - k > n)
{
continue;
}
if(k > m)
{
break;
}
result[i] += a[m - k] * b[n -(power - k)];
}
}
==〉
for (i=0; i< result.size(); i++)
{
result[i] = 0;
for (j=0; j< a.size(); j+=)
{
if (i-j >= 0)
{
result [i] += a[j] *b[i-j];
}
else break;
}
}

【在 j*****y 的大作中提到】

: 这题目还要考　big integer的相乘, 其实感觉挺难的
: vector power(vector &a, vector & b)
: {
: int m = a.size() - 1;
: int n = b.size() - 1;
: vector result(m + n + 1, 0);
: for(int i = 0; i < result.size(); ++i)
: {
: int power = m + n - i;
: for(int k = 0; k <= power; ++k)

j*y2013-01-23 08:01

19 楼

thanks，你的 idea 也可以简化我的 code
for(int i = 0; i < result.size(); ++i)
{
int power = m + n - i;
for(int k = max(0, power - n); k <= min(m, power); ++k)
{
result[i] += a[m - k] * b[n -(power - k)];
}
}

如果从低位开始存取的话，下面这段代码好像可以简单一点?
for(int i = 0; i < result.size(); ++i)
{
int power = m + n - i;
for(int k = 0; k <= power; ++k)
{

if(power - k > n)
{
continue;
}
if(k > m)
{
break;
}
result[i] += a[m - k] * b[n -(power - k)];
}
}
==〉
for (i=0; i< result.size(); i++)
{
result[i] = 0;
for (j=0; j< a.size(); j+=)
{
if (i-j >= 0)
{
result [i] += a[j] *b[i-j];
}
else break;
}
}

【在 g*********n 的大作中提到】

: 如果从低位开始存取的话，下面这段代码好像可以简单一点?
: for(int i = 0; i < result.size(); ++i)
: {
: int power = m + n - i;
: for(int k = 0; k <= power; ++k)
: {
:
: if(power - k > n)
: {
: continue;