G's interview, 2 questions

1: Given a string S, return minimum number of chars that you can add to its

您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies
esult is not integer, round it.

zq13667243992 发表于 2015-8-29 10:30
第二题不就是m/p吗？？

不是。pE(k)=E(k-1)+1，其中p是正面朝上的概率，E(k)是出现连续K次朝上的期望，E(0)=0。

uikos 发表于 2015-9-7 01:09
不是。pE(k)=E(k-1)+1，其中p是正面朝上的概率，E(k)是出现连续K次朝上的期望，E(0)=0。

正解。。这题作为电面也太难了点。。
1.explanation：http://stats.stackexchange.com/q ... ive-heads-on-a-coin
2.closed form solution ：http://www.quora.com/What-is-the ... -two-heads-in-a-row

ChrisGates23 发表于 2015-8-29 09:16
请问lz第一题是否可转化为从S的末尾往前找最长的palindrome，复杂度O(nm), n是S的长度，m是子串的长度。

我觉得和lc上边那道shortest palindrome很像

请问lz第一题是否可转化为从S的末尾往前找最长的palindrome，复杂度O(nm), n是S的长度，m是子串的长度。

“m (>= 1) heads in a row” 是指连续m个head吗

请问第二题不是一个数学概率问题吗？为什么要write function?

第二题不就是m/p吗？？

第一个题把string reverse，kmp求失配函数。 复杂度O(n).

ChrisGates23 发表于 2015-8-29 09:16
请问lz第一题是否可转化为从S的末尾往前找最长的palindrome，复杂度O(nm), n是S的长度，m是子串的长度。

O(n)，用法KMP