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

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}.

hard
Microsoft
Coding & Algorithms
Software Engineer

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'

Loading coding console...

Quick Overview

Find all balanced k in a permutation

Constraints

Examples

Hints