Microsoft OA
Summary
I encountered this specific algorithmic problem during a Microsoft Online Assessment, which focused on maximizing the smaller of two sums by selecting a fixed number of elements from two arrays.
Full Experience
I encountered this problem during a Microsoft Online Assessment. It involved selecting exactly k indices from two integer arrays, A and B, both of length n. My goal was to maximize the smaller value between the total sum from A and the total sum from B for the selected indices.
Interview Questions (1)
Problem Statement
You are given two integer arrays A and B, both of length n. You need to select exactly k indices (the same indices in both arrays). Your goal is to maximize the smaller value between the total sum from A and the total sum from B for the selected indices.
In other words, when you pick k positions, you calculate:
- sumA = sum of selected elements from A
- sumB = sum of selected elements from B
Then you take the smaller of these two sums. You need to make that smaller value as large as possible.
Example
A = [6, 3, 6, 5, 1]
B = [1, 4, 5, 9, 2]
k = 3
If you pick indices {0, 2, 3}:
sumA = 6 + 6 + 5 = 17
sumB = 1 + 5 + 9 = 15
The smaller value is 15.
This is the maximum possible, so the answer is 15.