当前在线人数12826
首页 - 分类讨论区 - 海外生活 - 待字闺中版 - 同主题阅读文章

此篇文章共收到打赏
0

  • 10
  • 20
  • 50
  • 100
您目前伪币余额:0
未名交友
[更多]
[更多]
G's interview, 2 questions
[版面:待字闺中][首篇作者:mscoder] , 2015年08月18日20:20:30 ,1631次阅读,19次回复
来APP回复,赚取更多伪币 关注本站公众号:
[分页:1 ]
mscoder
进入未名形象秀
我的博客
[回复] [回信给作者] [本篇全文] [本讨论区] [修改] [删除] [转寄] [转贴] [收藏] [举报] [ 1 ]

发信人: mscoder (code), 信区: JobHunting
标  题: G's interview, 2 questions
发信站: BBS 未名空间站 (Tue Aug 18 20:20:30 2015, 美东)

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.



--
※ 来源:·WWW 未名空间站 网址:mitbbs.com 移动:在应用商店搜索未名空间·[FROM: 131.]

 
kkuser
进入未名形象秀
我的博客
[回复] [回信给作者] [本篇全文] [本讨论区] [修改] [删除] [转寄] [转贴] [收藏] [举报] [ 2 ]

发信人: kkuser (kkuser!), 信区: JobHunting
标  题: Re: G's interview, 2 questions
发信站: BBS 未名空间站 (Tue Aug 18 20:30:56 2015, 美东)

Is the requirement of the 2nd one to calculate Math.round(1/pow(p, m)) ?
--
※ 来源:·WWW 未名空间站 网址:mitbbs.com 移动:在应用商店搜索未名空间·[FROM: 38.]

 
backstab
进入未名形象秀
我的博客
[回复] [回信给作者] [本篇全文] [本讨论区] [修改] [删除] [转寄] [转贴] [收藏] [举报] [ 3 ]

发信人: backstab (沧海月明), 信区: JobHunting
标  题: Re: G's interview, 2 questions
发信站: BBS 未名空间站 (Tue Aug 18 20:41:24 2015, 美东)

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.

【 在 mscoder (code) 的大作中提到: 】
: 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.




--
如果有来生,要做一棵树;
站成永恒,没有悲欢的姿势。
一半在土里安详,一半在风里飞扬,
一半洒落阴凉,一半沐浴阳光。
非常沉默,非常骄傲,    
从不依靠,从不寻找

※ 来源:·WWW 未名空间站 网址:mitbbs.com 移动:在应用商店搜索未名空间·[FROM: 108.]

 
mscoder
进入未名形象秀
我的博客
[回复] [回信给作者] [本篇全文] [本讨论区] [修改] [删除] [转寄] [转贴] [收藏] [举报] [ 4 ]

发信人: mscoder (code), 信区: JobHunting
标  题: Re: G's interview, 2 questions
发信站: BBS 未名空间站 (Tue Aug 18 20:42:13 2015, 美东)

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

【 在 kkuser (kkuser!) 的大作中提到: 】
: Is the requirement of the 2nd one to calculate Math.round(1/pow(p, m)) ?



--
※ 来源:·WWW 未名空间站 网址:mitbbs.com 移动:在应用商店搜索未名空间·[FROM: 131.]

 
mscoder
进入未名形象秀
我的博客
[回复] [回信给作者] [本篇全文] [本讨论区] [修改] [删除] [转寄] [转贴] [收藏] [举报] [ 5 ]

发信人: mscoder (code), 信区: JobHunting
标  题: Re: G's interview, 2 questions
发信站: BBS 未名空间站 (Tue Aug 18 20:48:18 2015, 美东)

The first one is a variant of the LeetCode's shortest palindrome? 
【 在 backstab (沧海月明) 的大作中提到: 】
: 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



