uber logo
Uber· SDE-2

Uber OA || SDE-2

Posted
19 Feb 2026
489 reads

Summary

I recently completed an Online Assessment for an SDE-2 role at Uber, which involved solving two distinct algorithmic problems.

How it went

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

Questions asked (2)

  1. 01

    Permutation Prefix Validation

    Data Structures & Algorithms

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

    Minimum Time

    Data Structures & Algorithms

    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
    

Know someone preparing? Send it to them:WhatsAppLinkedInX

Interviewed at Uber recently?

Write up your rounds while you still remember the questions. It helps the next person more than you would think.

Share your experience
Discussion 0

Questions for the author, or how your own interview compared.

Join the discussion

Sign in with Google to comment or ask the author a question.

No comments yet

Be the first to share your thoughts and start the discussion!