Amazon | OA | Bangalore

Round 1

Questions: You need to develop a new application and there are N features to be developed for the application. Each feature has two time arrays associated with it:

1. developerTime
2. integrationTime

For each feature, you have 2 ways to choose:

1. You can either develop it from scratch using the developers in your company and consider there are minimum N developers so you can assign each developer one feature. The total time would be the maximum time taken by the developers.
2. Another way is to assign some of the features to the Lead who is only one person in number, so the total time would be the sum of time taken by them for each feature.

The total time would be the maximum time taken by developers & the lead. Find the smallest time needed to finish all the features?

Examples:

1. N=4
DeveloperTime = [3,4,5,9]
Integration Time = [3,2,5,5]

Assign the first three features to devs and the last to the Lead. 
So the ans would be 5 only coz first three takes 5 time 
and the last one takes 5 by the lead so ans = 5.

2. N = 4
DeveloperTime = [1,5,7,2]
Integration Time = [1,1,3,3]

Assign the first & last course to dev so that would be max(1,2)= 2  
and second third courses to the Lead which would take 1+3=4 for them 
so ans = max(2,4) = 4 as the lead takes 4 to finish it

3. N = 5
DeveloperTime = [10,8,15,13,20]
Integration Time = [1,1,2,2,1]

Assign all features to the lead, it would take 1+1+2+2+1 = 7 only which is still less than the 8 for the developer.

The code of mine passed only half test cases:

priority_queue<pair<int,int>> pq;
int ans=0;

for(int i=0;i<developerTime.size();i++) 
    pq.push({developerTime[i],i});

while(!pq.empty()){
    int val = pq.top().first;
    int ind = pq.top().second;
    pq.pop();
    if(ans >= val) break;
    if(val <= integrationTime[ind]){
        ans = max(ans,val);
        break;
    }
    ans += integrationTime[ind];
}
return ans;

I am sorting the dev time by highest value and once it is less than the integration time, I stop and return the max of two values.

Maybe I didn't account for TCs like dev = [11,11,11] and integration = [2,8,3] where it seems like getting the integration time is best since they are all less but dev time would take only 11 compared to integration 13.

Any suggestions for the correct code?

Edit: Got this code link on reddit https://ideone.com/k18T03

Candidate's Approach

The candidate attempted to solve the problem using a priority queue to manage the developer times. The approach involved pushing developer times into the queue and calculating the maximum time based on the conditions provided. However, the candidate realized that the approach did not account for certain test cases where integration times could yield a better result.

Interviewer's Feedback

No feedback provided.

---