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:
|
|
