Google电面

漫漫人生路 发表于 2019-2-3 09:46
嗯，不同字母之前切，不过，需要s1， s2跟s2， s1都试一遍。

对的 是得要镜像都来一次

请问电话面试面试官怎么给出题目呢？是纯语言描述吗？还是会发送给你一段类似于leetcode题目描述的那种文字？谢谢

richpanda 发表于 2019-2-3 02:57
这道题考双指针的灵活用法。先只考虑a1b2的情况（另外那种情况a2b1是对称的，互换一下s1和s2就可以了。）双 ...

s2那个指针不用跳到s1去吧?

伊万卡 发表于 2019-2-4 22:33
请问电话面试面试官怎么给出题目呢？是纯语言描述吗？还是会发送给你一段类似于leetcode题目描述的那种文字 ...

会复制文字到google doc上的

请问下楼主电面是1小时吗

follow up是有O(n)的解的，关键点是不一样了选A还是B切，然后切在什么地方。
切肯定是以不一样了的那个char开始的在长的回文除，而找longest prefix parlindrome可以先flip string，然后用KMP找longest identical suffix，因为回文flip以后和原本的回文还是一样的。参考里扣214

henryqcy 发表于 2019/02/07 20:37:38
follow up是有O(n)的解的，关键点是不一样了选A还是B切，然后切在什么地方。
切肯定是以不一样了的那个char开始的在长的回文除，而找longest prefix parlindrome可...

你讲的应该是对的，就是这个LC214 的kmp o（n）解法。之前想错到LC5去了，结果不敢把这个string reverse了。这道电面题follow up不错！

follow up 用 马拉车 来处理剩下的字符串。
比如 A 切在 index 3, 我们对A[3]之后的跑马拉车，然后马拉车中，遍历每个中心，遇到每个中心对应的回文半径能覆盖到A[4]的, 则证明这是从A[4]开始的最长回文，更新最长回文。
对B也做一遍，比较两个最长回文然后判断怎么切。

最后时间不到followup没写会有问题吗

qqaas 发表于 2019-2-7 18:49
请问下楼主电面是1小时吗

40到45分钟吧