狗家挂经

刚收到HR电话，不出意外地挂了狗家。现在把面经发出来，希望造福后来人，也给自己攒点rp。

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

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

面完了就move on了，虽然找工作挺难的，但是还是要劝勉大家坚持坚持再坚持，总有一天能找到合适自己的工作的！

第三题给一个nlogn的思路，greedy，还得证明，代码量也好多，感觉面试的时候很难都写完啊。

1. /* return the minimum number of deletion and copy to get target String
   
2.          store the index of characters in source into index table
   
3.          replace target string with the its charactes's index in source string, and try to find as much as continuous increasing index as possible.
   
4.          To achieve that, we want to choose index as small as possible, however, need to be greater than previous char's index;
   
5.          1. O(n) process the index table
   
6.          2. for each character, O(log n) - binary search to find the smallest index that is greater than previous index, if no such index, assign the smallest index of current character
   
7.          3. rebuild answer list O(n)
   
8.          total: Time: O(n log n) Space: O(n)
   
9.          End case, no such character in source. return empty list
   
10.          AZAB -> ZBAZ
    
11.          i.e.
    
12.          1. get table
    
13.          A: 2
    
14.          Z: 0, 3
    
15.          B: 1
    
16.          2. assign index: 2,3,2,1
    
17.          3. find how many continuous increasing subArray
    
18.                  answer: [2,3],[2],[1]
    
19.          */
    
20.         public List<List<Integer>> canTransForm(String target, String source){
    
21.                 // assume only capital letter in target and source
    
22.                 if(target == null || source == null || target.length() == 0 || source.length() == 0){
    
23.                         return new ArrayList<>();
    
24.                 }
    
25.                
    
26.                 // init index table
    
27.                 Map<Character, List<Integer>> map = new HashMap<>();
    
28.                 for(int i = 0; i < source.length(); i++){
    
29.                         char c = source.charAt(i);
    
30.                         List<Integer> indexes = map.get(c);
    
31.                         if(indexes == null){
    
32.                                 indexes = new ArrayList<>();
    
33.                                 map.put(c, indexes);
    
34.                         }
    
35.                         indexes.add(i);
    
36.                 }
    
37.                
    
38.                 // init the target index array
    
39.                 int[] targetIdx = new int[target.length()];
    
40.                
    
41.                 for(int i = 0; i < target.length(); i++){
    
42.                         List<Integer> indexes = map.get(target.charAt(i));
    
43.                         if(indexes == null){
    
44.                                 return new ArrayList<>();
    
45.                         }else{
    
46.                                 // binary search index
    
47.                                 targetIdx[i] = find(indexes, i == 0 ? Integer.MAX_VALUE : targetIdx[i - 1]);
    
48.                         }
    
49.                 }
    
50.                
    
51.                 // build final result list               
    
52.                 return buildList(targetIdx);
    
53.         }
    
54.        
    
55.         // binary search smallest number that larger than i
    
56.         private int find(List<Integer> indexes, int i){
    
57.                 int l = 0;
    
58.                 int r = indexes.size() - 1;
    
59.                 while(l < r){
    
60.                         int mid = l + (r - l) / 2;
    
61.                         if(indexes.get(mid) <= i){
    
62.                                 l = mid + 1;
    
63.                         }else{
    
64.                                 r = mid;
    
65.                         }
    
66.                 }
    
67.                
    
68.                 if(indexes.get(l) <= i){
    
69.                         return indexes.get(0);
    
70.                 }else{
    
71.                         return indexes.get(l);
    
72.                 }
    
73.         }
    
74.        
    
75.         // build final list by count continuous increasing subArray
    
76.         private List<List<Integer>> buildList(int[] targetIdx){
    
77.                 List<List<Integer>> res = new ArrayList<>();
    
78.                 List<Integer> cur = new ArrayList<>();
    
79.                 cur.add(targetIdx[0]);
    
80.                 for(int i = 1; i < targetIdx.length; i++){
    
81.                         if(targetIdx[i] > targetIdx[i - 1]){
    
82.                                 cur.add(targetIdx[i]);
    
83.                         }else{
    
84.                                 res.add(cur);
    
85.                                 cur = new ArrayList<>();
    
86.                                 cur.add(targetIdx[i]);
    
87.                         }
    
88.                 }
    
89.                 if(cur.size() != 0){
    
90.                         res.add(cur);
    
91.                 }
    
92.                 return res;
    
93.         }

复制代码

mtrsen 发表于 2018-10-13 10:53
楼主最后一题可以再详细说一下吗，前面的team部分不知道和题目有什么关系

team就是说有自己这方和对手一方，跟下面一个同学说的BFS或者DFS找边界差不多，但是问题是他要求怎么样判断你下的一个地方能立即kill对方的一个或多个棋子？所以我认为是找边界，然后找所有边界只有一个空缺的位置，这样就能确定立即kill对方的一些棋子。

楼主最后一题可以再详细说一下吗，前面的team部分不知道和题目有什么关系

最后一题是类似围棋的规则么？
如果是围棋的话。假设我的棋子是1， 对手-1。 当我判断我的题是否吃掉对手棋子时，则是看上下左右4个点。是否有-1，完全被我的1或者边界包围了，也就是DFS或者BFS找边界把。

感谢楼主！

感谢楼主分享！有反馈说是挂在第三轮还是第四轮了吗？还是其他轮？第三轮关于优化面试官有过提示么？感谢！～～

感谢分享

zjm724 发表于 2018-10-13 13:39
感谢楼主分享！有反馈说是挂在第三轮还是第四轮了吗？还是其他轮？第三轮关于优化面试官有过提示么？感谢！ ...

没有什么提示，我到现在也没想出来。。。

lucifer_vent 发表于 2018-10-13 12:02
最后一题是类似围棋的规则么？
如果是围棋的话。假设我的棋子是1， 对手-1。 当我判断我的题是否吃掉对手 ...

是的，但是我当时是想找到一个空缺，放进去之后就能kill对方一些棋子。现在回头想一想，其实找边界不太好做，反而找空缺，再判断是否能kill一些棋子比较容易实现。

请问lz onsite结束后，有没有先team match？是HC挂的吗？