狗家Fall Intern电面

保持队形再来贡献一个面经。
6月28号面的，刚好赶上他们mountain view的有很多人据说组织去游乐场玩了大概这是为啥面我的都是两个纽约的白人妹子。
第一面是read two files
Fi

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

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

这个word是否可以由这些骰子摇出，要求不能两个或两个字母以上由同一个骰子出来，但骰子数量可以很多，骰子上字母可以是任意字母，重复也行。

第二题个人感觉应该属于人工智能领域的CSP问题，类似八皇后问题，本身是NP-hard，但也有很多优化方法，这里感觉考官就是靠暴力的backtracking吧？
但是似乎也可以用 Bottom-up 的DP解，如果没错的话应该是n的三次方：
n = word.length
Let M[ ] [ ]  be a 2-D share matrix with shape of (n,n)  
For i = 0 to n:
        set = [ ]
        for dice in all dices:
                if dice has char[ i ]
                set.append( {dices-dice} ) (one possible state after crossing this one )
         if set.isEmpty():
                return "don’t exist!"
                m[ i ][ i ] = set
For offset = 0 to n-1:
        for i = 0 to n - offset:
                j = i + offset
                //fill M[ i ][ j ]:
                for dice_set in M[ i+1 ][ j ]:
                        keep_dice_set = false
                        for dice in dice_set:
                                if dice has char[ i ]
                                remove this dice from this dice_set
                                keep_dice_set = true // this state is possible
                                if char[ i ] is last char:
                                        return “Yes, there exits!”  //goal test
                                break
                        if keep_dice_set is false:
                                remove this dice_set  (the state is impossible or unsatisfactory)
                for dice_set in M[ i ][ j-1 ]:
                        do the same as M[ i+1 ][ j ] case
                M[ i ][ j ] =  Natural join(M[ i+1 ][ j ], M[ i ][ j-1 ] )
                If M [ i ][ j ] is an empty set:
                        return  “don’t exists!”
return “don’t exits” // the algorithm will probably never reach this line

zhangsikai123 发表于 2017-7-13 10:26
第二题个人感觉应该属于人工智能领域的CSP问题，类似八皇后问题，本身是NP-hard，但也有很多优化方法，这里 ...

参照大神点拔的八皇后思路。用bit manipulation 存状态 做了backtracking. 如下。大神的dp解更优。我这个可能稍微适合普通玩家理解一点。

1. #include <iostream>
   
2. #include <vector>
   
3. using namespace std;
   
4. 
   
5. #define N 6  // N is the length of target string
   
6. 
   
7. bool helper(vector<string>& strs, string target, int state, int pos){
   
8.    
   
9.     // calculate cross: indices of chars in target that also appear in strs[pos]. Those indices are set at the corresponding bit in "cross".
   
10.     if(state == (1 << N) - 1) return true; // all bits are set
    
11.     if(pos == N) return false; // already tried all strings in strs without success
    
12.    
    
13.     int cross = 0;
    
14.     string& curr = strs[pos];
    
15.     for(int i = 0; i < N; i++) {
    
16.         if(count(curr.begin(), curr.end(), target[i]))
    
17.             cross |= (1 << i);
    
18.     }
    
19.     int cand = cross & (~state);
    
20.     for(; cand != 0; cand -= cand & (-cand)) {
    
21.         if(helper(strs, target, state + (cand&(-cand)), pos+1)) return true;
    
22.     }
    
23.     return false;
    
24. }
    
25. 
    
26. bool makeTarget(vector<string>& strs, string target) {
    
27.     int state = 0;
    
28.     return helper(strs, target, state, 0);
    
29. }
    
30. 
    
31. int main(int argc, const char * argv[]) {
    
32.     // insert code here...
    
33.     vector<string> strs = {
    
34.         "abcdef",
    
35.         "abcdef",
    
36.         "abcdef",
    
37.         "abcdef",
    
38.         "abcdef",
    
39.         "abcdef"
    
40.     };
    
41.     cout << helper(strs, "abcdef", 0, 0) << endl;
    
42.    
    
43.     strs = vector<string> ({
    
44.         "abcdef",
    
45.         "abcdef",
    
46.         "abcdef",
    
47.         "abcdef",
    
48.         "abcdef"
    
49.     });
    
50.     cout << helper(strs, "abcdef", 0, 0) << endl;
    
51.    
    
52.     strs = vector<string> ({
    
53.         "axxxxx",
    
54.         "abyyyy",
    
55.         "abczzz",
    
56.         "abcdqq",
    
57.         "abcdep",
    
58.         "lllllf"
    
59.     });
    
60.     cout << helper(strs, "abcdef", 0, 0) << endl;
    
61.     return 0;
    
62. }

复制代码

请问第二题roll到char的顺序有关系吗？比如第一个拿到的字母需要是target word的开始的第一个char

zhengwei 发表于 2017-6-30 07:50
请问第二题roll到char的顺序有关系吗？比如第一个拿到的字母需要是target word的开始的第一个char

顺序没有关系，一个骰子只能roll一个字母，只要能roll到这个target word就行

这么难的题，摸摸头~~~

楼主你做过coding sample么。。过了多久收到电面邮件？。。我等了一星期了，估计GG了。

这还要考文件操作？？

第二个问题本质上是求二分图的最大匹配... 算法是“匈牙利算法”或者网络流的”最大流算法“，复杂度是O(V^3)，V = dices数量 + word长度。

具体来说就是建立两个节点集合S和T，word中每个字母为S中一个节点，每个dice为T中一个节点，然后对于任意节点s∈S，t∈T，s与t之间建立一条边当且仅当dice t包含字母s。

然后S和T构成一个二分图，求得这个二分图的最大匹配数为W，那么结果“是否可以由这些骰子摇出”等价于(W == word长度)。

这种图论题目确实很难（而且工作中没用），自己去想基本上只能弄出来指数级的穷举方法，leetcode上好像也是没有的，一些学校的算法课程会在最后一两章讲网络流。

第二题有什么思路吗？

331412073 发表于 2017-7-6 01:16
楼主你做过coding sample么。。过了多久收到电面邮件？。。我等了一星期了，估计GG了。

我做完coding sample第二天一早就收到约电面的邮件了，那时候是六月初了，现在可能时间有点晚了，你再等等

wxl3691 发表于 2017-7-6 01:19
这还要考文件操作？？

我当时一听也是懵，文件操作不是重点考察应该