How do I practice coding and algorithm questions?

Use PracHub's coding console to write, test, and debug your solutions in Python or JavaScript. View hints, test against sample inputs, and compare with official solutions.

What difficulty level is this coding question?

This is a medium difficulty Coding & Algorithms question, commonly asked during Take-home Project rounds at Uber.

What role is this question designed for?

This question is commonly asked for Software Engineer candidates at Uber during technical interviews.

Determine balanced k values in a permutation

Quick Overview

This question evaluates algorithmic reasoning about permutations and contiguous subarray properties, testing skills in array manipulation, positional reasoning, combinatorial insight, and complexity-aware algorithm design within the Coding & Algorithms domain.

Company: Uber

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Take-home Project

You are given a permutation `p` of the integers `1..n`. For a number `k` (where `1 <= k <= n`), call `k` **balanced** if there exists a contiguous subarray `p[l..r]` such that: - `r - l + 1 = k`, and - the multiset of values in `p[l..r]` is exactly `{1, 2, ..., k}` (i.e., the subarray is a permutation of `1..k`). Your task: for every `k = 1..n`, determine whether `k` is balanced and return a binary string `s` of length `n` where: - `s[k-1] = '1'` if `k` is balanced - `s[k-1] = '0'` otherwise ### Input - An integer `n` - A permutation `p` of length `n` *(If your platform uses multiple test cases, solve independently per test case.)* ### Output - A binary string of length `n`. ### Example If `n = 5` and `p = [4, 1, 3, 2, 5]`, you should output a string of length 5 indicating which `k` are balanced. ### Constraints Assume `n` can be large (e.g., up to `2e5`), so an `O(n log n)` or `O(n)` approach is expected.

Quick Answer: This question evaluates algorithmic reasoning about permutations and contiguous subarray properties, testing skills in array manipulation, positional reasoning, combinatorial insight, and complexity-aware algorithm design within the Coding & Algorithms domain.

You are given a permutation p of the integers 1 through n. For a number k (1 <= k <= n), call k balanced if there exists a contiguous subarray of length k whose elements are exactly the set {1, 2, ..., k} in any order. Return a binary string s of length n where s[k-1] is '1' if k is balanced and '0' otherwise. Because p is a permutation, each value appears exactly once. The challenge is to determine the answer for every k efficiently.

Constraints

1 <= n <= 2 * 10^5
p is a permutation of the integers 1..n
An O(n) or O(n log n) solution is expected

Examples

Input: (5, [4, 1, 3, 2, 5])

Expected Output: "10111"

Explanation: For k=1, the value 1 appears alone, so it is balanced. For k=2, positions of 1 and 2 are not adjacent. For k=3, values {1,2,3} occupy positions 2..4. For k=4 and k=5, the required values also occupy a contiguous block.

Input: (1, [1])

Expected Output: "1"

Explanation: The only possible k is 1, and the single-element subarray [1] matches {1}.

Input: (4, [2, 1, 4, 3])

Expected Output: "1101"

Explanation: k=1 and k=2 are balanced because 1 and then {1,2} occupy contiguous positions. For k=3, positions of {1,2,3} span length 4, so it fails. k=4 is balanced because the whole array contains {1,2,3,4}.

Input: (6, [1, 2, 3, 4, 5, 6])

Expected Output: "111111"

Explanation: For every k, the first k elements are exactly {1,2,...,k}, so every k is balanced.

Input: (5, [3, 4, 5, 1, 2])

Expected Output: "11001"

Explanation: k=1 is balanced by the subarray [1], and k=2 is balanced by [1,2]. For k=3 and k=4, the positions of 1..k are too spread out. k=5 is balanced because the full array contains all values 1..5.

Solution

def solution(n, p):
    if n == 0:
        return ""

    pos = [0] * (n + 1)
    for i, value in enumerate(p):
        pos[value] = i

    answer = []
    min_pos = pos[1]
    max_pos = pos[1]

    for k in range(1, n + 1):
        if k > 1:
            if pos[k] < min_pos:
                min_pos = pos[k]
            if pos[k] > max_pos:
                max_pos = pos[k]

        if max_pos - min_pos + 1 == k:
            answer.append('1')
        else:
            answer.append('0')

    return ''.join(answer)

Time complexity: O(n). Space complexity: O(n).

Hints

Instead of checking every subarray, first record the position of each value from 1 to n.
For a fixed k, the numbers 1..k can form a valid length-k subarray exactly when their minimum and maximum positions span k indices.

Quick Overview