c*******a
发帖数: 45 | 1 开始几道C++概念题：
1，abstract class 和 concrete class 的区别。
2，abstract class 可不可以有constructor
3，如果abstract class有constructor，这个constructor什么时候被call。
然后算法题：
1，写段程序，把sorted array放到binary search tree里面
2，写一个函数来计算x的n次方。 |
Z*****Z
发帖数: 723 | 2 bless
【在 c*******a 的大作中提到】
: 开始几道C++概念题：
: 1，abstract class 和 concrete class 的区别。
: 2，abstract class 可不可以有constructor
: 3，如果abstract class有constructor，这个constructor什么时候被call。
: 然后算法题：
: 1，写段程序，把sorted array放到binary search tree里面
: 2，写一个函数来计算x的n次方。
|
k***n
发帖数: 93 | |
y*****o
发帖数: 36 | 4 bless and thanks for sharing!! |
c******t
发帖数: 1500 | 5 请问楼主，把sorted array放到binary search tree里面，这个tree是必须balanced吗
？ |
c*******a
发帖数: 45 | 6 面试的人到没说是不是哟啊balanced，但是言下的意思，就是要balanced的吧。 |
s*****n
发帖数: 5488 | 7 从中间开始不就是balanced了吗。
【在 c******t 的大作中提到】
: 请问楼主，把sorted array放到binary search tree里面，这个tree是必须balanced吗
: ？
|
s*********g
发帖数: 153 | |
K******g
发帖数: 1870 | 9 “他看到我有不对的地方，还帮我改”
面试官帮你改bug，这绝对不是什么好事情啊。人家每挑一个，你离死亡就近一步，呵呵
另外，你最后一题，能详细点吗？考察的重点是recursive呢，还是溢出啊？
【在 c*******a 的大作中提到】
: 开始几道C++概念题：
: 1，abstract class 和 concrete class 的区别。
: 2，abstract class 可不可以有constructor
: 3，如果abstract class有constructor，这个constructor什么时候被call。
: 然后算法题：
: 1，写段程序，把sorted array放到binary search tree里面
: 2，写一个函数来计算x的n次方。
|
E*****7
发帖数: 128 | 10 分析:为什么GOOGLE考这么"简单"的C++题 (写一个函数来计算x的n次方)?
答案1:
int XraisedtoN(int x, int N) {
int result = 1;
for (int i = 0; i < N; i++) {
result = result * x;
}
return result;
}
且慢, 如果 N = 0 或者 N = -2, 答案1死定了.
答案2:
int XraisedtoN(int x, int N) {
if (N == 0) // X^0 = 1
return 1;
int num;
bool negative;
if (N < 0) // handle X^-2 for example
{
num = -N;
negative = true;
}
else {
num = N;
negative = false;
}
int result = 1;
for (int i = 0; i < N; i++) {
result = result * x;
}
if (negative)
return (1/result);
else
return result;
}
且慢, 2^(-2)按照上述答案2计算为1/4永远为零(正解为
if (negative)
return (1.0)/result
答案2也死定了.看似简单的一道题,有很多陷阱(边界条件/特例).
我的答案是:
template // base type T, return type R
R XraisedtoN(T x, int N) {
if ( N == 0 )
return 1; // X^0 = 1
bool negative;
int num;
if ( N < 0 ) {
num = -N;
negative = true;
}
else {
num = N;
negative = false;
}
T result(1); // type is NOT R
for (int i = 0; i < num; i++)
result = result * x;
if (negative)
return (R)( R(1) / result );
else
return (R)result;
}
不过, 我得告诉面试官此解的前提条件是:
The base type T should be convertible to type R, either implicitly or explicitly |
|
|
j**l
发帖数: 2911 | 11 需要你用bit操作给出O(log N)的算法吧，也可用来结合矩阵乘来求Fibonacci数列
【在 E*****7 的大作中提到】
: 分析:为什么GOOGLE考这么"简单"的C++题 (写一个函数来计算x的n次方)?
: 答案1:
: int XraisedtoN(int x, int N) {
: int result = 1;
: for (int i = 0; i < N; i++) {
: result = result * x;
: }
: return result;
: }
: 且慢, 如果 N = 0 或者 N = -2, 答案1死定了.
|
j**l
发帖数: 2911 | 12 除了时间复杂度外，至少还有处理溢出的问题，负指数的问题，结果用int存还是
double存的问题，能否用数组表示大整数作乘方的问题，各种test cases的问题，要考
虑得很多
【在 E*****7 的大作中提到】
: 分析:为什么GOOGLE考这么"简单"的C++题 (写一个函数来计算x的n次方)?
: 答案1:
: int XraisedtoN(int x, int N) {
: int result = 1;
: for (int i = 0; i < N; i++) {
: result = result * x;
: }
: return result;
: }
: 且慢, 如果 N = 0 或者 N = -2, 答案1死定了.
|
n*******0
发帖数: 2002 | 13 co-ask.
【在 c******t 的大作中提到】
: 请问楼主，把sorted array放到binary search tree里面，这个tree是必须balanced吗
: ？
|
d**e
发帖数: 6098 | 14 balance应该是最简单的吧，直接由中间取就可以了。
【在 n*******0 的大作中提到】
: co-ask.
|
y*********e
发帖数: 518 | 15 这个题目可以说是在考察边界条件，面试者应该跟考官沟通好。一般情况下 N
应该是非负的整数。若是遇到负的整数怎么办？抛出异常就可以了。若是
integer overflow怎么办？
最naive的解法是O(N)。此题也可以优化到O(logN)，我曾经遇到这个面题，
当时想出来的解法如下：
计算X^1, X^2, X^4, X^8, ..., X^M, X^(2M)，使得M <= N < 2M。
那么欲求的值就介于X^M和X^(2M)之间。然后用二分法确定 N 的位置。
从X^1, X^2, 涨到 X^M (M <= N < 2M)，需要O(logN)的时间。然后在M
和2M里面确定N的位置，需要O(logN)的时间。整个解法还需要O(logN)的空间
。
【在 E*****7 的大作中提到】
: 分析:为什么GOOGLE考这么"简单"的C++题 (写一个函数来计算x的n次方)?
: 答案1:
: int XraisedtoN(int x, int N) {
: int result = 1;
: for (int i = 0; i < N; i++) {
: result = result * x;
: }
: return result;
: }
: 且慢, 如果 N = 0 或者 N = -2, 答案1死定了.
|
s*****n
发帖数: 5488 | 16 logN有用吗？unsigned long也是就是64位。
【在 y*********e 的大作中提到】
: 这个题目可以说是在考察边界条件，面试者应该跟考官沟通好。一般情况下 N
: 应该是非负的整数。若是遇到负的整数怎么办？抛出异常就可以了。若是
: integer overflow怎么办？
: 最naive的解法是O(N)。此题也可以优化到O(logN)，我曾经遇到这个面题，
: 当时想出来的解法如下：
: 计算X^1, X^2, X^4, X^8, ..., X^M, X^(2M)，使得M <= N < 2M。
: 那么欲求的值就介于X^M和X^(2M)之间。然后用二分法确定 N 的位置。
: 从X^1, X^2, 涨到 X^M (M <= N < 2M)，需要O(logN)的时间。然后在M
: 和2M里面确定N的位置，需要O(logN)的时间。整个解法还需要O(logN)的空间
: 。
|
y*********e
发帖数: 518 | 17 若是函数的输入不是int或者long long，是任意精确度的big_int呢？
【在 s*****n 的大作中提到】
: logN有用吗？unsigned long也是就是64位。
|
E********a
发帖数: 124 | 18 看到第二题，回忆起当年我还初来本版时见到一位大牛algorithmics的code，觉得很漂
亮简洁：while
里面3行code搞定，log复杂度。
【在 c*******a 的大作中提到】
: 开始几道C++概念题：
: 1，abstract class 和 concrete class 的区别。
: 2，abstract class 可不可以有constructor
: 3，如果abstract class有constructor，这个constructor什么时候被call。
: 然后算法题：
: 1，写段程序，把sorted array放到binary search tree里面
: 2，写一个函数来计算x的n次方。
|
r*********s
发帖数: 2157 | 19 是怎么写的呢?
【在 E********a 的大作中提到】
: 看到第二题，回忆起当年我还初来本版时见到一位大牛algorithmics的code，觉得很漂
: 亮简洁：while
: 里面3行code搞定，log复杂度。
|
j******4
发帖数: 116 | 20 x^n
Rev(x, n)
if n == 0
return 1
if n=1
return x
if n is even
return Rev(x*x, n/2)
else
return rev(x*x, n/2) * x
【在 c*******a 的大作中提到】
: 开始几道C++概念题：
: 1，abstract class 和 concrete class 的区别。
: 2，abstract class 可不可以有constructor
: 3，如果abstract class有constructor，这个constructor什么时候被call。
: 然后算法题：
: 1，写段程序，把sorted array放到binary search tree里面
: 2，写一个函数来计算x的n次方。
|
j**l
发帖数: 2911 | 21 求a^n
result = 1;
p = a;
while (n)
{
if (n & 1)
result *= p;
n >>= 1;
p *= p;
}
return result;
【在 r*********s 的大作中提到】
: 是怎么写的呢?
|
j**l
发帖数: 2911 | 22 二进制原理
比如a^5, 因为5的2二进制是101, 5 = 4 + 1 也就是拆为a^4 * a
比如a^6, 因为6的2二进制是110, 6 = 4 + 2 也就是拆为a^4 * a^2
比如a^7, 因为7的2二进制是111, 7 = 4 + 2 + 1 也就是拆为a^4 * a^2 * a
也就是对序列a, a^2, a^4, a^8, a^16, a^32, ...
决定乘不乘上某项就看指数二进制对应的位是不是1
【在 j**l 的大作中提到】
: 求a^n
: result = 1;
: p = a;
: while (n)
: {
: if (n & 1)
: result *= p;
: n >>= 1;
: p *= p;
: }
|
