阿玛松 vo 挂经

bq：
challenging project;
courses in this semester and plan courses next semester;
上过多少算法课

第一题 按照空格给字符串分词，每个单词计数
第二题 判断一个字符串是不是另外两个字符串的乱序组合 比如 X = "ABC

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

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

er了..大家题目错了千万不要慌，口头讲一下思路也可以。楼主最后知道有点崩但在问题环节还是强颜欢笑吹了一波amazon comprehension, 可能这也有帮助吧。 不到面试结束千万不要认输。最后求一波offer群！

dfs, 三个point i,j,k 分别指向首字母， 判断 i==k || j == k 都不满足就return false， recursion 所有的情况，直到 i+j == z.length()

private boolean helper(String X,String Y,String Z,int indx,int indy,int indz){
    if (indx >= X.length() || indy >= Y.length() )return false;
    if (X.charAt(indx) == Z.charAt(indz) && Y.charAt(indy) == Z.charAt(indz))
          return helper(X,Y,Z,indx + 1,indy,indz + 1) || helper(X,Y,Z,indx,indy + 1,indz + 1);
    if (X.charAt(indx) == Z.charAt(indz))return helper(X,Y,Z,indx + 1,indy,indz + 1);
    if(Y.charAt(indy) == Z.charAt(indz)) return helper(X,Y,Z,indx,indy + 1,indz + 1);
    return false;
}

请问第三题是考虑三种情况吗？

Z是AB的顺序组合，Z是AB的乱序组合，Z不是AB的组合，只有第二种情况返回true

先用map判断Z是不是由AB组成的，如果是再用DP或dfs去判断Z是不是顺序组合，不是就返回true?

补充内容 (2019-2-21 08:17):
第二题

好像是错了。。应该用bfs写。。。

用recursion 来bfs 每层Z少一位， 然后X 少一位 OR Y少一位 最后把底层的判断OR 一下？

sssphon 发表于 2019-2-21 06:46
用recursion 来bfs 每层Z少一位， 然后X 少一位 OR Y少一位 最后把底层的判断OR 一下？

是的了。。

下周面试，好紧张不知道问点什么，求好运

kashimoto 发表于 2019-2-21 06:47
是的了。。

请问一下 bfs的recursion里面用stack来写可以吗？

楼主请问是蠡口 酒气 吗？就是去判断是否是顺序组合

第二题是dp吗？

kashimoto 发表于 2019-2-21 06:34
好像是错了。。应该用bfs写。。。

双指针 字符数量左右不匹配的。。

是dp， O(len(X)*len(Y))复杂度