领英onsite新题

Onsite的时候碰到了一道新题，其他题都是tag题就不赘述了, system design 也是面经题， top k shared link。

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

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

当时用dfs + memo做的，写的不太对。谁给写个正确的？多谢了啊


补充内容 (2018-1-31 08:10):
求点大米，很多帖子不能看

感觉用 backtracking + trie 做好一些

octluck 发表于 2018-1-11 13:42
如果你写出来能贴一个吗？或者站内也行，多谢啦

额，想了一晚上没想出来ｄｆｓ＋ｍｅｍ要怎么实现。感觉要保证所有应该被替换的ｓｕｂｓｔｒｉｎｇ都被替换好难。

想了个ＤＰ的解法，不知道对不对：

1. class Solution {
   
2.         Map<String, String> dict;
   
3. 
   
4.         public List<String> replaceString (String s1, List<String> s2, List<String> s3) {
   
5.                 dict = new HashMap<String, String>();
   
6.                 for (int i=0; i<s2.size(); i++) {
   
7.                         dict.put(s2.get(i), s3.get(i));
   
8.                 }
   
9.                
   
10.                 List<List<String>> dp = new LinkedList<List<String>>();
    
11.                 dp.add(new LinkedList<String>());
    
12.                 dp.get(0).add("");
    
13.                
    
14.                 for (int r=0; r<s1.length(); r++) {
    
15.                         dp.add(new LinkedList<String>());
    
16.                         for (int l=0; l<=r; l++) {
    
17.                                 String key = s1.substring(l, r+1);
    
18.                                 if (dict.containsKey(key)) {
    
19.                                         String suffix = dict.get(key);
    
20.                                         List<String> prefixs = dp.get(l);
    
21.                                         for (String prefix: prefixs) {
    
22.                                                 dp.get(r+1).add(prefix + suffix);
    
23.                                         }
    
24.                                 }
    
25.                         }
    
26.                         if (dp.get(r+1).size() == 0) {
    
27.                                 List<String> prefixs = dp.get(r);
    
28.                                 for (String prefix: prefixs) {
    
29.                                         dp.get(r+1).add(prefix + s1.charAt(r));
    
30.                                 }
    
31.                         }
    
32.                 }
    
33. 
    
34.                 return dp.get(s1.length());
    
35.         }
    
36. }

复制代码

另外面试的小哥和我说他家有人投诉面试题网上到处都是要求公司换题，不知道以后会不会换更多新题。大家抓紧时间啊。

有这么麻烦吗？不是s1里面任何在s2里面出现的都换成s3中对应的吗？没有组合的情况吧？
直接替换就好啦，为什么要dfs？

provhomme 发表于 2018-1-10 09:30
有这么麻烦吗？不是s1里面任何在s2里面出现的都换成s3中对应的吗？没有组合的情况吧？
直接替换就好啦，为 ...

因为 abbbbc 可以分成 a b b b b c, a bb bb c, a b b bb c, a b bb b c, a bb b b c
output: {adefdefdefdefc, adfgdfgc, adefdefdfgc, adefdfgdefc, adfgdefdefc}

面的时候给的例子就是组合啊

octluck 发表于 2018-1-10 11:18
因为 abbbbc 可以分成 a b b b b c, a bb bb c, a b b bb c, a b bb b c, a bb b b c
output: {adefdef ...

哦，原来是这样，我还以为如果是b就全部是换一个，bb就全部是换两个呢。

replacement 的order 是 list的order 吗? 就是{b, bb} 先consider 在consider bb 对否?

say543 发表于 2018-1-10 15:37
replacement 的order 是 list的order 吗? 就是{b, bb} 先consider 在consider bb 对否?

这个我没问，应该没什么要求吧，但是不能替换的字母顺序不能变

楼主请问你的ｄｆｓ＋ｍｅｍ算法中需要ｍｅｍ来记录什么呀？谢谢。

楼上洗衣机成精 发表于 2018-1-11 13:18
楼主请问你的ｄｆｓ＋ｍｅｍ算法中需要ｍｅｍ来记录什么呀？谢谢。

原来用work break II 的思路，结果没有写出来