Uber OA || SDE-2

I participated in an Online Assessment for an SDE-2 role at Uber. During this assessment, I was presented with the following two algorithmic problems:

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

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

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