Google电面

今天下午面的Google 全职电面 面试官感觉像个国人大哥 挺nice的 题也不难 但是一开始想复杂了

给两个长度一样的string A，B  把他们对齐切一刀 这样就得到了A1 A2 B1 B2 四个substring
写一个func check 能不能找到这一刀  A1和B

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

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

的时候把速度放慢了点 顺带着解释 虽然也没啥好解释的 就尽量interact 所以后面没啥时间 followup时候就讲了idea怎么实现 没具体写code了 希望能给个旅游的机会吧

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

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

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

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

Follow up是枚举所有切法，然后选出最长的palindrome ?

对其切的话怎么样用two pointer呢？ 难道不需要枚举所有的切法吗 求提示

wtcupup 发表于 2019-2-2 15:32
Follow up是枚举所有切法，然后选出最长的palindrome ?

就是如果A B的切口可以不在同一个地方 然后找拼出来的最长的palindrome 我当时给的解法也是双指针 感觉不需要枚举呀

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

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

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

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

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

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

祝好运