Uber Online Assessment SDE2/SDE3
Summary
I completed Uber's Online Assessment for an SDE-2/SDE-3 role and was able to solve both problems.
Full Experience
Today, I completed the Uber Online Assessment for an SDE-2/SDE-3 role.
The assessment was conducted on HackerRank under strict proctoring (camera monitored) and consisted of 2 problems to be solved in 90 minutes.
Problem 1: Given a permutation of size n, we needed to construct a binary string of length n. For each k (1 ≤ k ≤ n), determine whether k is “balanced”.
A value k is considered balanced if there exists a subarray [l, r] such that the elements in that subarray form a permutation of numbers from 1 to k.
Constraints: 1 ≤ n ≤ 2 × 10^5
Examples: Input: [1, 3, 2, 4] Output: "1011"
Input: [3, 1, 2, 4] Output: "1111"
Problem 2: We are given n plates placed on a 2D plane with coordinates defined by arrays x and y.
Two plates can be collected together if:
- They lie in the same row (same x) or same column (same y), and
- Their distance is ≤ d
The goal is to determine the minimum time required to collect all plates, where collecting one plate allows collecting all plates connected to it under these rules.
Constraints: 1 ≤ n ≤ 10^5 0 ≤ d ≤ 10^9 0 ≤ x[i], y[i] ≤ 10^9
Example: n = 3, d = 1 x = [0, 2, 1] y = [0, 1, 2] Output: 3
Overall, the assessment focused heavily on efficient data structures and problem-solving under constraints (O(n log n) / O(n) solutions).
It was a great experience working through these problems.
I am able to solve both problems.
Interview Questions (2)
Balanced Subarray Permutation
Given a permutation of size n, construct a binary string of length n where for each k (1 ≤ k ≤ n) the k-th character is '1' if k is balanced and '0' otherwise.
A value k is considered balanced if there exists a subarray [l, r] such that the elements in that subarray form a permutation of numbers from 1 to k.
Constraints
- 1 ≤ n ≤ 2 × 10^5
Examples
- Input: [1, 3, 2, 4] Output: "1011"
- Input: [3, 1, 2, 4] Output: "1111"
Collect Plates with Distance Constraint
You are given n plates placed on a 2D plane with coordinates given by arrays x and y.
Two plates can be collected together if:
- They lie in the same row (same
x) or the same column (samey), and - Their Manhattan distance is ≤ d.
Collecting one plate allows you to collect all plates that are connected to it through these rules. Determine the minimum time required to collect all plates.
Constraints
- 1 ≤ n ≤ 10^5
- 0 ≤ d ≤ 10^9
- 0 ≤ x[i], y[i] ≤ 10^9
Example
- n = 3, d = 1
- x = [0, 2, 1]
- y = [0, 1, 2]
- Output: 3