--
※ 来源:·WWW 未名空间站 网址:mitbbs.com 移动:在应用商店搜索未名空间·[FROM: 131.]

 
mscoder
进入未名形象秀
我的博客
[回复] [回信给作者] [本篇全文] [本讨论区] [修改] [删除] [转寄] [转贴] [收藏] [举报] [ 6 ]

发信人: mscoder (code), 信区: JobHunting
标  题: Re: G's interview, 2 questions
发信站: BBS 未名空间站 (Tue Aug 18 20:53:12 2015, 美东)

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
【 在 beast24 (BeastMode) 的大作中提到: 】
: 1. 字母是insert哪里都可以还是只有两端
: 2. is it m + int(1/(1-pow(1-p, m)))



--
※ 来源:·WWW 未名空间站 网址:mitbbs.com 移动:在应用商店搜索未名空间·[FROM: 131.]

 
backstab
进入未名形象秀
我的博客
[回复] [回信给作者] [本篇全文] [本讨论区] [修改] [删除] [转寄] [转贴] [收藏] [举报] [ 7 ]

发信人: backstab (沧海月明), 信区: JobHunting
标  题: Re: G's interview, 2 questions
发信站: BBS 未名空间站 (Tue Aug 18 21:02:28 2015, 美东)

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

【 在 mscoder (code) 的大作中提到: 】
: The first one is a variant of the LeetCode's shortest palindrome? 
: algorithm
: then
: .



--
如果有来生,要做一棵树;
站成永恒,没有悲欢的姿势。
一半在土里安详,一半在风里飞扬,
一半洒落阴凉,一半沐浴阳光。
非常沉默,非常骄傲,    
从不依靠,从不寻找

※ 来源:·WWW 未名空间站 网址:mitbbs.com 移动:在应用商店搜索未名空间·[FROM: 108.]

 
jbamboo
进入未名形象秀
我的博客
[回复] [回信给作者] [本篇全文] [本讨论区] [修改] [删除] [转寄] [转贴] [收藏] [举报] [ 8 ]

发信人: jbamboo (jbamboo), 信区: JobHunting
标  题: Re: G's interview, 2 questions
发信站: BBS 未名空间站 (Tue Aug 18 21:14:17 2015, 美东)

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


【 在 mscoder (code) 的大作中提到: 】
: 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.




--
※ 来源:·WWW 未名空间站 网址:mitbbs.com 移动:在应用商店搜索未名空间·[FROM: 50.]

 
ThinkU
进入未名形象秀
我的博客
[回复] [回信给作者] [本篇全文] [本讨论区] [修改] [删除] [转寄] [转贴] [收藏] [举报] [ 9 ]

发信人: ThinkU (每天想你多一丝), 信区: JobHunting
标  题: Re: G's interview, 2 questions
发信站: BBS 未名空间站 (Tue Aug 18 21:49:34 2015, 美东)

也可以用kmp
翻转字符串加到前面,然后求字符串的kmp值
【 在 backstab (沧海月明) 的大作中提到: 】
: 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



--
※ 来源:·WWW 未名空间站 网址:mitbbs.com 移动:在应用商店搜索未名空间·[FROM: 70.]

 
say543
进入未名形象秀
我的博客
[回复] [回信给作者] [本篇全文] [本讨论区] [修改] [删除] [转寄] [转贴] [收藏] [举报] [ 10 ]

发信人: say543 (Morris), 信区: JobHunting
标  题: Re: G's interview, 2 questions
发信站: BBS 未名空间站 (Thu Aug 20 23:33:56 2015, 美东)

kmp 要怎么解阿? 第一题是随处都可加character 还是只能加在头尾?
--
※ 来源:·WWW 未名空间站 网址:mitbbs.com 移动:在应用商店搜索未名空间·[FROM: 75.]

 
say543
进入未名形象秀
我的博客
[回复] [回信给作者] [本篇全文] [本讨论区] [修改] [删除] [转寄] [转贴] [收藏] [举报] [ 11 ]

发信人: say543 (Morris), 信区: JobHunting
标  题: Re: G's interview, 2 questions
发信站: BBS 未名空间站 (Fri Aug 21 01:26:29 2015, 美东)


