Maximum of Fixed-Window Minimums
Company: Oracle
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Technical Screen
Given an integer array `A` and a window length `x`, consider every contiguous subarray of length `x`. Find the minimum value in each window, then return the maximum of those minimum values.
### Function
Implement `maxOfWindowMinimums(A, x)`. Use the exact integer representation described below for this console interface.
- `A` is a nonempty array of integer values, and `n` is its length.
- `x` is an integer satisfying `1 <= x <= n`.
- Return one value for this specified window length, not an answer for every possible length.
- Negative values and repeated values are allowed. Windows retain their original contiguous positions in `A`.
### Exact integer representation
This console represents integer values as canonical decimal strings so they retain their exact values in every supported language. This is an input/output representation convention; it does not impose a maximum integer magnitude.
- `A` is an array of strings representing signed integers.
- `x` is a string representing a positive integer. Its numeric value satisfies the bounds above.
- Return the selected integer value as a canonical decimal string.
- A canonical decimal string is `"0"`, a sequence of ASCII digits beginning with `1` through `9`, or `"-"` followed by such a sequence. It has no leading plus sign, leading zeroes, whitespace, or negative zero.
- Compare represented integer values, not the lexicographic order of their strings. Do not round values or restrict them to a fixed-width integer type.
### Example
```text
A = ["1", "3", "-1", "5", "3", "6"]
x = "3"
Output: "3"
```
The table below shows the represented integer values:
| Window | Minimum |
| --- | --- |
| `[1, 3, -1]` | `-1` |
| `[3, -1, 5]` | `-1` |
| `[-1, 5, 3]` | `-1` |
| `[5, 3, 6]` | `3` |
The maximum of the four minima is `3`, so return `"3"`.
For a numeric window length of 1, every element is its own window. For a numeric window length of `n`, there is exactly one window containing the entire array. The result follows the same rule in both cases.
Aim for an algorithm that uses a linear number of integer comparisons in `n`. Account separately for the cost of processing decimal digits.
Overview: Find the maximum among all fixed-length sliding-window minima, handling negative values, duplicates, and boundary window sizes with a linear-time approach.
Read the full Oracle Software Engineer interview experience this question came from
Given an integer array `A` and a window length `x`, consider every contiguous subarray of length `x`. Find the minimum value in each window, then return the maximum of those minimum values.
### Function
Implement `maxOfWindowMinimums(A, x)`. Use the exact integer representation described below for this console interface.
- `A` is a nonempty array of integer values, and `n` is its length.
- `x` is an integer satisfying `1 <= x <= n`.
- Return one value for this specified window length, not an answer for every possible length.
- Negative values and repeated values are allowed. Windows retain their original contiguous positions in `A`.
### Exact integer representation
This console represents integer values as canonical decimal strings so they retain their exact values in every supported language. This is an input/output representation convention; it does not impose a maximum integer magnitude.
- `A` is an array of strings representing signed integers.
- `x` is a string representing a positive integer. Its numeric value satisfies the bounds above.
- Return the selected integer value as a canonical decimal string.
- A canonical decimal string is `"0"`, a sequence of ASCII digits beginning with `1` through `9`, or `"-"` followed by such a sequence. It has no leading plus sign, leading zeroes, whitespace, or negative zero.
- Compare represented integer values, not the lexicographic order of their strings. Do not round values or restrict them to a fixed-width integer type.
### Example
```text
A = ["1", "3", "-1", "5", "3", "6"]
x = "3"
Output: "3"
```
The table below shows the represented integer values:
| Window | Minimum |
| --- | --- |
| `[1, 3, -1]` | `-1` |
| `[3, -1, 5]` | `-1` |
| `[-1, 5, 3]` | `-1` |
| `[5, 3, 6]` | `3` |
The maximum of the four minima is `3`, so return `"3"`.
For a numeric window length of 1, every element is its own window. For a numeric window length of `n`, there is exactly one window containing the entire array. The result follows the same rule in both cases.
Aim for an algorithm that uses a linear number of integer comparisons in `n`. Account separately for the cost of processing decimal digits.
Constraints
- A is a nonempty array of canonical signed decimal strings; repeated and negative values are valid.
- x is a canonical positive decimal string representing 1 through len(A).
- Consider original contiguous windows of exactly x entries and return one maximum of their minima.
- Comparisons use integer values; no fixed-width magnitude or length bound is added.
Examples
Input: (['1', '3', '-1', '5', '3', '6'], '3')
Expected Output: '3'
Explanation: The source table has four minima and the final one is greatest.
Input: (['-9223372036854775809'], '1')
Expected Output: '-9223372036854775809'
Explanation: The only window returns its only exact signed value.
Hints
- A window is contiguous and has exactly the specified length.
- Return the integer value, so equal optimal windows do not require selecting a position.