发个口袋宝石OA+电1电2面经

OA: Zombie cluster， 不多说啦

Phone1:
题是小哥口述的，让自己take notes
http://www.1point3acres.com/bbs/thread-217589-1-1.html

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

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

font>


一面华人小哥，二面华裔姐姐，两位口音都很纯正，人也很好很耐心，一时没有思路也不会催你，讲到正确的思路他们也会予以肯定，面试体验还是很好的，就是自己水平不够，二面那个题卡壳太久估计跪了

BTW，我连续两轮都没有遇到高频题，苦练的许久的strstr+ topk也没有发挥出来，也许是口袋宝石意识到题库泄露，有意的加新题或是改条件，最近面的小伙伴要注意啦， 最后求个大米

其实就是按长度排好序，然后建一个Map<String, Set<String>>, 这里Set<String>是所有该string能组合成的parent string， 好拗口，这么写parentString.indexOf(string) != -1大家就懂了.
然后每次除了更新自己的parent string，还要回过头去更新所以以自己为parent string的 string，把祖先string从它那里移除, 举例， ring可以到tring和string， 发现tring能到string，然后回过头把ring里的string去掉
最后用一个visited set来过一遍所有string，看有多少条path（有向）

jili 发表于 2017-7-12 07:18
对的要排序，我之前想了一个图的方法，每个String 看做一个Vertex， 建立一个邻接矩阵记录两两间是否为子 ...

尝试着写了一个 但是不能handle duplicate, 如果handle duplicate 改动应该也不大

1. public static List<String> partitionStr(String[] strs) {
   
2.             Arrays.sort(strs, (String a, String b) -> a.length() - b.length());
   
3.             Map<String, Set<String>> parentStr = new HashMap<>();
   
4.             for (int i = 0; i < strs.length; i++) {
   
5.                     for (int j = i + 1; j < strs.length; j++) {
   
6.                             if (strs[j].indexOf(strs[i]) == -1) {
   
7.                                     continue;
   
8.                             }
   
9.                             Set<String> s = parentStr.getOrDefault(strs[i], new HashSet<>());
   
10.                             s.add(strs[j]);
    
11.                             parentStr.put(strs[i], s);
    
12.                     }
    
13.             }
    
14.            
    
15.             List<String> res = new ArrayList<>();
    
16.             Set<String> visited = new HashSet<>();
    
17.             for (int i = 0; i < strs.length; i++) {
    
18.                     if (parentStr.containsKey(strs[i])) {
    
19.                             for (String val: parentStr.get(strs[i])) {
    
20.                                     if (parentStr.containsKey(val)) {
    
21.                                             parentStr.put(strs[i], nonIntersect(parentStr.get(strs[i]), parentStr.get(val)));
    
22.                                     }
    
23.                             }
    
24.                     }
    
25.             }
    
26.             for (int i = 0; i < strs.length; i++) {
    
27.                     if (!parentStr.containsKey(strs[i])) {
    
28.                             continue;
    
29.                     }
    
30.                     path(parentStr, res, "", visited, strs[i]);
    
31.             }
    
32.             return res;
    
33.     }
    
34.    
    
35.     public static void path(Map<String, Set<String>> map, List<String> res, String cur,
    
36.                     Set<String> visitedKey, String key) {
    
37.             if (visitedKey.contains(key)) {
    
38.                     return;
    
39.             }
    
40.             if (map.containsKey(key)) {
    
41.                     for (String val: map.get(key)) {
    
42.                             path(map, res, cur + key + " ", visitedKey, val);
    
43.                     }
    
44.                     visitedKey.add(key);
    
45.             } else {
    
46.                     res.add(cur + key);
    
47.                     return;
    
48.             }
    
49.     }
    
50.    
    
51.     public static Set<String> nonIntersect(Set<String> a1, Set<String> a2) {
    
52.             Set<String> res = new HashSet<>();
    
53.             for (String val: a1) {
    
54.                     if (!a2.contains(val)) {
    
55.                             res.add(val);
    
56.                     }
    
57.             }
    
58.             return res;
    
59.     }

复制代码

siren01 发表于 2017-7-12 04:31
这个电话面试没有懂，能再讲解一下么

补充内容 (2017-7-12 04:32):

case 1:   bc 是 abc 子串，  算一个partition
case 2:   str 是 string子串 组成 （string, str）
             ing 是 string 子串 组成 （string, ing）
             str ing 之间没有子串关系， 返回2
             返回2

case 3:  ri 是 string 子串 ， 组成 (string, ri)
            ri 是 ringo 子串，  组成  (ringo, ri)
            string ringo 之间没有子串关系, 返回 2

case 4:  ring 是 tring 子串， tring是 string 子串， 组成 (string, tring, ring)， 返回1

这个电话面试没有懂，能再讲解一下么

补充内容 (2017-7-12 04:32):
电面2

今天刚收到正式拒信，主要就坑在二面这个题，3楼作了更详细的说明，有人再遇到这题的时候一定要把它秒掉啊

jili 发表于 2017-7-12 04:42
今天刚收到正式拒信，主要就坑在二面这个题，3楼作了更详细的说明，有人再遇到这题的时候一定要把它秒掉啊

谢了，就当练练手用，不要太在意。move on

jili 发表于 2017-7-12 04:42
今天刚收到正式拒信，主要就坑在二面这个题，3楼作了更详细的说明，有人再遇到这题的时候一定要把它秒掉啊

感觉电面2和strStr有点像....算是变形？！

newgod2500 发表于 2017-7-12 05:25
感觉电面2和strStr有点像....算是变形？！

比strstr复杂些，我为了思考求partition个数的算法，判断是否为子串直接调了 indexOf, 面试官也没说啥

jili 发表于 2017-7-12 05:51
比strstr复杂些，我为了思考求partition个数的算法，判断是否为子串直接调了 indexOf, 面试官也没说啥

想请教下楼主，先排序，然后strstr+union-find？

lj910817 发表于 2017-7-12 06:42
想请教下楼主，先排序，然后strstr+union-find？

我也想到过，但这题规定的这种关系还不具有传递性，你看 case2: "string" "str" "ing" , union_find 是一个cluster 返回1,  但实际上应返回2。

jili 发表于 2017-7-12 06:59
我也想到过，但这题规定的这种关系还不具有传递性，你看 case2: "string" "str" "ing" , union_find 是一 ...

要先排序把，每次往前扫，str和string是一组，ing和string是一组