发面经攒人品，多个公司

sue0927 发表于 2015-8-4 21:25
Amex 我也面了，但是面试。。。太呵呵呵了。。
因为是个所谓的ab initIO的软件操作考察。。又被老印给黑了 ...

ab initIO？我都没听过诶  你面的哪一个岗呀？

计算平方根的话。。。泰勒展开有收敛半径吧？
比方说展开式里面有(x-1)的高次方，当x大于2时不收敛，需要预先处理一下。

我猜牛顿法可以一步到位：
result = 1;
diff = 99999;
while(diff > 0.01){
newx = (x+a/x)/2;
diff = abs(newx - x);
x = newx;
}
我猜这个可能是短时间里能写完的简单算法。。。

补充内容 (2015-8-5 08:38):
sorry，是x初值=1，不是result。。。

mint0715 发表于 2015-8-5 08:37
计算平方根的话。。。泰勒展开有收敛半径吧？
比方说展开式里面有(x-1)的高次方，当x大于2时不收敛，需要 ...

你这个我没有太看懂诶，a是什么？

面试官当时教我的解法：
给定任意y，求 sqrt(y) = x
可以写成x**2 = y
也就是x**2 - y = 0
. Χ
泰勒展开：
定义这个function: f(x) = x**2 - y
. 1point3acres在x0处的泰勒展开： f(x; x0) = f(x0) + f'(x0)*(x-x0) + f''(x0)*(x-x0)^2/2! + ...
也就是： f(x;x0) = f(x0) + 2*x0*(x-x0)
令f(x) = 0
得到 x0**2-y + 2*x0*(x-x0) = 0

解出x：   x = y/2*x0 - x0**2/2*x0 + x0 这样把x给估计出来的
求出x后，把这个x的值当做x0把以上步骤都循环一遍，直到精确到0.01

写在python里面：
def sqrt(y, x0):
    if x0 > = y or x0 <= 0:
        return "!"
    else:
        while decimal(abs(x0**2 - y))  < 0.01 :
            x = y/2*x0 - x0**2/2*x0 + x0
            x0 = x
        return x0

不知道我表述清楚没有。。。

luoqing 发表于 2015-8-5 11:49
你这个我没有太看懂诶，a是什么？

面试官当时教我的解法：

你的x就是我的newx，你的y就是我的a。
f(x;x0) = f(x0) + 2*x0*(x-x0) = 0
=> x0^2 - y + 2*x0*x - 2x0^2 = 0
=> 2*x0*x = y+x0^2
=> x = y/(2*x0) + x0/2
就是我代码里的：
newx = (x+a/x)/2
一回事。牛顿法本身就是一阶导数推导出来的。。。

我一开始以为你用的直接展开sqrt（x）做的= =所以，我以为泰勒可能会不收敛。

另，lz如果想开眼界的话，可以google一下：Fast Inverse Square Root
这个东西可以用迭代法瞬间算出1/sqrt(y)，然后再用1除一下。

zan fen xiang~~~~

Is question 1(2) a follow-up of 1(1)? If so, how to do that?

感谢楼主！ 很有帮助

感谢楼主！

Google 的第2题是不是用 Negative Binomial （或者手动推，数字不大）来以 p 表示出 A 赢的期望（给的条件是这个期望是 0.8），求出 p 然后带回 第 1 题来求解。

cgte88586 发表于 2015-10-9 00:59
Is question 1(2) a follow-up of 1(1)? If so, how to do that?

Yes, it is. The interviewer mentioned Bayesian as a hint. I dont know how to do it either

阿骄 发表于 2015-11-21 08:26
感谢楼主！

Google 的第2题是不是用 Negative Binomial （或者手动推，数字不大）来以 p 表示出 A 赢的 ...

可以仔细说一下negative binomial的思路吗？