微软 Event Onsite

Event，四小时四道题。

1. LC 117 变形，每层最后一个 next 指向下层最左node

2. LC 153

3. 从无

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

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

容 (2017-5-10 23:00):
已挂。。。

感谢楼主分享，祝好运。感觉最后一题好像是排列组合题啊，比如给你两个c, 两个a，和两个t，有多少种组合方式构成cat？答案是8

所以，我斗胆写了下面这个代码，不知道对不对：

1. 
   
2. public static int countCats(String s, String target) {
   
3.         if (s == null || s.length() < target.length()) return 0;
   
4. 
   
5.         int res = 1;
   
6.         int[] targetHash = new int[26];
   
7.         for (int i = 0; i < target.length(); i++) {
   
8.             int idx = target.charAt(i) - 'a';
   
9.             targetHash[idx]++;
   
10.         }
    
11. 
    
12.         int[] hash = new int[26];
    
13.         for (int i = 0; i < s.length(); i++) {
    
14.             int idx = s.charAt(i) - 'a';
    
15.             hash[idx]++;
    
16.         }
    
17. 
    
18. 
    
19.         for (int i = 0; i < 26; i++) {
    
20.             if (hash[i] < targetHash[i]) return 0; // impossible
    
21. 
    
22.             if (targetHash[i] > 0) {
    
23.                 res *= chooseKFromN(hash[i], targetHash[i]);
    
24.             }
    
25.         }
    
26. 
    
27.         return res;
    
28.     }
    
29. 
    
30.     // 计算组合数：
    
31.    //  recursively computing the number of ways for choosing k from n elements
    
32.     private static long chooseKFromN(int N, int K) {
    
33.         System.out.println("N = " + N + ", K = " + K);
    
34.         if (N < K) return 0;
    
35.         if (K == 0 || N == K) return 1;
    
36.         return chooseKFromN(N-1, K-1) + chooseKFromN(N-1, K);
    
37.     }
    

复制代码

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

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

最后一题subset变形吧，每次选头 检查是不是cat其中的字母 是的话就从该index后开始找下一个字母 backtrack一下 最终string的长度够了，或者要搜索的str.length == 0， count++
我一开始还以为只是数 字母个数 用hash 汗一下。。 pat楼主 面试的时候很容易蒙圈 经常下来会觉得当时傻了

LZ都是算法题么？没有系统设计么？

楼主这是啥组?

lsy1991121 发表于 2017-5-10 10:15
LZ都是算法题么？没有系统设计么？

是啊，很神奇的没碰到系统设计，不知是喜是忧。。。

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

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

感觉是Subset这题的变形。

啥是event onsite？

看着像sliding window problem

最后一题应该是幺幺伍用dp做吧