一月三十一号狗家昂赛

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

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

第一题

1.     public int minForReg(String reg, int s, int e){
   
2.         int cnt = 0;
   
3.         int min = Integer.MAX_VALUE;
   
4.         for(int i = s; i<=e; i++){
   
5.             char c = reg.charAt(i);
   
6.             if(c=='X'){
   
7.                 cnt++;
   
8.             }else if(c=='|'){
   
9.                 min = Math.min(cnt, min);
   
10.                 cnt  = 0;
    
11.             }else if(c=='('){
    
12.                 int end = i+1;
    
13.                 int left = 1;
    
14.                 while(end<=e && (reg.charAt(end)!=')' || left!=1)){
    
15.                     if(reg.charAt(end)=='(') left++;
    
16.                     if(reg.charAt(end)==')') left--;
    
17.                     end++;
    
18.                 }
    
19.                 cnt+=minForReg(reg, i+1, end-1);//不用包含括号了！
    
20.                 i=end;
    
21.             }
    
22.         }
    
23.         if(cnt!=0) min = Math.min(cnt, min);
    
24.         return min;
    
25.     }

复制代码

O(n)吧

第五题Tree+Iterator有点微妙，至少children也要是用iterator来access。不然给你一个有巨多个<li>的页面就挂了。同理text也要考虑要不要用iterator。
无论如何还得有个很神的parsing算法来构造这个Tree+Iterator结构。

consciousgaze 发表于 2017-2-3 05:03
发几遍格式都不对……直接贴raw text了
一轮题二：
这道题只是写了dfs里while里的框架，解释思路面试官看 ...

这个有问题吧，比如 121314...这种，如果是按照12来解，一下略过了12个字符就不对吧，因为其实只能是1个21个三

consciousgaze 发表于 2017-2-3 05:03
发几遍格式都不对……直接贴raw text了
一轮题二：
这道题只是写了dfs里while里的框架，解释思路面试官看 ...

应该是 count + 1 + int(c);

consciousgaze 发表于 2017-2-3 05:04
第三轮：
这道题面筋里有，不过我没看到完整清楚的解法，这次写了就写一下吧
给出string s，和dict d。求 ...

请问用trie怎么做呢，把words存到trie里？

第三轮，java version

1. public class LongestSubsequenceInDict {
   
2. 
   
3.     public String longestSubsequenceWord(String s, Set<String> dict) {
   
4.         String res = "";
   
5.         for (String word : dict) {
   
6.             if (word.length() > res.length() && isSebsequence(s, word)) {
   
7.                 res = word;
   
8.             }
   
9.         }
   
10. 
    
11.         return res;
    
12.     }
    
13. 
    
14.     private boolean isSebsequence(String s, String word) {
    
15.         int i = 0;
    
16.         int j = 0;
    
17.         while (i < s.length() && j < word.length()) {
    
18.             if (s.charAt(i) == word.charAt(j)) {
    
19.                 i++;
    
20.                 j++;
    
21.             } else {
    
22.                 i++;
    
23.             }
    
24.         }
    
25. 
    
26.         return j == word.length();
    
27.     }
    
28. 
    
29. 
    
30.     public String longestSubsequenceWord1(String s, Set<String> dict) {
    
31.         String res = "";
    
32.         HashMap<Character, TreeSet<Integer>> cachedS = buildCachedS(s);
    
33.         
    
34.         for (String word : dict) {
    
35.             if (word.length() > res.length() && isSebsequence1(cachedS, word)) {
    
36.                 res = word;
    
37.             }
    
38.         }
    
39. 
    
40.         return res;
    
41.     }
    
42. 
    
43.     private HashMap<Character,TreeSet<Integer>> buildCachedS(String s) {
    
44.         HashMap<Character,TreeSet<Integer>> map = new HashMap<>();
    
45.         for (int i = 0; i < s.length(); i++) {
    
46.             char c = s.charAt(i);
    
47.             if (map.containsKey(c)) {
    
48.                 map.get(c).add(i);
    
49.             } else {
    
50.                 map.put(c, new TreeSet<>());
    
51.                 map.get(c).add(i);
    
52.             }
    
53.         }
    
54. 
    
55.         return map;
    
56.     }
    
57. 
    
58.     private boolean isSebsequence1(HashMap<Character, TreeSet<Integer>> map, String word) {
    
59.         int pos = 0;
    
60.         int i = 0;
    
61.         for (; i < word.length(); i++) {
    
62.             char c = word.charAt(i);
    
63.             if (!map.containsKey(c) || map.get(c).ceiling(pos) == null) {
    
64.                 return false;
    
65.             }
    
66.             pos = map.get(c).ceiling(pos);
    
67. 
    
68.         }
    
69.         return i == word.length();
    
70.     }
    
71. 
    
72. 
    
73. 
    
74.     public static void main(String[] args) {
    
75.         LongestSubsequenceInDict l = new LongestSubsequenceInDict();
    
76.         HashSet<String> set = new HashSet<>();
    
77.         set.add("abc");
    
78.         set.add("abbbc");
    
79.         set.add("abb");
    
80.         System.out.println(l.longestSubsequenceWord1("aaaaaaabbbbbbdddddd", set));
    
81.         System.out.println(l.longestSubsequenceWord1("aaaaaaabbbbbbddddddc", set));
    
82.     }
    
83. }
    

复制代码

consciousgaze 发表于 2017-2-3 10:19
第四轮code

def getFirstInt(byteArray):

请问返回第一个数是指什么？

consciousgaze 发表于 2017-2-3 04:59
一轮题一：判断regex可以包含的最少字符。我的解法起码有一个可以不用stack的地方（注释里说了），也应该能 ...

没看懂，这个题是要问什么呢，最少的字符是要满足什么条件？

第四轮code

1. public class ParseVariableLengthInteger {
   
2. 
   
3.     public static void main(String[] args) {
   
4.         int[] arr = {0b10000101, 0b00100001, 0b11010101};
   
5.         System.out.println(isCorrectFormat(arr));
   
6.     }
   
7. 
   
8.     public static boolean isCorrectFormat(int[] arr) {
   
9.         if (arr == null || arr.length == 0) {
   
10.             return true;
    
11.         }
    
12. 
    
13.         int count = 0;
    
14.         for (int i = 0; i < arr.length; i++) {
    
15.             if (count == 0) {
    
16.                 int  v = arr[i];
    
17.                 if ((v >> 7) == 1) {
    
18.                     count = 0;
    
19.                 } else if ((v >> 6) == 0b01) {
    
20.                     count = 1;
    
21.                 } else if ((v >> 5) == 0b001) {
    
22.                     count = 2;
    
23.                 } else if ((v >> 4) == 0b0001) {
    
24.                     count = 3;
    
25.                 } else {
    
26.                     return false;
    
27.                 }
    
28.             } else {
    
29.                 count--;
    
30.                 if (count < 0) {
    
31.                     return false;
    
32.                 }
    
33.             }
    
34.         }
    
35. 
    
36.         return count == 0;
    
37.     }
    
38. }
    

复制代码