Katkat
Back

How to maximize rewards with exactly k tasks

MathWorksSoftware Engineer · Technical Screen
EasySoftware EngineerTechnical ScreenCoding & Algorithms

Last updated

This Coding & Algorithms question evaluates a candidate's ability to perform combinatorial optimization and benefit-based assignment reasoning on arrays, testing algorithm design, complexity-aware implementation, and quantitative decision-making in constrained assignment problems.

You are assigning n independent tasks to two interns.

  • Each task must be done by exactly one intern.
  • If intern 1 does task i, you earn reward1[i] points.
  • If intern 2 does task i, you earn reward2[i] points.
  • Intern 1 must be assigned exactly k tasks; intern 2 gets the remaining n - k tasks.
  • Tasks can be assigned in any order (no contiguity requirement).

Goal: Return the maximum total points achievable.

Input

  • reward1: integer array of length n
  • reward2: integer array of length n
  • k: integer (0 ≤ k ≤ n)

Output

  • An integer: the maximum possible total reward.

Notes / Expected Complexity

Design an algorithm that works efficiently for large n (e.g., up to 10^5).