Katkat
Back

Solve Two OA Algorithm Problems

UberSoftware Engineer · Online Assessment
HardSoftware EngineerOnline AssessmentCoding & Algorithms

Last updated

This problem tests your ability to optimize resource allocation using a greedy approach with a priority queue and to determine graph reachability within a constrained network.

Problem 1: Throughput Maximization

You are managing a fleet of autonomous vehicles that process data tasks. You are given an array tasks where tasks[i] represents the profit of task i, and an array costs where costs[i] is the computational capacity required to process it. You have a total capacity limit. However, tasks must be processed in non-decreasing order of their computational costs.

Given the arrays tasks and costs, and an integer capacity, return the maximum profit achievable such that the total cost of selected tasks does not exceed capacity and the selected tasks follow the non-decreasing cost constraint.

Example

Input: tasks = [10, 20, 30], costs = [1, 2, 3], capacity = 3 Output: 30 Explanation: You can pick task 1 and 2 (cost 1+2=3, profit 10+20=30) or task 3 (cost 3, profit 30). Both are valid.

Problem 2: Network Activation

You are given a grid of size N x M representing sensors. Some sensors are 'active' (represented by 1) and others are 'inactive' (0). An active sensor can trigger its neighbors (up, down, left, right) if the neighbor's value is 0. This activation propagates recursively. Given a starting sensor (r, c), determine the total number of sensors that become active after the propagation stabilizes.

Constraints

  • 1 <= N, M <= 1000
  • The grid contains only 0s and 1s.

Example

Input: grid = [[1, 0], [0, 0]], start = (0, 0) Output: 4 Explanation: The sensor at (0,0) is active. It activates (0,1) and (1,0). Once (1,0) is active, it activates (1,1). All sensors become active.

Hints

Hint 1

For Problem 1, sort the tasks by their cost first to satisfy the non-decreasing constraint and treat it as a variation of the knapsack problem.

Hint 2

For Problem 2, recognize this as a graph traversal problem where active sensors act as nodes and adjacent 0s are edges waiting to be traversed.

Hint 3

Use Breadth-First Search (BFS) or Depth-First Search (DFS) for Problem 2 to explore the connectivity of the sensors starting from the source coordinate.

Follow-up questions

  • How would you modify Problem 1 if tasks could be processed in any order but you have a penalty for switching between tasks of different types?
  • For Problem 2, how would you handle the calculation if the activation has a decay factor where an active sensor only triggers its neighbor if the neighbor is within a certain distance?
  • What is the space complexity of your BFS/DFS implementation in Problem 2 if the entire grid is empty?