前几天的 骨骼店面

前几天的电面 题很简单 白人大叔

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

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

最后压着时间写完的，面试官也就没问怎么优化。感觉自己全程话有点多，每写一行都跟在跟他交流，浪费的时间有点多。
全程交流很流畅，面试官人很好。
面试完才想到貌似可以用dp做，心里有点慌。但是貌似看别人的面经有人没用最优解最后也能拿到onsite?
可是这种简单的题会不会要求更高一点啊。
最后求问狗家店面一般多久给回复啊，等电话等的坐立难安。

这题我想用greedy从A中匹配尽量多的B中的元素（用反证法可以证出这样肯定最少），然后双指针扫A和B,B扫完了说明A匹配完了，B指针reset成0匹配A的下一段。代码也很简单（时间复杂度是O(m + n)）:

1. public int minConstruct0(String a, String b) {
   
2.         int i = 0;
   
3.         int count = 0;
   
4.         while (i < a.length()) {
   
5.             int j = 0;
   
6.             int prev = i;
   
7.             while (i < a.length() && j < b.length()) {
   
8.                 if (a.charAt(i) == b.charAt(j)) {
   
9.                     i++;
   
10.                     j++;
    
11.                 } else {
    
12.                     j++;
    
13.                 }
    
14.             }
    
15.             if (prev == i) return -1;
    
16.             count++;
    
17.         }
    
18.         return count;
    
19.     }

复制代码

补充内容 (2018-8-17 02:20):
时间复杂度应该是O(mn).

感谢分享！祝好运！
貌似可以先根据B求所有可行路径（子序列），然后在A上求从头到尾的最短路径。B上通过枚举或者dfs（O(2^n)）构造可行子序列，可行子序列可以再构造一个trie方便后面查询。A上DP求最短路（O(n * m), 其他最短路径算法应该再快些)。

这个感觉可以dfs + memorization
记录下sub  string 是否可以由挖去字符串构成就行。

請問樓主可以分享一下題目嗎？積分不夠．．．謝謝！

用c++写的话，想用一个map(hash table)存B里面的每个字符包含index的vector(list)，然后遍历A用lower_bound做匹配，并记录当前的位置，每当找不到的时候就重置位置为0，然后使用次数加1，时间复杂度是O(len(A)log(len(B))), 空间复杂度是O(len(B))， 不知道对不对，很暴力就是了，anyway

感觉有点像   易散旧，  把b 变个花样存进 dictionnary里 然后就一样了

请问楼主 oa 考的什么题目 Google发了oa 还没敢打开

w651164284 发表于 2018-8-10 07:18
用c++写的话，想用一个map(hash table)存B里面的每个字符包含index的vector(list)，然后遍历A用lower_bound ...

请问时间复杂度里的log（len（B））是怎么出现的？那个匹配过程是类似二分法么？
不太会c++。感谢回复。

uncle Max 发表于 2018-8-10 07:25
请问楼主 oa 考的什么题目 Google发了oa 还没敢打开

OA就是开花和求最近时间的那两道题。
我开花那题用的还是O（n*n）的解法都过了。
感觉他们会看你的test case 和 comment。尽量把代码写的清晰 好看 没bug吧。
还有就是请尽早做吧。
我同学比我晚投几天连OA都没拿到，我觉得应该是越早机会越大。

我的思路是dp 有不对的地方求地里小伙伴们指点~
dp[i] = A的前i个字符用B拼出的最少次数
首先全部设为Integer.MAX_VALUE表示不能拼出来
dp[0] = 0;
然后
for (int i = 1; i <= A.length; i++) {
   for (int j = 0; j < i; j++) {
       if (dp[j] != Integer.MAX_VALUE && B.indexOf(A.substring(j, i)) > 0) {
            dp[i] = Math.min(dp[i], dp[j] + 1);
       }
   }
}
最后return dp[A.length]

xiaocase 发表于 2018-8-10 07:26
请问时间复杂度里的log（len（B））是怎么出现的？那个匹配过程是类似二分法么？
不太会c++。感谢回复。

lower_bound是log(n)的时间复杂度，如果list是有序的话