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 hard difficulty Coding & Algorithms question, commonly asked during Technical Screen rounds at Microsoft.

What role is this question designed for?

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

Find all balanced k in a permutation | Microsoft Coding Question

Find all balanced k in a permutation

Company: Microsoft

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: hard

Interview Round: Technical Screen

You are given a permutation \(p\) of length \(n\) containing each integer from \(1\) to \(n\) exactly once. For each \(k\) where \(1 \le k \le n\), determine whether there exists a **contiguous subarray** of \(p\) whose elements are **exactly** the set \(\{1,2,\dots,k\}\) (in any order). - If such a subarray exists, call \(k\) **balanced**. - Output a binary string \(s\) of length \(n\) where \(s[k]\) (1-based) is `'1'` if \(k\) is balanced, otherwise `'0'`. ### Input - Integer \(n\) - Array \(p\) of length \(n\), a permutation of \([1..n]\) ### Output - A string of length \(n\) consisting of `'0'` and `'1'` ### Notes / expectations - Aim for an efficient algorithm (e.g., \(O(n)\) or \(O(n \log n)\)), not enumerating all subarrays.

Quick Answer: This question evaluates understanding of permutations, array range reasoning, index mapping, and efficient algorithm design for detecting contiguous subarrays that exactly contain the prefix set {1..k}.

You are given a permutation p of length n containing each integer from 1 to n exactly once. For each k from 1 to n, determine whether there exists a contiguous subarray of p whose elements are exactly the set {1, 2, ..., k} in any order. If such a subarray exists, then k is called balanced. Return a binary string s of length n where s[k-1] is '1' if k is balanced, and '0' otherwise.

Constraints

1 <= n <= 2 * 10^5
p is a permutation of the integers from 1 to n

Examples

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

Expected Output: '11101'

Explanation: For k = 1, 2, and 3, the positions of {1..k} form contiguous segments. For k = 4 they do not. For k = 5, the whole array works.

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

Expected Output: '11011'

Explanation: The sets {1}, {1,2}, {1,2,3,4}, and {1,2,3,4,5} each occupy contiguous positions, but {1,2,3} does not.

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

Expected Output: '1001'

Explanation: Only k = 1 and k = 4 are balanced. The values {1,2} and {1,2,3} are too spread out.

Input: (1, [1])

Expected Output: '1'

Explanation: The only value forms a contiguous subarray by itself.

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

Expected Output: '111111'

Explanation: Every prefix {1..k} is already a contiguous subarray.

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

Expected Output: '1011001'

Explanation: Balanced values are k = 1, 3, 4, and 7 based on the span of positions of values 1 through k.

Hints

Instead of checking every subarray, think about where each value 1, 2, ..., k appears in the permutation.
For a fixed k, the values 1 through k form a valid contiguous subarray exactly when their minimum and maximum positions span a segment of length k.

Quick Overview

This question evaluates understanding of permutations, array range reasoning, index mapping, and efficient algorithm design for detecting contiguous subarrays that exactly contain the prefix set {1..k}.