CNB Crystal DP - 未名空间MITBBS历史存档

国际科技财经博客移民网络热点娱乐民生时事公众号

Redian新闻

>未名空间

>Money - 海外理财

CNB Crystal DP

CNB Crystal DP# Money - 海外理财

m*r2019-01-12 08:01

1 楼

1: Given a string S, return minimum number of chars that you can add to its
back to obtain a palindrome. Explain the complexity
2: Write a function to return expected number of tosses of an unbiased or
biased coin until there are m (>= 1) heads in a row,supposing the head
probability in a toss is p: 0 < p <= 1. If the result is not integer, round
it.

i*92019-01-12 08:01

2 楼

19年1月1号的 AA gift card 在11号报销了，4张同时
微信支付算作unknown transportation, 拿不到3个点。

k*r2019-01-12 08:01

3 楼

Is the requirement of the 2nd one to calculate Math.round(1/pow(p, m)) ?

t*u2019-01-12 08:01

4 楼

zan
赶紧下蛋了

【在 i*****9 的大作中提到】

: 19年1月1号的 AA gift card 在11号报销了，4张同时
: 微信支付算作unknown transportation, 拿不到3个点。

b*b2019-01-12 08:01

5 楼

1. if you remember the Manacher’s Algorithm, then first use that algorithm
to find the longest palindrome string end at last char of given string, then
result is S.lenght - length of longest palindrome string end at last char.
use Manacher's algo, it's O(n).
2. 2nd floor's answer seems correct to me.

its
round

【在 m*****r 的大作中提到】

: 1: Given a string S, return minimum number of chars that you can add to its
: back to obtain a palindrome. Explain the complexity
: 2: Write a function to return expected number of tosses of an unbiased or
: biased coin until there are m (>= 1) heads in a row,supposing the head
: probability in a toss is p: 0 < p <= 1. If the result is not integer, round
: it.

c*f2019-01-12 08:01

6 楼

3号买的，11页报了。

【在 i*****9 的大作中提到】

: 19年1月1号的 AA gift card 在11号报销了，4张同时
: 微信支付算作unknown transportation, 拿不到3个点。

m*r2019-01-12 08:01

7 楼

"toss until there are m (>= 1) heads in a row"
So, 1/pow(p, m) is not right!

【在 k****r 的大作中提到】

: Is the requirement of the 2nd one to calculate Math.round(1/pow(p, m)) ?

g*e2019-01-12 08:01

8 楼

多少面额的？

【在 i*****9 的大作中提到】

: 19年1月1号的 AA gift card 在11号报销了，4张同时
: 微信支付算作unknown transportation, 拿不到3个点。

b*42019-01-12 08:01

9 楼

1. 字母是insert哪里都可以还是只有两端
2. is it m + int(1/(1-pow(1-p, m)))

d*o2019-01-12 08:01

10 楼

去年11月买的又可以买了？

m*r2019-01-12 08:01

11 楼

The first one is a variant of the LeetCode's shortest palindrome?

algorithm
then
.

【在 b******b 的大作中提到】

: 1. if you remember the Manacher’s Algorithm, then first use that algorithm
: to find the longest palindrome string end at last char of given string, then
: result is S.lenght - length of longest palindrome string end at last char.
: use Manacher's algo, it's O(n).
: 2. 2nd floor's answer seems correct to me.
:
: its
: round

c*y2019-01-12 08:01

12 楼

这个卡，加副卡，一定要ssn吗？

m*r2019-01-12 08:01

13 楼

2. It seems to be round ( (1.0 - p^m) / (p^m*(1.0-p)) ) when 0 < p <1;
When p = 1, it's clearly m

【在 b*****4 的大作中提到】

: 1. 字母是insert哪里都可以还是只有两端
: 2. is it m + int(1/(1-pow(1-p, m)))

b*b2019-01-12 08:01

14 楼

that's my understanding, but i can be wrong, :)

【在 m*****r 的大作中提到】

: The first one is a variant of the LeetCode's shortest palindrome?
:
: algorithm
: then
: .

j*o2019-01-12 08:01

15 楼

m heads in a row是指连续m个heads吗？

its
round

【在 m*****r 的大作中提到】

T*U2019-01-12 08:01

16 楼

也可以用kmp
翻转字符串加到前面，然后求字符串的kmp值

algorithm
then
.

【在 b******b 的大作中提到】

s*32019-01-12 08:01

17 楼

kmp 要怎么解阿? 第一题是随处都可加character 还是只能加在头尾?

s*32019-01-12 08:01

18 楼

可以说说怎么得到的吗?

【在 m*****r 的大作中提到】

: 2. It seems to be round ( (1.0 - p^m) / (p^m*(1.0-p)) ) when 0 < p <1;
: When p = 1, it's clearly m

a*u2019-01-12 08:01

19 楼

