推特 电面

刚刚面完的电面，先聊简历和一个project聊了很久，一道题，给两个字符串s1和s2，找出s2的任何permutation第一次

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

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

O(n2)。面试官问有没有更优的解法，没想出来。。感觉要跪

mmmfighting 发表于 2017-5-10 11:53
上上周约的

这题是利口无硫其

mmmfighting 发表于 2017-5-10 11:55
因为不满足条件的话还要copy一下原来的map，所以是O(n^2)

用slide window，如果不匹配不需要完整恢复整个map，只需要把s1开始匹配的第一个再恢复到map里面去就好了，所以时间复杂度还是O(n)

whyz 发表于 2017-5-9 10:18
这题是不是可以用sliding window做 然后是O(n)?

可以详细讲一下吗？用sliding window也是要修改map的，如果不满足还要恢复map，最坏情况不应该是O((m-n)*n)吗？m,n分别是两个字符串长度

这题是不是可以用sliding window做 然后是O(n)?

这题好像是lc原题

楼主什么时候约的电面啊

楼主的意思是统计s2 的frequency 然后s1里用双指针找正好覆盖frequency的子串吗？这样是O(n)呀

楼主是投的社招吗？

维护一个s2长度的窗口，统计一下字母的频率即可

sfsttz 发表于 2017-5-9 13:13
楼主的意思是统计s2 的frequency 然后s1里用双指针找正好覆盖frequency的子串吗？这样是O(n)呀

最坏情况下是kn吧 当k=n的时候还是o(n^2)

jsgq 发表于 2017-5-9 12:26
楼主什么时候约的电面啊

上上周约的