谷狗新鲜店面

刚刚店面完 感觉gg 都怪自己太紧张 写的时候太多bug 其实题目很简单
电话10点准时打来，然后一开始问了我一下intern还有project的东西，接着就直接做题了。
题目是

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

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

这个题应该很简单了，可是当时做的时候太紧张了， 就一直在debug。。。。。

求加大米！！

byfwh 发表于 2018-12-10 00:06
感谢楼主提供思路
请问这样下来为什么是O(n*m)呢
判断一个substring存不存在第二个里面是O(m^2) (不用 ...

题目说能够从str2中移走任意数目的字符，也就是说能用来匹配str的不是str2的substring，而是（非连续的）subsequence。方法就是在str当前还未被匹配的部分中，不停地找能够匹配subsequence of str2的最长前缀。在str中找一个能匹配str2子序列的前缀的naive算法需要用时O(m)；最坏情况下，每个匹配部分的长度都为1，也就是说总共要进行O(n)次匹配。所以总时间是O(nm)。

雨雪霏霏 发表于 2018-11-29 03:37
你好 我认为substring贪心是错误的 比如
str1: abcca
str2: acb

请问这样做对吗

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

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

一点想法，如果修改后的s2 (记作ms2)要能重构成s1，那么ms2一定要是s1的前缀。从所有可能构成s1前缀的ms2出发，由长到短，且ms2需要满足：s1长度是这些前缀长度的整倍数k倍。匹配ms2 k倍，如果存在，倍数k即为答案，如果不行，试长度-1的另一个ms2，如果长度为1都不行，那就是不存在。

举个例子：

1. 
   
2. // s1 = "BABBABBABBAB" (len1 = 12)
   
3. // s2 = "CCBABB" (len2 = 6)
   
4. // true, 4
   
5. 
   
6. // start from length 6, prefix of s1 is "BABBAB", we can't find it in s2, skip
   
7. // start from length 5, 12 is not k times of 5, skip
   
8. // start from length 4, prefix of s1 is "BABB", which is a subsequence of s2
   
9. //  then we compare, BABB | ABBA | BBAB ， 2nd length 4 substring not match, skip
   
10. // start from length 3, prefix of s1 is "BAB", which is a subsequence of s2
    
11. //  then we compare, BAB | BAB | BAB | BAB ，all length 3 substring match, return value 12 / 3 = 4
    
12. 
    
13. // if we get to length 1 prefix of s1, still does't match, we know there is not solution
    
14. 
    
15. // time complexity, at worse check  O(len2) times, each comparison, will take O(len1), so it should be O(len1 * len2)
    
16. 
    

复制代码

第二问没有头绪啊…想用贪心算法但是不确定是不是最优，能证明吗？

lukuang 发表于 2018-11-28 03:27
第二问没有头绪啊…想用贪心算法但是不确定是不是最优，能证明吗？

第二题我是用了iterative的就直接用loop去check那个第一个的substring是不是存在在第二个里面，当时面试的小哥是这么提示我的
最后下来runtime是O(n*m) n是str1的length m是str2的length
看起来好像不是最优的样子。。。

26号也面了这一道…一模一样

lukuang 发表于 2018-11-28 03:27
第二问没有头绪啊…想用贪心算法但是不确定是不是最优，能证明吗？

第二题贪心应该是最优的
因为如果str[i:i+j] 可以被 str2[k:k+j] match而且是最长match 那么 str[i+1:i+j] 一定可以被 str2[k+1:k+j] match
所以str[i]这一位如果被贪心match到前面去了，不会影响总的min number

shanshanlate 发表于 2018-11-28 03:59
第二题我是用了iterative的就直接用loop去check那个第一个的substring是不是存在在第二个里面，当时面试 ...

感觉你这个解法基本算是暴力解法？不过还是感谢回复！有人也回复我了说贪心好像是最优的，你也可以看看？我觉得可以讨论一下。

zigchg 发表于 2018-11-28 04:30
第二题贪心应该是最优的
因为如果str 可以被 str2[k:k+j] match而且是最长match 那么 str 一定可以被 st ...

有道理，谢谢！

请问str2有dup的characters吗？ 感觉如果没有的话可以直接用hashmap记录char和index 直接match str1

zigchg 发表于 2018-11-28 04:30
第二题贪心应该是最优的
因为如果str 可以被 str2[k:k+j] match而且是最长match 那么 str 一定可以被 st ...

你好 我认为substring贪心是错误的 比如
str1: abcca
str2: acb
最优解应该是4 因为str1[0:2]可以由str2的a,b构成
贪心的话只能匹配substring 而不是subsequence
当然如果是贪心匹配subsequence那肯定是对的...

三周前也面了这一道！一模一样