美国今日头条跪经

面试官国人大哥,上来常规聊天，让说了一下自己的工作经验和相关经历。然后做题，是一道经过修改的难题， 感觉更难了。

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

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

因为之前没做过，所以就没写完。给我的一种感觉就是中国公司面试bar 更高？ 希望对大家有帮助，求多多加米

烂花子。。。。。

这个最优不是应该让考官定义的吗？还是说最优的定义也是问题的一部分?

个人感觉相乘会更好吧 相当于找到概率乘积和最大的那个.. bfs和dfs都可以做吧..如果最优是出现概率最大的话

rpmy 发表于 2019-11-12 20:17
这个最优不是应该让考官定义的吗？还是说最优的定义也是问题的一部分?

最优的定义也是问题的一部分

randallhong 发表于 2019-11-12 21:18
个人感觉相乘会更好吧 相当于找到概率乘积和最大的那个.. bfs和dfs都可以做吧..如果最优是出现概率最大的话 ...

最优确实概率最大

相乘会有个问题
比如，对于一个 sentence S=[W1,W3,..,Wn]
score(s) =  p(W1) * p(W2)*...*p(Wn)

score(s)  最后会over flow, 如果 Word probabiloity 都很小，比如等于0.00000001 ， 而且n 很大 比如 n=100.


相加和 相乘是一样的，相当于
log(score(s)) = log( p(W1) * p(W2)*...*p(Wn)) = log( p(W1) ) + log( p(W2) ) + ... + log( p(Wn) )

相加相当于我们最后求 log(score(s)) 的最优

直接求和与求了log之后求和是不一样的啊。0.8+0.0000001 > 0.1+0.1 但是明显后者出现概率更大啊。

huorili 发表于 2019-11-13 18:22
直接求和与求了log之后求和是不一样的啊。0.8+0.0000001 > 0.1+0.1 但是明显后者出现概率更大啊。

有道理。那不应该直接求和。

但是为了防止多个小的浮点数相乘溢出，对每个概率取log 相加比较make sense
log(0.8) + log(0.0000001) = -7.1  < log(0.1) + log (0.1) = -2

我觉得不需要找到所有的可以分成的句子，而是直接DP，dp[i] 表示前i个字母可以分成的概率最大的句子，之后每加一个单词就往回去找新构成的单词(k到i)的概率*dp[i - k]。同时用另外一个path array记录当前这个i是由上一个的哪一个最优跳过来的。