电面 爱比

前几天的电面 发一下攒人品 貌似是新题 不过和老题类似

有一堆experience 格

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

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

experience.

dp做的 过了

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

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

我不是课代表a 发表于 2019-9-17 13:27
楼主 请问intern和new grad 面经通用吗

我没面过abb家intern 但它们家题库差不多就那些我估计也能通用吧

一个带记忆的dfs的做法，先把所有experiences 按照end time排序dp(k,duration), 代表从前k个里选若干experience, 这些experience在duration (in hours) 范围内，欢迎一起讨论。

1. 
   
2. #include<bits/stdc++.h>
   
3. using namespace std;
   
4. class Solution {
   
5. public:
   
6.     vector<vector<int>> memo;
   
7.     int dp(vector<vector<int>>& experiences,int k,int duration){
   
8.         int start = experiences[k][0];
   
9.         int end = experiences[k][1];
   
10.         int interest = experiences[k][2];
    
11.         if(k==0) {
    
12.             if(end-start<=duration) return interest;
    
13.             return 0;
    
14.         }
    
15.         if(duration<=0) return 0;
    
16.         if(memo[k][duration]) return memo[k][duration];
    
17.         memo[k][duration] = dp(experiences,k-1,duration);
    
18.         if(end-start<=duration) {
    
19.             memo[k][duration] = max(memo[k][duration],interest);
    
20.             for(int i = k-1;i>=0;i--){
    
21.                 if(experiences[i][1]<=start){
    
22.                     memo[k][duration] = max(memo[k][duration],interest+dp(experiences,i,duration-(end-experiences[i][1])));
    
23.                 }
    
24.             }
    
25.         }
    
26.         return memo[k][duration];
    
27.     }
    
28.     static bool comp(vector<int>& a,vector<int>&b){
    
29.         return a[2]<b[2];
    
30.     }
    
31.     int maxInterest(vector<vector<int>> experiences){
    
32.         // sort experience by end date in ascending order
    
33.         sort(experiences.begin(),experiences.end(),comp);
    
34.         int n = experiences.size();
    
35.         memo.resize(n,vector<int>(25,0));
    
36.         return dp(experiences,n-1,24);
    
37.     }
    
38. };
    
39. 
    
40. int main(){
    
41.     Solution s;
    
42.     vector<vector<int>> experiences({{0,5,5},{6,8,12},{0,3,1}});
    
43.     cout<<s.maxInterest(experiences);
    
44. }   

复制代码

不设置积分限制了 求大米啊～

楼主可以详细讲一下吗～ 感谢

比如有[0, 3, 1], [0, 5, 5], [6, 18, 2]
应输出7 选[0, 5, 5], [6, 18, 2] 这两个experience （假设一天的时间是0到24 小时）
如果存在[0, 5, 5][5, 6, 1] 同一个点开始和结束 这2个都可以选

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

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

codeforliving 发表于 2019-9-15 15:54
DP是不是这样做？

首先按照start 排序这些element

这样似乎不对？因为按照start排序 并不能说明i的end就是最大的。

楼主 请问intern和new grad 面经通用吗

马上要面abb了，求群主指点下，拜托了🙏

我不是课代表a 发表于 2019-9-17 13:27
楼主 请问intern和new grad 面经通用吗

我没面过abb家intern 但它们家题库差不多就那些我估计也能通用吧