狗家店面

給一個班級座位表如圖，最上面是老師的位子，S代表學生的位子。


學生跟學生之間可以傳遞紙條，學生跟學生之間的數字代表傳遞紙條被老師發現的機率

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

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

求大米了
光是畫這個圖就花不少時間...
米也不夠看面經

ClearSight 发表于 2022-11-9 22:10
楼主的解法是遍历所有的path, 计算每个path的成功概率，然后用1减？
感觉具体做起来可以用backtrack, 每次 ...

backtracking也可以的 類似刷題word search那題
方便的話請幫加米，謝謝

和刷题网义乌疑似很像

1. #include <iostream>
   
2. #include <numeric>
   
3. #include <vector>
   
4. 
   
5. using namespace std;
   
6. 
   
7. /*
   
8.     double p = 0.9;                // caught when passing vertically to adjacent rows
   
9.     double q = 0.2;                // caught when passing horizontally to adjacent cols
   
10. */
    
11. double caughtPossibility(vector<pair<int, int>> &students, double p, double q) {
    
12.     // source: students[0]
    
13.     // dest: students.back()
    
14.    
    
15.     // 1 - (not caught by teacher) * ... * (not caught by teacher)
    
16.     // we find the product of posiblity of all edges, then 1-X is the answer
    
17.     /*
    
18.     int r = 1;
    
19.     double pToNextCol = p * pow(0.5, r);
    
20.     double pToNextRow = q * pow(0.5, r);
    
21.     */
    
22.     // move from [sr,sc] to [dr, dc]
    
23.     auto probablityToMove = [&](pair<int, int>& from, pair<int, int>& to) {
    
24.         auto [sr, sc] = from;
    
25.         auto [dr, dc] = to;
    
26.         
    
27.         // not adjacent cells...
    
28.         if (abs(dr - sr) > 1 && abs(dc - sc) > 1) {
    
29.             return 0.0;
    
30.         }
    
31.         // same position, do not need calculate.
    
32.         if (dr == sc && dc == sc) {
    
33.             return 1.0;
    
34.         }
    
35.         
    
36.         // move on the same colume
    
37.         if (abs(dr - sr) == 1) {
    
38.             return p * pow(0.5, dr > sr ? sr : dr);
    
39.         }
    
40.         // move on the same row
    
41.         if (abs(dc - sc) == 1) {
    
42.             return q * pow(0.5, sr);
    
43.         }
    
44.         
    
45.         // not reachable
    
46.         return 0.0;
    
47.     };
    
48.    
    
49.     // given the path
    
50.     double notByCaught = 1.0;
    
51.     for (int i = 1; i < students.size(); i++) {
    
52.         notByCaught *= 1 - probablityToMove(students[i - 1], students[i]);
    
53.     }
    
54.     return 1 - notByCaught;
    
55. }
    
56. 
    
57. 
    
58. int main(int argc, char *argv[]) {
    
59.     double p = 0.5, q = 0.9;
    
60.     vector<pair<int, int>> path = {
    
61.         {0, 1},
    
62.         {0, 2},
    
63.         {0, 3}
    
64.     };
    
65.     cout << caughtPossibility(path, p, q);
    
66. }

复制代码

不同吧。這題沒有target number, input 長度也不固定

请问楼主是面L几level的职位？谢谢

现在google还在招人吗？

ashzhao 发表于 2022-11-9 20:12
请问楼主是面L几level的职位？谢谢

L4/L5
方便的話請幫加米，謝謝

z572993482 发表于 2022-11-9 20:38
现在google还在招人吗？

面試是有，但team matching不一定有HC
方便的話請幫加米，謝謝

楼主的解法是遍历所有的path, 计算每个path的成功概率，然后用1减？
感觉具体做起来可以用backtrack, 每次四个方向选一个

請問是樓主是怎麼拿到面試的？是海投之後 HR reach out 問要不要面試？