Hacker's Team

Reported in interviews at Citadel

Problem statement

A cyber-security firm builds a team of hackers. For each index i, the skill of the i-th candidate on team A is team_a[i] and on team B is team_b[i]. A contiguous window of indices [i..j] can form a strong team if, at every index k in the window, you select the value from either team_a[k] or team_b[k] so that the resulting sequence of selected skills is non-decreasing. Choose the window that maximizes its length (j - i + 1) and return that maximum length.

Implement:

def getMaxSubarrayLen(team_a, team_b):

Both arrays have the same length n; the function returns an integer.

Example: team_a = [5, 2, 4, 1], team_b = [3, 6, 2, 2]. Over the window of indices 1..3 you can pick team_a[1]=2, team_b[2]=2, team_b[3]=2, giving the non-decreasing sequence [2, 2, 2] of length 3. No window of length 4 works, so the answer is 3.

Constraints: $1 \le n \le 10^5$, $1 \le \text{team\_a}[i], \text{team\_b}[i] \le 10^9$.

Show hint

When you try to extend a valid window by one more index, which single piece of information from the previous index do you actually need?

Relevant roles: ML Engineer, Forward Deployed Engineer and AI Engineer.

Related free problems