Redian新闻
>
L家和G家的几道面试题不懂
avatar
L家和G家的几道面试题不懂# JobHunting - 待字闺中
b*g
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的有什么区别?
avatar
g*s
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的有什么区别?

avatar
b*g
3
1. 呃,那本质上还是bigInteger啊
2. 能具体说说是怎样的机制吗?

【在 g*******s 的大作中提到】
: 1. 可以用类似大数乘法把结果存在一个数组里吧?
: 2. big data说明cache装不下,需要处理cache溢出的机制,比如LRU

avatar
g*G
4
第一题如果面试时碰到,就自己写String multiplication呗,我是写好加法,cache1-
9的乘法结果,然后错位相加
如果想加速的话可以用Karatsuba乘法
第二题不会,搬小板凳听
avatar
b*7
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;
}
avatar
s*5
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;

avatar
s*x
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.

avatar
s*5
8
没错,我脑子short了。

【在 s********x 的大作中提到】
: Try System.out.print(1001%10);
: See what it gives you
:
: v"

avatar
t*d
9
Should work, thx

★ 发自iPhone App: ChineseWeb 7.8

【在 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;

avatar
s*5
10
根据原题,最后返回结果的时候,似乎要去掉重复数字?LZ没说清楚。

【在 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;

avatar
u*o
11
MARK
avatar
k*j
12
同问第二题api设计
avatar
c*p
13
mark
avatar
r*c
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 的大作中提到】
: 贴段代码
: 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;

avatar
x*0
15
mark
相关阅读
logo
联系我们隐私协议©2024 redian.news
Redian新闻
Redian.news刊载任何文章,不代表同意其说法或描述,仅为提供更多信息,也不构成任何建议。文章信息的合法性及真实性由其作者负责,与Redian.news及其运营公司无关。欢迎投稿,如发现稿件侵权,或作者不愿在本网发表文章,请版权拥有者通知本网处理。