狗家电面

周二面的狗家电面。对面是个小姐姐,上来干净利索开始做题,没有自我介绍的时间。
题目是给定两个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没有的字符,那肯定拼不出来,否则肯定能拼出来(最差情况每次取一个字符嘛)。
  2. 贪心算法,二重循环,从target的头开始依次在source中寻找匹配,并且用一个bool的数组来标记当前target的字符是不是已经被匹配了。
    代码大概就是这样,仔细看了一眼还是有小bug的,不过基本思路就是这样了。
    for i in range(len(target)):
    if target[i] 被访问过:
    continue
    ptr = i
    for j in range(len(source)):
    while target[ptr] 被访问过 and ptr < len(target):
    ptr += 1
    if source[j] == target[ptr]:
    target[ptr]标记为已访问
    ptr += 1

然后小姐姐问我有没有什么improvement,没想出来,然后她让我写几个test case,写了5,6组,包括两个字符串为空的情况,包括source只有一个字符串的情况,包括两个字符串相等的情况。
然后她说你看着这些test case,能不能想到什么改进,我说可以加一些细节的判断,比如先判断了一定可以拼成target之后,如果发现source就一个字符,就直接返回target的长度不需要循环。

感觉面试时还是太紧张了。。。写了两三个typo,把set([])直接写成了(),第二段代码她没帮我查typo,但是当时时间不够了,就已经进入问问题环节了,相信还是有bug的。
不过我全程写了自己觉得还比较清楚的注释,不知道能不能加一些印象分。

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

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

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

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

茅塞顿开,学习啦!

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