How do I approach Coding & Algorithms interview questions?

Coding & Algorithms questions require understanding of core concepts and practice. PracHub provides solutions with explanations to help you master coding & algorithms interviews.

What difficulty level is this interview question?

This is a hard difficulty Coding & Algorithms question, commonly asked during Take-home Project rounds at Uber.

What role is this question designed for?

This question is commonly asked for Software Engineer candidates at Uber during technical interviews.

Solve Two OA Algorithm Problems | Uber Interview Question

Q: Solve Two OA Algorithm Problems

These problems evaluate algorithmic optimization and graph connectivity competencies, specifically cost-constrained integer resource allocation for throughput maximization and spatial adjacency/connected-component reasoning for activation propagation.

Problem 1: Maximize Pipeline Throughput

A pipeline contains n services connected in series. The overall pipeline throughput is the minimum throughput among all services.

For service i:

Its base throughput is t[i] .
You may scale it up by a nonnegative integer number of times x[i] .
After scaling, its throughput becomes t[i] * (1 + x[i]) .
The scaling cost is x[i] * cost[i] .

You are given arrays t, cost, and an integer budget. Choose the scaling counts for all services so that the total cost does not exceed budget, and return the maximum possible overall pipeline throughput.

Problem 2: Minimum Activations for Chain Adsorption

You are given n balls on a 2D grid, where ball i is located at coordinates (x[i], y[i]). A ball can trigger another ball if:

they are in the same row ( y[i] == y[j] ) or the same column ( x[i] == x[j] ), and
the distance between them along that row or column is at most d .

Adsorption is transitive: if ball A can trigger ball B, and ball B can trigger ball C, then activating A will eventually absorb B and C as well.

In one operation, you may choose any single ball to activate. Return the minimum number of activations required to absorb all balls.

Problem 1: Maximize Pipeline Throughput

A pipeline contains n services connected in series. The overall pipeline throughput is the minimum throughput among all services.

For service i:

Its base throughput is t[i] .

You may scale it up by a nonnegative integer number of times x[i] .

After scaling, its throughput becomes t[i] * (1 + x[i]) .

The scaling cost is x[i] * cost[i] .

Problem 2: Minimum Activations for Chain Adsorption

You are given n balls on a 2D grid, where ball i is located at coordinates (x[i], y[i]). A ball can trigger another ball if:

they are in the same row ( y[i] == y[j] ) or the same column ( x[i] == x[j] ), and

the distance between them along that row or column is at most d .

Adsorption is transitive: if ball A can trigger ball B, and ball B can trigger ball C, then activating A will eventually absorb B and C as well.

In one operation, you may choose any single ball to activate. Return the minimum number of activations required to absorb all balls.

Solve Two OA Algorithm Problems

Quick Overview

Problem 1: Maximize Pipeline Throughput

Problem 2: Minimum Activations for Chain Adsorption

Submit Your Answer

Solve Two OA Algorithm Problems

Quick Overview

Problem 1: Maximize Pipeline Throughput

Problem 2: Minimum Activations for Chain Adsorption

Submit Your Answer