Facebook面经 9/27

mayuaner 发表于 2016-9-29 03:00
问了，我说是On^2. 但是不知道我的dp和大家写的是不是一样，不过也已经过去了。应该是多少呢?

我觉得也是

DreamBoy 发表于 2016-9-29 03:40
我觉得也是

O(n^3), 算hash code 时候要O(n)

huai10 发表于 2016-10-8 16:40
O(n^3), 算hash code 时候要O(n)

请问是什么意思？能详细说说吗

forestwn 发表于 2016-10-8 17:30
请问是什么意思？能详细说说吗

一般我们认为hash table 用string做key是O(1)，但其实它要用每一个char去算hash code

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

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

huai10 发表于 2016-10-8 17:48
一般我们认为hash table 用string做key是O(1)，但其实它要用每一个char去算hash code

如果这么算的话 string的比较也是O(K) 和hash table 本身没有关系

forestwn 发表于 2016-10-8 18:30
如果这么算的话 string的比较也是O(K) 和hash table 本身没有关系

并不懂为啥word break需要string比较

huai10 发表于 2016-10-8 22:21
并不懂为啥word break需要string比较

你是对的 我上面是想说 如果按照char比较为O(1)的话 hash和比较都变成O(K) 是general来说 和这题木关系
感谢分享你的想法 有道理 :)

是的。当时说的是On2加上hash和substring等的时间。

leixiang5 发表于 2016-9-28 07:08
- -没有啊..add and search word...也就60来行啊....你们一写玩...面试官直接给下一道?

这题他问你followup了吗？支持"*"的匹配