狗家电面

周二面的狗家电面。对面是个小姐姐，上来干净利索开始做题，没有自我介绍的时间。
题目是给定两个string，source 和 target，用source的多个copy拼接成target，但是拼接的过程中可以删掉source的一些字符再拼接（也就是不连续的子串）。
1. 什么情况下肯定可以拼出target？
2. 最少用多少个source的copy。
Example：
source = 'QWRTYE'
target = 'QTRYEQW' = 'Q##T##' + '##R#YE' + 'QW####'
所以就是用到3个source的copy。

我的解答：
1. 把source的所有字符加到一个set里，然后遍历target，如果target中出现了source没有

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

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

象分。

现在已经第二天过去啦。。。还没有收到onsite。。。有点焦虑。。。希望如果对方觉得面的不好起码给个加面吧。。。要直接挂了进冷冻期就惨了。。。

顺便问下大家fulltime收到电面的，是不是三天内没消息就不太妙了啊

Map<Character,List< Integer>>map : key<character> value<这个char 出现的index>
for(char ch : source) build map;
for(char ch : target) -> 用二分查找去找尽量小的index -> 保证可以保证每次走的路径最长。

楼主，
我觉得小姐姐的说的优化是时间复杂度上的优化，侧重点不是时间效率
应该用Binary search 来优化嵌套for loop.
变成N(LogM).

lovemyisa 发表于 2018/11/17 01:25:37
楼主，
我觉得小姐姐的说的优化是时间复杂度上的优化，侧重点不是时间效率
应该用Binary search 来优化嵌套for loop.
变成N(LogM).

茅塞顿开，学习啦！

我觉得小姐姐虽然提醒得有点儿明显~
我觉得你最差就是加面。因为code写完了
不过还是祝你可以拿到onsite！！！！