Uber SDE-1/2/SDE-Intern OA Questions | Kumar K | December 2025 |Set 001

Question

You have presented two distinct algorithmic problems: Balanced Numbers and Touring a Building.

1. Balanced Numbers (Permutation Analysis)

❓ Question Reiteration

Given a permutation of length n, determine if a number k is balanced. A number k (where 1 \le k \le n) is balanced if, when you choose two indices i and r such that 1 \le i < r \le n and the sub-array P[i..r] is a permutation of length k, the number of such indices i and r is exactly one.

A permutation of length n contains each integer from 1 to n exactly once in any order.

 * Function: countBalancedNumbers(int[] P)

 * Input: P, the given permutation.

 * Output: A binary string of length n, where the k-th character is '1' if k is a balanced number and '0' otherwise.

 Example Walkthrough

For P = [4, 1, 3, 2] (n=4):

 * For k=1: Choose i=2, r=2, so P[2..2]=[1]. This is a permutation of length 1. Count is 1. So, k=1 is balanced ('1').

 * For k=2: No pair of indices results in a permutation of length 2. (Possible sub-arrays are [4, 1], [1, 3], [3, 2], [4, 1, 3], [1, 3, 2], [4, 1, 3, 2]). None of these are a permutation of \{1, 2\}. Count is 0. So, k=2 is not balanced ('0').

 * For k=3: Choose i=2, r=4, so P[2..4]=[1, 3, 2]. This is a permutation of length 3 (\{1, 2, 3\}). Count is 1. So, k=3 is balanced ('1').

 * For k=4: Choose i=1, r=4, so P[1..4]=[4, 1, 3, 2]. This is a permutation of length 4 (\{1, 2, 3, 4\}). Count is 1. So, k=4 is balanced ('1').

The final answer is "1011".