L家和G家的几道面试题不懂 - 未名空间MITBBS历史存档

国际科技财经博客移民网络热点娱乐民生时事公众号

Redian新闻

>未名空间

>JobHunting - 待字闺中

L家和G家的几道面试题不懂

L家和G家的几道面试题不懂# JobHunting - 待字闺中

b*g2013-06-02 07:06

1 楼

都是大家贴的面经，但是有几个我不懂：
1. L家的factorial digits sum。比如input为10，因为10！= 3628800，就应该返回
sum的值 = 3+6+2+8。除了用BigInteger class，还有其他方法吗？（因为C++的stl里
没有BigInteger）
2. G家的Design an API which is used for a cache big data。
big data的和小data的有什么区别？

g*s2013-06-02 07:06

2 楼

1. 可以用类似大数乘法把结果存在一个数组里吧？
2. big data说明cache装不下，需要处理cache溢出的机制，比如LRU

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

: 都是大家贴的面经，但是有几个我不懂：
: 1. L家的factorial digits sum。比如input为10，因为10！= 3628800，就应该返回
: sum的值 = 3+6+2+8。除了用BigInteger class，还有其他方法吗？（因为C++的stl里
: 没有BigInteger）
: 2. G家的Design an API which is used for a cache big data。
: big data的和小data的有什么区别？

b*g2013-06-02 07:06

3 楼

1. 呃，那本质上还是bigInteger啊
2. 能具体说说是怎样的机制吗？

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

: 1. 可以用类似大数乘法把结果存在一个数组里吧？
: 2. big data说明cache装不下，需要处理cache溢出的机制，比如LRU

g*G2013-06-02 07:06

4 楼

第一题如果面试时碰到，就自己写String multiplication呗，我是写好加法，cache1-
9的乘法结果，然后错位相加
如果想加速的话可以用Karatsuba乘法
第二题不会，搬小板凳听

b*72013-06-02 07:06

5 楼

贴段代码
void multiply(vector & src, int num)
{
assert(!src.empty() && num > 0);
int c = 0;
for(int i = 0; i < (int)src.size(); i++)
{
int v = src[i] * num + c;
src[i] = v % 10;
c = v/10;
}
while(c > 0)
{
src.push_back(c%10);
c /= 10;
}
}
int FactDigitsSum(size_t n)
{
if(n < 2) return 1;
vector src;
src.push_back(1);
for(int i = 2; i <= n; i++)
mutiply(src, i);
int sum = accumulate(src.begin(), src.end(), 0);
return sum;
}

s*52013-06-02 07:06

6 楼

There is a bug in the "multiply" function. When "num" is not very small, "v"
can be > 100, so "v%10" > 10, and then you push a >10 number into the "i"
position of the vector. Everything messed up.

【在 b******7 的大作中提到】

: 贴段代码
: void multiply(vector & src, int num)
: {
: assert(!src.empty() && num > 0);
: int c = 0;
: for(int i = 0; i < (int)src.size(); i++)
: {
: int v = src[i] * num + c;
: src[i] = v % 10;
: c = v/10;

s*x2013-06-02 07:06

7 楼

Try System.out.print(1001%10);
See what it gives you

v"

【在 s***5 的大作中提到】

: There is a bug in the "multiply" function. When "num" is not very small, "v"
: can be > 100, so "v%10" > 10, and then you push a >10 number into the "i"
: position of the vector. Everything messed up.

s*52013-06-02 07:06

8 楼

没错，我脑子short了。

【在 s********x 的大作中提到】

: Try System.out.print(1001%10);
: See what it gives you
:
: v"

t*d2013-06-02 07:06

9 楼

Should work, thx

★ 发自iPhone App: ChineseWeb 7.8

【在 b******7 的大作中提到】

s*52013-06-02 07:06

10 楼

根据原题，最后返回结果的时候，似乎要去掉重复数字？LZ没说清楚。

【在 b******7 的大作中提到】

u*o2013-06-02 07:06

11 楼

MARK

k*j2013-06-02 07:06

12 楼

同问第二题api设计

c*p2013-06-02 07:06

13 楼

mark

r*c2013-06-02 07:06

14 楼

你的代码正确无误，不过是倒着算的，我笨，改写了一下，好顺应从小就习惯了的思维
，见笑了。
void multiply(deque& src, int num)
{
int c = 0;
for(int i = src.size() - 1; i >= 0; --i)
{
int v = src[i] * num + c;
src[i] = v % 10;
c = v / 10;
}
while(c > 0)
{
src.push_front(c % 10); //msd first
c /= 10;
}
}

【在 b******7 的大作中提到】