Uber SDE-2 Online Assessment Interview Questions

Problem Statement You are given a permutation p of size n. For each prefix p[1..k] (where 1 ≤ k ≤ n), determine whether it forms a valid permutation of integers from 1 to k. A prefix is

Problem Statement You are given a permutation p of size n. For each prefix p[1..k] (where 1 ≤ k ≤ n), determine whether it forms a valid permutation of integers from 1 to k. A prefix is valid if it contains every integer from 1 to k exactly once.

Return a binary string of length n where: - '1' → prefix p[1..k] is a permutation of [1..k] - '0' → otherwise --- ## Function Signature

cpp string countBalancedNumbers(vector<int> p)

Constraints - 1 ≤ n ≤ 2 * 10^5 - p is a permutation of integers from 1 to n ---

Example

Input

n = 4 p = [1, 4, 2, 3]

Output

1001

--- # 2️⃣ Minimum Time

Problem Statement You are given n plates placed on a 2D grid. Each plate has magnetic attraction power d. Two plates are connected if the Euclidean distance between them is ≤ d. If you collect one plate, all plates connected to it (directly or indirectly) are collected in the same second. You can collect any one plate per second.

Return the minimum number of seconds required to collect all plates. --- ## Function Signature

cpp int getMinTime(int n, int d, vector<int> x, vector<int> y)

Constraints - 1 ≤ n ≤ 10^5 - 0 ≤ d ≤ 10^9 - 0 ≤ x[i], y[i] ≤ 10^9 ---

Example

Input

n = 4 d = 1 x = [0, 0, 1, 2] y = [0, 1, 0, 2]

Output

2