waymo暑假实习面试分享

liuxiaoyu4321 发表于 2018-9-14 07:47
假设有k个十字路口，有一辆车在每个路口停车的概率是p, 问连续两个路口不停车的概率是多少

这听上去是个概率题啊。两个路口不停不是(1-p)^2 么？楼主能详细说下么，为什么是dp？

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

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

我觉得楼主用dp的思路应该是对的。

这样的dp是不是更方便：每一步，停的概率是（上一步停的概率+上一步不停的概率）* 停的概率，不停的概率是 上一步停的概率 * 不停的概率，dp完之后return(1-结果)。

1. #include<vector>
   
2. #include<iostream>
   
3. #include<cmath>
   
4. using namespace std;
   
5. 
   
6. void helper(vector<bool> &stop, int i, double p, double& res){
   
7.     if(i==(int)stop.size()) {
   
8.         int t = 0, f = 0;
   
9.         for(auto k : stop){
   
10.             if(k) t++;
    
11.             else f++;
    
12.         }
    
13.         cout << t << " " <<f <<" " << pow(p,t)* pow(1.0-p,f) << endl;
    
14.         res += ( pow(p,t) * pow(1.0-p,f) );
    
15.         return;
    
16.     }
    
17. 
    
18.     if(i>0 && stop[i-1] == true){
    
19.             stop[i] = false;
    
20.             helper(stop, i+1, p, res);
    
21.     }else{
    
22.         stop[i] = false;
    
23.         helper(stop, i+1, p, res);
    
24.         stop[i] = true;
    
25.         helper(stop, i+1, p, res);
    
26.     }
    
27.     return;
    
28. 
    
29. }
    
30. 
    
31. double cal(int n, double p){
    
32.     // p means stop
    
33.     vector<bool> stop(n,false);
    
34.     double res = 0.0;
    
35.     helper( stop, 0, p, res);
    
36.     return res;
    
37. }
    
38. 
    
39. 
    
40. int main(){
    
41.     int n = 2;
    
42.     double p = 0.2;
    
43.     double prob = cal(n,p);
    
44.     cout << prob << endl;
    
45.     return 0;
    
46. }

复制代码

我不会用动态规划解这个， 帮我看看我这个遍历的算法对不对。
思路就是把所有最多连续停一次的case都走一遍， 概率加和，然后再用1减去，就是所需要的值。

liuxiaoyu4321 发表于 2018-9-14 07:47
假设有k个十字路口，有一辆车在每个路口停车的概率是p, 问连续两个路口不停车的概率是多少

跟朋友们讨论了下，dp这样子做可以：

1. #include<vector>
   
2. #include<iostream>
   
3. #include<cmath>
   
4. using namespace std;
   
5. 
   
6. 
   
7. double cal(int n, double p){
   
8.     // p means stop
   
9.     vector<double> S(n, 0.0), N(n, 0.0);
   
10.     S[0] = p; N[0] = 1.0-p;
    
11.     for( int i =1; i< n; i++ ){
    
12.         S[i] = (S[i-1] + N[i-1])*p;
    
13.         N[i] = (S[i-1] )*(1-p);
    
14.     }
    
15.    
    
16.     return 1.0 -S[n-1] - N[n-1];
    
17. }
    
18. 
    
19. 
    
20. int main(){
    
21.     int n = 3;
    
22.     double p = 0.2;
    
23.     double prob = cal(n,p);
    
24.     cout << prob << endl;
    
25.     return 0;
    
26. }

复制代码

能具体分享一下第二轮吗

想问一下waymo的面试 可以用java吗？

楼主可以补充下面试能用JAVA写吗

pr1234567 发表于 2018-11-5 11:08
跟朋友们讨论了下，dp这样子做可以：
[mw_shl_code=cpp,true]#include
#include

哈喽， 可以解释一下 S 和N 代表啥嘛？ dp 的思路是什么呀