G新鲜实习加面

Job Hunting Interview
, , , , , ,
1

之前面经发过了, 刚刚加面,2个超简单问题:
warm up: 给[a, b] [c, d], return true if overlap, return false otherwise
给定D={a, at, cat} 这种, return 一个最长的字符串, 这个字符每次删去一个字符得到的字符串依然在D里, 比如这里返回 cat, 因为 cat - at - a -"" 可以得到这样一个链, 搜索一下就行了
然后是时间复杂度之类的分析

然后已经过去了28分钟, 他居然说没问题了,我尬问了几个问题…30分钟就挂了.
这种情况是不是不太好啊…为什么没有面够时间呢…好紧张

2

两种思路吧
增的话: 处理全部字符串搞成hashMap, key是length, value是一个Set<String>, 然后从length = 1的字符串开始, 每个字符串遍历起所有插入点添加’a’ - ‘z’, 如果得到的新字符串在map.get(length + 1)里, 就放Queue里下一轮继续, BFS的思路
删的思路就是遍历所有字符删, 然后看在不在set里, A满足这个性质的条件是 A的某一删1个字符的子串也在这个List里. 删的思路能节约一个26的常数级复杂度

3

可以麻烦讲一下第二题的思路吗？谢谢！

4

应该事lz做太快了面试官准备的提都问完了，我onsite有一轮就是把面试官的问题都做完了

5

这样吗？楼主

public static String findLong(HashSet<String> dict){
       HashMap<String,Integer> map = new HashMap<>();
       for(String a: dict){
           map.put(a, findlist(a, dict, map));
       }
 
       int res = 0;
       String str = "";
       for(Map.Entry<String,Integer> e: map.entrySet()){
           if (res < e.getValue()) {
               res = e.getValue();
               str = e.getKey();
           }
           System.out.println(e.getKey());
           System.out.println(e.getValue());
       }
 
       return str;
   }
 
   public static int findlist(String a, HashSet<String> dict, HashMap<String, Integer> map){
       if(!dict.contains(a)) return 0;
       int max = 0;
       for(int i = 0; i < a.length() ;i++) {
           String temp = a.substring(0, i) + a.substring(i + 1);
           if (map.containsKey(temp)) {
               max = map.get(temp);
           } else {
               max = Math.max(max, findlist(temp, dict, map));
           }
       }
       return max + 1;
   }
6

求楼主详细讲一下删的思路可以吗，有点没看懂

7
  1. 先把List改Set
  2. 建Map, Str → Boolean的Map
  3. 遍历Set里的Str, 对于一个String s, 如果s为1 并且 s 在 set里(也就是input的list里), map记录 s → true
  4. 如果String s长度不是1, 如果s在Set里, 比如String是 catty, 那么就递归调用看 atty, ctty, caty, catt 必须也满足这个性质. 直到到达base case(3里的长度为1)
  5. 最后再遍历一遍Set, 返回map.get(str) 为 true并且最长的就行了
8

这是不是word ladder啊？经典的BFS