Uber10.14电面

刚结束的电面
直接上题
find all possible palindromic subsequence in a giv

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

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

-10-15 06:48):
还是个国人大哥面的，唉

f1371342385 发表于 2015-10-16 12:12
LZ，是返回多少个还是所有的组合，如果是number的话，可以用dp来解决。但是是所有的组合。。。那就不会了

所有的组合其实还是dp 只不过矩阵每个元素是个list而不是number

ChloeF 发表于 2015-10-16 10:03
是这个咩？http://www.geeksforgeeks.org/dynamic-programming-set-12-longest-palindromic-subsequence/

恩 后来想了一下 基本上这个改进一下就行

ChloeF 发表于 2015-10-16 10:03
是这个咩？http://www.geeksforgeeks.org/dynamic-programming-set-12-longest-palindromic-subsequence/

这个是最长啊，题目不是all 吗？

brute force？ 枚举？这是FB某个面经题吗？

这题感觉很难啊

补充内容 (2015-10-15 06:21):
bless楼主。
楼主能否说下这题要怎么用DP呢？

我感觉很类似FB某个面经题，以每一位为中心枚举

majiamajia 发表于 2015-10-15 06:20
我感觉很类似FB某个面经题，以每一位为中心枚举

枚举就是brutal force吗？复杂度O(n^2）吗？

dylanwen 发表于 2015-10-15 06:24
枚举就是brutal force吗？复杂度O(n^2）吗？

对的感觉是这样N^2的复杂度

majiamajia 发表于 2015-10-15 06:34
对的感觉是这样N^2的复杂度

枚举subsequence到不了n^2吧？如果能也不用dp了

ImGoingSSJ 发表于 2015-10-15 06:36
枚举subsequence到不了n^2吧？如果能也不用dp了

worst case 。。恩DP其实也还好啊就是还要额外的space?

majiamajia 发表于 2015-10-15 06:37
worst case 。。恩DP其实也还好啊就是还要额外的space?

枚举应该是2^n吧，对每个char都是有或者没

subsequence 还是 substring? 如果是substring 枚举的话也就 O(n2)吧 开个布尔二位数记录一下str[i...j]是不是就完了。要是subsequence那就不一样了