Google Intern 跪经

第一次店面 凉凉
Q1: 有字符串 S1， S2 问通过S2删除一

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

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

一个没有存在在database的电话

第一题, 只是面试需要的话, O(nd)的算法可以, d是n的divisor的个数. 高级一点可以O(n)时间.

要解决两个问题:
1. 找到最长的prefix of s1, such that it is a subsequence of s2.
这个可以直接extend lc的392. https://leetcode.com/problems/is-subsequence/ 让这步骤获得的prefix的长度为m.

2. 找到最长的prefix of s1, s3, such that it has length <=m, 然后 s3^k = s1 for some k. 这个s3就是答案.
这个有两个方法, 面试的时候用傻方法就可以了. 找到n的所有的divisor, 比如d是n的divisor, 然后测试s1[0..d-1]是否满足要求. 因为n的divisor的个数=O(n^epsilon) for any positive epsilon. 所以这部分可以O(n^epsilon * n)=O(n^{1+epsilon})时间搞定.

另一个稍微高级一点. 需要的知道一个定理. 对于string s, 如果t^k = s, 则我们说|t|是s的一个period.

定理: p和q是一个string s的period, 则gcd(p,q)也是s的period.

这样的话, 你只要做的是找到最短的period p. 然后找到n的divisor里比m小的然后可以被p整除的最大数.
所以难点就是找到最短的period. 但这个是算法领域里很常见的问题. 这个的话看看这个stackoverflow的post跟着找就好. https://stackoverflow.com/questi ... ng-t-such-that-tm-s