可以讲讲怎么算的吗？
我算的是1/(p^m)*(1-1/(p^m*(1-p)))+2m
找到了https://courses.cit.cornell.edu/info2950_2012sp/mh.pdf
你算的是对的，厉害。

【在 m*****r 的大作中提到】

: 2. It seems to be round ( (1.0 - p^m) / (p^m*(1.0-p)) ) when 0 < p <1;
: When p = 1, it's clearly m

h*p2019-01-12 08:01

20 楼

LZ这是一轮电面吗？

its
round

【在 m*****r 的大作中提到】

w*12019-01-12 08:01

21 楼

我来说一下第二个题，作为一个面试题的话，那简直难到爆炸。是我们graduate概率课
的一个例子，做为一道一小时完成的ECE qualify题目完全是有可能的。这个题叫做
First Occurrence of Successive Hits。
Let y_m 表示题目要求的，flip出m个head需要的平均次数（期望）。
To analytically get y_m，需要下面这个recurrence equation：
y_m = y_{m-1}/p + 1/p
初始条件，y_1 = 1/p (其实算出这个初始条件都不简单了，你需要知道 geometric
random variable 的特殊性质，不信你试试看。。。)
这题答案看上去很简单，但是要得到那个recurrence equation是很花时间的，要用到
expectation的很多高级性质，我估计LZ在简历说了自己概率或者数学很厉害什么的，
我很难想象面试能有这种题！！！面试官黑的漂亮！！！

m*r2019-01-12 08:01

22 楼

It took a while to come up the following solution.Yep, it should be a PHD
qualify题目.
Let X be number of tosses. Let q = 1-p
First, if p = 1, then, clearly E(X) = m.
Suppose 0 < p < 1. We can calculate the expectation E(X) via conditioning
Let t_i be the result of the i-th toss
Consider using telescoping by observing that
E(X) = E(X|t_1 = H)p + (E(X)+1)q
E(X|t_1 = H) = E(X|t_1 = H,t_2 = H)p + (E(X)+2)q
E(X|t_1 = H,t_2 = H) = E(X|t_1 = H,t_2 = H,t_3 = H)p + (E(X)
+3)q
...
E(X|t_1 = H,t_2 = H, ..., t_m-1 = H) = mp + (E(X)+m)q
Note that
E(X) = E(X|t_1 = H)p + (E(X)+1)q
E(X|t_1 = H)p = E(X|t_1 = H,t_2 = H)p^2 + (E(X)+2)qp
E(X|t_1 = H,t_2 = H)p^2 = E(X|t_1 = H,t_2 = H,t_3 = H)p^3 + (E(
X)+3)qp^2
...
E(X|t_1 = H,t_2 = H, ..., t_m-1 = H) = mp^m + (E(X)+m)qp^(m-1)
By telescoping,
E(X) = mp^m + (E(X)+1)q + (E(X)+2)qp + ... + (E(X)+m)qp^(m-1)
= mp^m + E(X)(q + qp + ... + qp^(m-1)) + (q + 2qp + ... + mqp^(m-1))
= mp^m + E(X)sum{qp^(k-1): k = 1,..., m} + sum{kqp^(k-1): k = 1,..., m}
Solve for E(X) yields
E(X) = (mp^m + sum{kqp^(k-1): k = 1,..., m}) / (1 - sum{qp^(k-1): k = 1,...,
m})
= (mp^m + q*sum{kp^(k-1): k = 1,..., m}) / (1 - q*sum{p^(k-1): k = 1,..
., m})
= (mp^m + q*s) / (1 - q*t),
where
s = sum{kp^(k-1): k = 1,..., m}
and
t = sum{p^(k-1): k = 1,..., m}
Since
s = (1 - (m+1)p^m + p(1-p^m)/(1-p)) / (1-p)
t = (1-p^m) / (1-p)
We can further simplify E(X) into E(X) = (1-p^m) / (p^m*(1-p))
In the 45 minutes session, I only reached E(X) = (mp^m + q*s) / (1 - q*t)
and was told time was running out. But I told this E(X) can be simplified.
Not sure whether the guy followed or not.

【在 w*****1 的大作中提到】

: 我来说一下第二个题，作为一个面试题的话，那简直难到爆炸。是我们graduate概率课
: 的一个例子，做为一道一小时完成的ECE qualify题目完全是有可能的。这个题叫做
: First Occurrence of Successive Hits。
: Let y_m 表示题目要求的，flip出m个head需要的平均次数（期望）。
: To analytically get y_m，需要下面这个recurrence equation：
: y_m = y_{m-1}/p + 1/p
: 初始条件，y_1 = 1/p (其实算出这个初始条件都不简单了，你需要知道 geometric
: random variable 的特殊性质，不信你试试看。。。)
: 这题答案看上去很简单，但是要得到那个recurrence equation是很花时间的，要用到
: expectation的很多高级性质，我估计LZ在简历说了自己概率或者数学很厉害什么的，