FB2017新鲜面经

感觉面试官很着急，所以题目比较简单： input是一个string，求出所有可能的大小写组合。 比如ab 返回：Ab，ab，aB，AB
DFS简单明了，唯一需要注意就是input包含punctuation之类的情况要考虑到。
时间复杂度，2^n

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

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

，做题加follow-up大概半小时不到，他就急急说题做完了，你有问题吗？- -
等结果，攒人品，求保佑🙏，同时祝大家也一切顺利早日拿offer

“我用string 存储中间的string 变化过程，Ab，问题是这样占用内存比较多为什么?”
不太明白，所有可能结果不是要返回吗？这样不是无论如何都会占指数内存吗
另外10^18大概是亿分钟不是一分钟吧...

这个应该可以用记忆化搜索提高到n^2吧 用一个cache来存substring的结果

sfsttz 发表于 2017-5-10 15:55
“我用string 存储中间的string 变化过程，Ab，问题是这样占用内存比较多为什么?”
不太明白，所有可能结 ...

感觉 10^18 是  10^9 second    按照 一个操作10^-9 s 来看，这样对不？

好厉害好厉害！！！！

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

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

whyz 发表于 2017-5-11 00:41
这个应该可以用记忆化搜索提高到n^2吧 用一个cache来存substring的结果

没懂，怎么优化，没有需要记忆的地方啊？求解释

sfsttz 发表于 2017-5-10 15:55
“我用string 存储中间的string 变化过程，Ab，问题是这样占用内存比较多为什么?”
不太明白，所有可能结 ...

求大神解释，不懂

smallwarm 发表于 2017-5-11 00:53
感觉 10^18 是  10^9 second    按照 一个操作10^-9 s 来看，这样对不？

我也不懂，为啥？

snowboardingpig 发表于 2017-5-14 14:48
我也不懂，为啥？

这就是个大概估算，

https://discuss.codechef.com/que ... hin-the-time-limits