【 在 mscoder (code) 的大作中提到: 】
: 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


可以说说怎么得到的吗?
--
※ 来源:·WWW 未名空间站 网址:mitbbs.com 移动:在应用商店搜索未名空间·[FROM: 75.]

 
aiuou
进入未名形象秀
我的博客
[回复] [回信给作者] [本篇全文] [本讨论区] [修改] [删除] [转寄] [转贴] [收藏] [举报] [ 12 ]

发信人: aiuou (aiuou), 信区: JobHunting
标  题: Re: G's interview, 2 questions
发信站: BBS 未名空间站 (Fri Aug 21 02:16:09 2015, 美东)

可以讲讲怎么算的吗?
我算的是1/(p^m)*(1-1/(p^m*(1-p)))+2m

找到了https://courses.cit.cornell.edu/info2950_2012sp/mh.pdf
你算的是对的,厉害。


【 在 mscoder (code) 的大作中提到: 】
: 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




--
※ 修改:·aiuou 於 Aug 21 02:57:41 2015 修改本文·[FROM: 107.]
※ 来源:·WWW 未名空间站 网址:mitbbs.com 移动:在应用商店搜索未名空间·[FROM: 107.]

 
hplp
进入未名形象秀
我的博客
[回复] [回信给作者] [本篇全文] [本讨论区] [修改] [删除] [转寄] [转贴] [收藏] [举报] [ 13 ]

发信人: hplp (hplp), 信区: JobHunting
标  题: Re: G's interview, 2 questions
发信站: BBS 未名空间站 (Fri Aug 21 02:39:54 2015, 美东)

LZ这是一轮电面吗?

【 在 mscoder (code) 的大作中提到: 】
: 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.




--
※ 来源:·WWW 未名空间站 网址:mitbbs.com 移动:在应用商店搜索未名空间·[FROM: 50.]

 
wzy0791
进入未名形象秀
我的博客
[回复] [回信给作者] [本篇全文] [本讨论区] [修改] [删除] [转寄] [转贴] [收藏] [举报] [ 14 ]

发信人: wzy0791 (阿毛牛), 信区: JobHunting
标  题: Re: G's interview, 2 questions
发信站: BBS 未名空间站 (Fri Aug 21 02:44:33 2015, 美东)

我来说一下第二个题,作为一个面试题的话,那简直难到爆炸。是我们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的很多高级性质,简单推导的话主要是用conditioning,我
估计LZ在简历说了自己概率或者数学很厉害什么的,我很难想象面试能有这种题!!!
面试官黑的漂亮!!!


--
※ 修改:·wzy0791 於 Aug 21 13:29:18 2015 修改本文·[FROM: 64.]
※ 来源:·WWW 未名空间站 网址:mitbbs.com 移动:在应用商店搜索未名空间·[FROM: 64.]

 
mscoder
进入未名形象秀
我的博客
[回复] [回信给作者] [本篇全文] [本讨论区] [修改] [删除] [转寄] [转贴] [收藏] [举报] [ 15 ]

发信人: mscoder (code), 信区: JobHunting
标  题: Re: G's interview, 2 questions
发信站: BBS 未名空间站 (Fri Aug 21 12:24:21 2015, 美东)


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.


【 在 wzy0791 (阿毛牛) 的大作中提到: 】
: 我来说一下第二个题,作为一个面试题的话,那简直难到爆炸。是我们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在简历说了自己概率或者数学很厉害什么的,
: ...................



--
※ 来源:·WWW 未名空间站 网址:mitbbs.com 移动:在应用商店搜索未名空间·[FROM: 131.]

[分页:1 ]
[快速返回] [ 进入待字闺中讨论区] [返回顶部]
回复文章
标题:
内 容:

未名交友
将您的链接放在这儿

友情链接


 

Site Map - Contact Us - Terms and Conditions - Privacy Policy

版权所有,未名空间(mitbbs.com),since 1996