The coding problem involved finding all possible Minimum Excluded Values (MEX) of an integer array after performing at most one increment operation. The challenge was understanding how a single element modification could change the MEX and determining all reachable values efficiently.
Interview Details
Online Assessment — Coding: Find All Possible MEX Values
Given an integer array memoryBlocks of length n, every element satisfies 0 <= memoryBlocks[i] < n。 The MEX (Minimum Excluded Value) of an array is the smallest non-negative integer that does not appear in the array.
For example:
The MEX of [0, 1, 3] is 2.
The MEX of [1, 2, 3] is 0.
The MEX of [0, 1, 2] is 3.
The task is to find all distinct MEX values that can be obtained after performing at most one operation. An operation consists of choosing one element and increasing its value by exactly 1, provided the element is less than n - 1. The function should return the achievable MEX values in ascending order.
Function Signature
deffindValidSizes(memoryBlocks):# Return sorted possible MEX valuespass
deffindValidSizes(memoryBlocks):# Return sorted possible MEX valuespass
Example Test Cases
The following examples illustrate the rules using representative arrays.
Input:
memoryBlocks = [0, 1, 2]
Output:
[0, 1, 3]
Explanation:
No operation -> [0, 1, 2] -> MEX = 3
Increment 0:
[1, 1, 2] -> MEX = 0
Increment 1:
[0, 2, 2] -> MEX = 1
The value 2 cannot be incremented because n - 1 = 2.
Input:
memoryBlocks = [0, 1, 2]
Output:
[0, 1, 3]
Explanation:
No operation -> [0, 1, 2] -> MEX = 3
Increment 0:
[1, 1, 2] -> MEX = 0
Increment 1:
[0, 2, 2] -> MEX = 1
The value 2 cannot be incremented because n - 1 = 2.
Input:
memoryBlocks = [0, 0, 1, 1, 3, 4]
Output:
[2, 5]
Explanation:
No operation -> MEX = 2
Increment one occurrence of 1:
[0, 0, 1, 2, 3, 4] -> MEX = 5
Other allowed increments do not produce
additional MEX values.
Input:
memoryBlocks = [0, 0, 1, 1, 3, 4]
Output:
[2, 5]
Explanation:
No operation -> MEX = 2
Increment one occurrence of 1:
[0, 0, 1, 2, 3, 4] -> MEX = 5
Other allowed increments do not produce
additional MEX values.
Part 1 — Brute Force with a Frequency Array
The initial idea was to construct a frequency array representing how many times each integer appeared. The original MEX could be calculated by scanning the frequency array for the first missing number. Since performing no operation was allowed, this value was included in the result immediately.
For each eligible element, the algorithm could temporarily increment its value, recompute the MEX, and then restore the frequency counts before trying the next element. A cleaned-up implementation of this simulation approach is:
deffindValidSizesBrute(memoryBlocks): n =len(memoryBlocks) freq =[0]*(n +1)for value in memoryBlocks: freq[value]+=1defget_mex(): mex =0while freq[mex]>0:
deffindValidSizesBrute(memoryBlocks): n =len(memoryBlocks) freq =[0]*(n +1)for value in memoryBlocks: freq[value]+=1defget_mex(): mex =0while freq[mex]>0:
Unlock Full Details
Create a free account to unlock this interview experience report.