This round was conducted to eliminate any candidates who may have engaged in unfair play during the Hackathon round. We had to share our screens and keep our cameras on while solving the questions.
Question 1: Find the Person with the Highest Score
Problem Statement:
Given q queries where each query consists of a name and a score, we need to find the person with the highest cumulative score at the end of all queries. In case of a tie, the person who reached the highest score first should be the winner.
Test Cases:
Input 1:
6
A 3
B 2
A 5
B 6
A 1
B 1 Output 1:
A Input 2:
3
mike 3
andrew 5
mike 2 Output 2:
andrew Code:
#include <bits/stdc++.h>
using namespace std;
int main() {
int n;cin>>n;
// int maxx=INT_MIN;
vector<pair<string,int>> queries;
unordered_map<string,int>m;
for(int i=0;i<n;i++){
string s;
int x;
cin>>s>>x;
m[s]+=x;
// maxx=max(maxx,m[s]);
queries.push_back({s,x});
}
unordered_map<string,bool> same;
int maxx1=INT_MIN;
for(auto x:m) maxx1=max(maxx1,x.second);
for(auto x:m){
if(x.second==maxx1){
same[x.first]=true;
}
}
unordered_map<string,int>m1;
for(auto x:queries){
m1[x.first]+=x.second;
if(m1[x.first]>=maxx1 && same[x.first]) {cout<<x.first;break;}
}
// cout<<ans<<" "<<maxx<<"\n";
return 0;
}Question 2: Job Scheduling with Minimum Maximum Load
Problem Statement:
You are given an array of jobs where jobs[i] represents the time required to complete a job. Distribute these jobs among k workers such that the maximum time taken by any worker is minimized.
Test Cases:
Input 1:
3
3 2 3
3 Output 1:
3 Input 2:
5
1 2 4 7 8
2 Output 2:
11 Code:
#include <bits/stdc++.h>
using namespace std;
int main() {
int n;cin>>n;
vector<int> v(n,0);
for(int i=0;i<n;i++){ cin>>v[i];}
int k;cin>>k;
int temp=k;
if(k>=v.size()) {cout<<*max_element(v.begin(),v.end());return 0;}
priority_queue<int,vector<int>,greater<int>> pq;
sort(v.begin(),v.end());
int idx;
for(int i=n-1;i>=0&&temp>0;i--) {
pq.push(v[i]);
temp--;
idx=i;
}
for(int i=idx-1;i>=0;i--){
int x= pq.top();
pq.pop();
x+=v[i];
pq.push(x);
}
int maxx=INT_MIN;
// for(auto x:pq) maxx=max(maxx,x);
while(!pq.empty()){
maxx=max(maxx,pq.top());
pq.pop();
}
cout<<maxx<<"\n";
return 0;
}Edge Case:
Input:
5
5 5 4 4 4
2 Output:
12 This test case initially failed, but the interviewer was satisfied with my greedy approach and selected me for the Hackathon Part B.