How should I practice Balanced Prefix Sets in a Permutation?

Start by reading the full statement, solve the visible examples, then compare the pattern against related Uber online assessment problems in FastPrep.

Is Balanced Prefix Sets in a Permutation associated with Uber?

FastPrep tags this as a Uber coding interview or online assessment practice problem when the problem catalog has that company context.

FastPrep

Problem · Array

Balanced Prefix Sets in a Permutation

● MediumUberFULLTIMEOA

See Uber hiring insights

You are given a permutation p of the integers 1 through n.

For each k from 1 to n, determine whether there exists a contiguous subarray whose set of values is exactly {1, 2, ..., k}.

Build a binary string of length n. The k-th character should be '1' if such a subarray exists for that k, otherwise it should be '0'.

Function Description

Complete the function balancedPrefixSetsMask in the editor below.

balancedPrefixSetsMask has the following parameter:

int[] p: a permutation of 1..n

Returns

String: a binary string whose k-th character indicates whether {1, 2, ..., k} appears as the value set of some contiguous subarray.

Examples

01 · Example 1

p = [2, 1, 4, 3]
return = "1101"

For k = 1, the subarray [1] works. For k = 2, the subarray [2, 1] works. For k = 3, the values {1, 2, 3} do not occupy a contiguous span. For k = 4, the whole array works.

02 · Example 2

p = [3, 1, 2, 5, 4]
return = "11101"

The sets {1}, {1, 2}, and {1, 2, 3} all appear within contiguous spans. The set {1, 2, 3, 4} does not. The whole array gives {1, 2, 3, 4, 5}.

Constraints

The source thread did not provide explicit numeric bounds.

p is a permutation of the integers 1..n.
The output string has length n.
Each character is either '1' or '0'.