Maximum Compatibility Score Sum — Problem & Solution
Maximum Compatibility Score Sum solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.
Maximum Compatibility Score Sum is a medium coding problem on dynamic programming, bit manipulation and backtracking, asked in Amazon and Google interviews.
- Difficulty: Medium
- Topics: Dynamic Programming, Bit Manipulation, Backtracking, Bitmask
- Asked at: Amazon, Google
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
A survey has n yes/no questions. m students and m mentors answered it: students[i] and mentors[j] are arrays of n answers, each 0 or 1.
The compatibility score of a student and a mentor is the number of questions they answered the same way. Pair every student with a different mentor (a one-to-one assignment).
Return the maximum possible sum of the compatibility scores of the pairs.
Example 1
Input: students = [[1,0],[0,1]], mentors = [[0,1],[1,0]]
Output: 4
Explanation: Student 0 with mentor 1 and student 1 with mentor 0 agree on everything.
Example 2
Input: students = [[0,0]], mentors = [[1,1]]
Output: 0
Example 3
Input: students = [[1,1,1],[0,0,0]], mentors = [[1,0,1],[0,1,0]]
Output: 4
Constraints
m == students.length == mentors.lengthn == students[i].length == mentors[j].length1 <= m, n <= 8students[i][k] and mentors[j][k] are 0 or 1
Hints for Maximum Compatibility Score Sum
Hint 1
Precompute the score of every student–mentor pair: an
m x mtable.Hint 2
With m <= 8 even trying all m! assignments works, but a bitmask DP is cleaner.
Hint 3
Let
dp[mask]be the best total when the firstpopcount(mask)students are paired with the mentors inmask; extend by pairing the next student with each free mentor.
How to solve Maximum Compatibility Score Sum
This is an assignment problem on a tiny m x m score table: process the students in order and keep a bitmask of mentors already taken.
Approach
- Compute
score[i][j]= number of equal answers between studentiand mentorj. - Set
dp[0] = 0; visit masks in increasing order. - For
mask, the next student isi = popcount(mask); for every mentorjnot inmask, updatedp[mask | 1<<j]withdp[mask] + score[i][j]. - Return
dp[2^m - 1].
Why it works
Any assignment pairs students 0, 1, …, m-1 in turn with distinct mentors, i.e. it is a path from the empty mask to the full mask collecting exactly its scores. The best completion depends only on which mentors remain, so keeping the best score per mask is exact.
Complexity
- Time —
O(m · 2^m + m² · n) - Space —
O(2^m)
Pitfalls
- Pairing each student greedily with their best remaining mentor is not optimal.
- Compatibility counts matching answers, zeros included — not the number of shared 1s.
- The student index is the popcount of the mask; no second DP dimension is needed.
Reference solution
Python
from typing import List
def maxCompatibilitySum(students: List[List[int]], mentors: List[List[int]]) -> int:
m = len(students)
n = len(students[0])
score = [[sum(1 for q in range(n) if students[i][q] == mentors[j][q]) for j in range(m)] for i in range(m)]
full = 1 << m
dp = [-1] * full
dp[0] = 0
for mask in range(full):
if dp[mask] < 0:
continue
i = bin(mask).count("1")
if i >= m:
continue
for j in range(m):
if mask & (1 << j):
continue
nm = mask | (1 << j)
v = dp[mask] + score[i][j]
if v > dp[nm]:
dp[nm] = v
return dp[full - 1]Java
public static int maxCompatibilitySum(int[][] students, int[][] mentors) {
int m = students.length, n = students[0].length, full = 1 << m;
int[][] score = new int[m][m];
for (int i = 0; i < m; i++) {
for (int j = 0; j < m; j++) {
for (int q = 0; q < n; q++) if (students[i][q] == mentors[j][q]) score[i][j]++;
}
}
int[] dp = new int[full];
Arrays.fill(dp, -1);
dp[0] = 0;
for (int mask = 0; mask < full; mask++) {
if (dp[mask] < 0) continue;
int i = Integer.bitCount(mask);
if (i >= m) continue;
for (int j = 0; j < m; j++) {
if ((mask & (1 << j)) != 0) continue;
int nm = mask | (1 << j);
dp[nm] = Math.max(dp[nm], dp[mask] + score[i][j]);
}
}
return dp[full - 1];
}C++
int maxCompatibilitySum(vector<vector<int>>& students, vector<vector<int>>& mentors) {
int m = students.size(), n = students[0].size(), full = 1 << m;
vector<vector<int>> score(m, vector<int>(m, 0));
for (int i = 0; i < m; i++) {
for (int j = 0; j < m; j++) {
for (int q = 0; q < n; q++) if (students[i][q] == mentors[j][q]) score[i][j]++;
}
}
vector<int> dp(full, -1);
dp[0] = 0;
for (int mask = 0; mask < full; mask++) {
if (dp[mask] < 0) continue;
int i = __builtin_popcount(mask);
if (i >= m) continue;
for (int j = 0; j < m; j++) {
if (mask & (1 << j)) continue;
int nm = mask | (1 << j);
dp[nm] = max(dp[nm], dp[mask] + score[i][j]);
}
}
return dp[full - 1];
}JavaScript
var maxCompatibilitySum = function(students, mentors) {
var m = students.length, n = students[0].length, full = 1 << m;
var score = [];
for (var i = 0; i < m; i++) {
score.push([]);
for (var j = 0; j < m; j++) {
var s = 0;
for (var q = 0; q < n; q++) if (students[i][q] === mentors[j][q]) s++;
score[i].push(s);
}
}
var dp = new Array(full).fill(-1);
dp[0] = 0;
for (var mask = 0; mask < full; mask++) {
if (dp[mask] < 0) continue;
var st = 0;
for (var x = mask; x; x >>= 1) st += x & 1;
if (st >= m) continue;
for (var t = 0; t < m; t++) {
if (mask & (1 << t)) continue;
var nm = mask | (1 << t), v = dp[mask] + score[st][t];
if (v > dp[nm]) dp[nm] = v;
}
}
return dp[full - 1];
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 402 dynamic programming problems · the whole catalogue
Learn the technique: Dynamic Programming · Bit Manipulation