Question

Microsoft | OA Coding Questions and Solutions | Set - 21 | 2022

Answer 1

Got this question in microsoft OA round:

 

A garbage truck collects plastic, metal and glass garbages(one at a time) from N houses. Array D consists of time taken by the truck to carry a particular garbage from ith house. Array T consists of string values(M -> Metal, G -> Glass, P -> Plastic) stating the type of garbages present in ith house.
Calculate the minimum time taken by the truck to collect all the garbages and return back to its garage.

 

Example Test Cases:
Test Case 1:

 

Input:
D: [3, 2, 4]
T: ["MPM", "", "G"]

Output:
19

Explanation: For house at 0th house metal truck will take 3 hours to arrive, 
2 hours to pick up garbage and 3 hours to go back i.e. 8 hours total. 
Plastic truck will take 3 hours to arrive at 0th house, 1 hour to pick up 
garbage and 3 hours to go back again, total of 7 hours. Glass truck will take 3+2+4=9hours 
to arrive at 2nd house, 1 hour to pick up garbage and 9 hours again to go back, 
making it a total time of 19 hours. Hence, the minimum time taken for all the 
garbages to be collected is 19 hours.

 

Test Case 2:

 

Input:
D: [2,1,1,1,2]
T: ["", "PP", "PP", "GM", ""]

Output:
12

Explanation: Plastic truck will take 4 hours to reach 2th house, 2 hours to 
collect from 2th house, 2 hours to collect from 1th house and 4 hours to go 
back again, total 12 hours. Glass truck will take 5 hours to arrive at 3rd house, 
1 hour to collect garbage and 5 hours to go back, making a total of 11 hours. 
Same for metal truck.

 

Constraints:
Number of elements in D and T array can have max of 10^5.
Each string length in T array can have max length of 10^5.

 

Answer 2

struct counter {
	int arr[26] = {0};
};

int solve(vector<int> &d, vector<string> &t) {
	int n=d.size(), m=t.size();
	assert(n==m);
	vector<counter>count(n+1);
	for(int i=0;i<n;++i) {
		int sz=t[i].size();
		counter c;
		for(int j=0;j<sz;++j) {
			c.arr[t[i][j] - 'A']++;
		}
		count[i] = c;
	}
	int ans = 0; 
	for(char ch:string("PGM")) {
		int cur = 0, mx = 0;
		for(int i=0;i<n;++i) {
			if(count[i].arr[ch - 'A'] > 0) {
				cur += 2*d[i];
				cur += count[i].arr[ch - 'A'];
				mx = max(mx, cur);
			} else {
				cur += 2*d[i];
			}
		}
		ans = max(ans, mx);
	}
	cout<<ans<<"\n";
	return ans;
}

int32_t main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);
  vector<int> d1 = {3, 2, 4};
  vector<string> t1 = {"MPM", "", "G"};
  assert(solve(d1,t1) == 19);
  vector<int> d2 = {2,1,1,1,2};
  vector<string> t2 = {"", "PP", "PP", "GM", ""};
  assert(solve(d2,t2) == 12);
  return 0;
}