w******j 发帖数: 185 | 1 f:
written test before interview:
Code:
public int bar(int a, int b) {
if (b == 0) return 1;
if (b % 2 == 0)
return bar(a, b / 2) * bar(a, b / 2);
return bar(a, b - 1) * a;
}
Questions:
1. bar 是什么?
2. big O in terms of a and b
3. list 2 - 3 changes you would make to the above fucntion, and reweite code
phone
1. array intersection
2. start from # , can only move to the upleft/up/upright cell from each
position, return the max value you could get traversing thru the matrix
W
=================
|0|5|0|5|0|1|0|4|
|0|0|0|2|0|0|0|0|
|0|1|0|0|2|2|0|1|
|0|0|0|0|2|0|0|1|
|9|0|0|0|2|7|0|0| H
|9|0|9|0|0|0|0|0|
|9|0|0|5|0|0|0|0|
|9|0|0|#|0|0|0|0| | r*********n 发帖数: 4553 | 2 算a^b吧,O(b),用memoization,是O(logb) | M*******u 发帖数: 51 | 3 第二个:1) Sort merge 2) DFS | r**h 发帖数: 1288 | 4 第二题不应该是DP吗?
【在 w******j 的大作中提到】 : f: : written test before interview: : Code: : public int bar(int a, int b) { : if (b == 0) return 1; : if (b % 2 == 0) : return bar(a, b / 2) * bar(a, b / 2); : return bar(a, b - 1) * a; : } : Questions:
| b****g 发帖数: 192 | 5 第一题是求a^b乘方吗?
因为有bar(a, b / 2) * bar(a, b / 2)存在,所以复杂度不是O(lgb)。其实就是O(b)
吧?
所以回答第三问时,这就是要改进的地方,return bar(a, b / 2)的平方
还可以再加几个特殊情况,比如:
if(a!=0 && b==0) return 1;(原来的未考虑a==0)
if(a==0 && b!=0) return 0;
还可以考虑溢出:
int tmp = bar(a,b/2);
if(tmp > INT_MAX/tmp) //overflow
也可以用long long记录所有中间结果改进。
最重要的是没考虑负数吧?
if(b<0) return 1/bar(a,b);
if(a<0 && b>0) 看b是奇偶在return正负bar(a,b)
【在 w******j 的大作中提到】 : f: : written test before interview: : Code: : public int bar(int a, int b) { : if (b == 0) return 1; : if (b % 2 == 0) : return bar(a, b / 2) * bar(a, b / 2); : return bar(a, b - 1) * a; : } : Questions:
| g**e 发帖数: 6127 | 6 漏了0^0
【在 b****g 的大作中提到】 : 第一题是求a^b乘方吗? : 因为有bar(a, b / 2) * bar(a, b / 2)存在,所以复杂度不是O(lgb)。其实就是O(b) : 吧? : 所以回答第三问时,这就是要改进的地方,return bar(a, b / 2)的平方 : 还可以再加几个特殊情况,比如: : if(a!=0 && b==0) return 1;(原来的未考虑a==0) : if(a==0 && b!=0) return 0; : 还可以考虑溢出: : int tmp = bar(a,b/2); : if(tmp > INT_MAX/tmp) //overflow
| b****g 发帖数: 192 | 7 心里考虑的,所以我才特一加了一行if(a!=0 && b==0)
但是因为0^0没定义,所以没写
【在 g**e 的大作中提到】 : 漏了0^0
| f*********m 发帖数: 726 | 8 感觉复杂度是
T(n)=2*T(n/2)+O(1), if b % 2 == 0
= T(n-1)+O(1),otherwise
所以是O(n).
【在 w******j 的大作中提到】 : f: : written test before interview: : Code: : public int bar(int a, int b) { : if (b == 0) return 1; : if (b % 2 == 0) : return bar(a, b / 2) * bar(a, b / 2); : return bar(a, b - 1) * a; : } : Questions:
|
|