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

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.

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

Read the full Microsoft Software Engineer interview experience this question came from

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.

Hints

  1. Instead of checking every subarray, think about where each value 1, 2, ..., k appears in the permutation.
  2. 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.

Loading coding console...