d****3
发帖数: 123 | 1 让我写一个calculate the nth number in fibonacci sequence的函数：
我给出了一个非递归版本，
public static int fibnacci_M(int i) {
if (i<=2) {
return 1;
} else {
int[] value = {1,1};
int sum = 0;
while (i>2) {
sum = value[0] + value[1];
value[1] = value[0];
value[0] = sum;
i--;
}
return sum;
}
}
然后他问我如果用递归复杂度多少。之后为我这个函数能不能马上deploy到Server上,
然后can this function be used to calculate the 1 billion th number, how to
improve the function to calculate large number. Will you calculate the
result for each request, if using cache how do you store and retrieve the
cache, will you store the cache in each app server? How many servers and how
much space do you need to store and calculate the cache.
我说了用java的BigInteger，然后扯了一些distributed system的东西，不过因为没做
过就随便说了说，面试官没满意，想问问版上各位这些问题该怎么答呢。 |
e*******8
发帖数: 94 | 2 这个方法不能算超过九十几的数吧？fib的number of digits是指数增长的，所以九十
几之后number of digits就超过64位了。时间复杂度取决于算n digit的数字的乘法
的时间复杂度。我记得是O(n log n loglog n).
dasgupta的算法书上有具体讲的。 |
d****3
发帖数: 123 | 3 如果用biginteger可不可以呢，关键想知道如何store 和 retrieve cache的答案呢。
【在 e*******8 的大作中提到】
: 这个方法不能算超过九十几的数吧？fib的number of digits是指数增长的，所以九十
: 几之后number of digits就超过64位了。时间复杂度取决于算n digit的数字的乘法
: 的时间复杂度。我记得是O(n log n loglog n).
: dasgupta的算法书上有具体讲的。
|
s********r
发帖数: 403 | 4 把算法按堆栈展开，可以形成一个类似 tree 结构，然后从底向上作 parallel
reduction。
被加数和结果应该做padding, 最好确保存在于不同的 cacheline, 降低 cache
thrashing |
z****e
发帖数: 54598 | 5 用string吧
这么简单的计算，何必用biginteger呢？
cache的话，这个题是典型的dp
所以把前面多次计算的结果，放到cache中去
每次先找结果，再计算
cache的话，因为只存不改，所以读起来毫无压力
不需要用太多的lock占用资源，用concurrenthashmap
不用hashtable，因为hashtable会锁整个对象
如果不想在每一个app server上都放的话
就找一个db，把数据给我往db里面塞
然后优化db和app server的连接，建立pool什么的
这个面官水平不差，懂得将简单的问题复杂化，并逐步深入测你的水平
【在 d****3 的大作中提到】
: 如果用biginteger可不可以呢，关键想知道如何store 和 retrieve cache的答案呢。
|
u*****o
发帖数: 1224 | 6 这题太可怕了..
我要是碰到了FIBONACCI肯定笑开花。。没想到后面隐藏着这么多陷阱。。
真是很傻很天真。。 |
s*******n
发帖数: 305 | 7
【在 z****e 的大作中提到】
: 用string吧
: 这么简单的计算，何必用biginteger呢？
: cache的话，这个题是典型的dp
: 所以把前面多次计算的结果，放到cache中去
: 每次先找结果，再计算
: cache的话，因为只存不改，所以读起来毫无压力
: 不需要用太多的lock占用资源，用concurrenthashmap
: 不用hashtable，因为hashtable会锁整个对象
: 如果不想在每一个app server上都放的话
: 就找一个db，把数据给我往db里面塞
|
d****3
发帖数: 123 | 8 如果把结果放在每一个App Server上的话，是不是每次Server Restart计算就要开始，
然后算到一定程度？如果好几个用户Request 1 billion th number，是不是第一个要
等一段时间才出结果？
【在 z****e 的大作中提到】
: 用string吧
: 这么简单的计算，何必用biginteger呢？
: cache的话，这个题是典型的dp
: 所以把前面多次计算的结果，放到cache中去
: 每次先找结果，再计算
: cache的话，因为只存不改，所以读起来毫无压力
: 不需要用太多的lock占用资源，用concurrenthashmap
: 不用hashtable，因为hashtable会锁整个对象
: 如果不想在每一个app server上都放的话
: 就找一个db，把数据给我往db里面塞
|
z****e
发帖数: 54598 | 9 对，如果关机就丢掉了
所以如果这个方法要包装成一个service的话
那就需要做persistence
找地方存起来
第一次当然会慢
【在 d****3 的大作中提到】
: 如果把结果放在每一个App Server上的话，是不是每次Server Restart计算就要开始，
: 然后算到一定程度？如果好几个用户Request 1 billion th number，是不是第一个要
: 等一段时间才出结果？
|
v********n
发帖数: 18 | 10 nmark.... 同觉得自己图森破n【在 dy0953 (dy0953)的大作中提到：】n：让我写一个
calculate the nth number in fibonacci sequence的函数：n：n：我给出了一个非递
归版本，n：public static int fibnacci_M(int i) {n： if (i<=2) {n：
return 1;n： } else {n……nn--n[发自未名空间Android客户端] |
