Coursera, Houzz, Airbnb 面经

1. mincost of flight from start to end if allowed at most k connections 这题就用BFS最好了吧，到过的点记录mincost做剪枝。如果空间有限制就用迭代加深搜索

clxy2008 发表于 2016-11-2 01:34
这个k指的是最多可以中转城市的个数吗？。。

根据以前地里的面经 是

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

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

楼主您好马上要去airbnb onsite啦，想问下是可以带自己电脑在自己的编译器上写的吗？

还有这个题目最佳用dp做吧

yucheyang2 发表于 2016-11-2 11:16
还有这个题目最佳用dp做吧

dp怎么做？

yucheyang2 发表于 2016-11-2 11:15
楼主您好马上要去airbnb onsite啦，想问下是可以带自己电脑在自己的编译器上写的吗？

应该是可以的

Sayako 发表于 2016-11-2 11:20
dp怎么做？

就是connection一围cities一围，

1. queue<string> q;
   
2. q.push(start);
   
3. 
   
4. int iter=0;
   
5. while(iter <=k){
   
6.     iter ++;
   
7.     int size = q.size();
   
8.     for(int i = 0; i < size; i++){
   
9.         auto cur = q.front(); q.pop();
   
10.         for(auto ng: neighbor[cur] && cost[ng] > cost[cur] + ticket[cur->ng]) {
    
11.             cost[ng] = cost[cur]+ ticket[cur->ng];
    
12.             q.push(ng);
    
13. 
    
14.         }
    
15.     }
    
16. }

复制代码

当时写了个类似的代码，跑了一下结果好像没有被challenge说不对，烙印说我这个效率不行，会重复走边。。 我想了一下，感觉也没法删边吧。

yucheyang2 发表于 2016-11-2 11:54
就是connection一围cities一围，

不太明白啊，求详细……