新鲜G家店面

今天下午刚店面完~~
题目比较简单。
找出最长的回文。

因为内存放不下， 要写一个api获取下一段，只要简单的写一下s

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

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

题结束了。。。

感觉没戏了，但是还是求给个下一轮吧。。。

楼主，我有一笨招，请指教；

其实就是定义一个回文的压缩方式，比如 $a,121$,就是说有个回文，两头是a,长度是121，中间是什么东西我们不care.
然后一段一段读，dp求解，然后压缩，成为 $a,121$cd$f,27$..., 这样的，长度短很多了。然后可以再dp，把我们定义的压缩方式看成一个新字符,再压缩，
处理下一段。
反复折腾，最后是收敛的，而且可以放在内存里。
找最长的那个。

houqingniao 发表于 2016-12-16 04:10
当时我也想到只存两头信息，感觉不对头就没说。

这问题很诡异，网上能找到一篇论文，
Palindrome Recognition In The Streaming Model
问题应该是有解的，但是作为电面，想不通为什么问这个问题，感觉太专业了。
楼主是研究算法的?

2008 发表于 2016-12-16 00:30
楼主，我有一笨招，请指教；

其实就是定义一个回文的压缩方式，比如 $a,121$,就是说有个回文，两头是a, ...

我觉得不可以压缩，压缩了以后你丢失了一些信息了，万一后面有匹配的怎么办

同求大神解答，，几个TB的数据流，内存放不下，怎么找最大回文？

同想知道。。。

祝楼主好运！谢谢分享！

补充内容 (2016-12-15 23:57):
http://stackoverflow.com/questio ... b-linear-space-time 网搜了一下，感觉超难啊，楼主估计面试官也不会啊


补充内容 (2016-12-15 23:58):
http://stackoverflow.com/questio ... b-linear-space-time 网搜了一下，感觉超级难，估计面试官也不会。

edyyy 发表于 2016-12-15 23:52
祝楼主好运！谢谢分享！

补充内容 (2016-12-15 23:57):

多谢。
这图灵机都出来了。。。
真是没想法 哈哈

houqingniao 发表于 2016-12-16 01:27
我觉得不可以压缩，压缩了以后你丢失了一些信息了，万一后面有匹配的怎么办

哦，没错，不能压缩。或者至少，我刚才说的压缩方法是不对的。

2008 发表于 2016-12-16 02:05
哦，没错，不能压缩。或者至少，我刚才说的压缩方法是不对的。

当时我也想到只存两头信息，感觉不对头就没说。