Katkat
Back

Maximize Throughput and Count Trigger Components

UberSoftware Engineer · Technical Screen
MediumSoftware EngineerTechnical ScreenCoding & Algorithms

Last updated

This problem tests your ability to optimize resource allocation using a greedy strategy and to identify connected components in a grid-based graph using traversal techniques.

Part 1: Throughput Optimization

You are managing a processing pipeline with n stages, each requiring a specific cost c[i] to increase its throughput by 1 unit. You have a total budget B. You want to maximize the total throughput of the pipeline, where the throughput of the entire system is limited by the bottleneck stage (the stage with the lowest throughput). Initially, all stages have a throughput of 0.

Implement the function max_throughput(costs, budget).

Part 2: Trigger Components

In a map, certain regions are marked as 'sensitive' (represented by 1) and others are 'stable' (represented by 0). A 'trigger' must be manually placed in each connected component of sensitive regions to maintain system integrity. Two sensitive regions are connected if they are horizontally or vertically adjacent.

Implement the function count_triggers(grid).

Examples

Throughput: costs = [2, 3, 1], budget = 5 Returns 2. Explanation: You can raise the throughput of all three stages to 1 (cost 6, exceeds budget). Alternatively, increase the cheapest stages to reach a uniform throughput of 1 first, then use remaining budget to increase the bottleneck.

Triggers: grid = [[1, 1, 0], [0, 1, 0], [0, 0, 1]] Returns 2. Explanation: The cluster of 1s in the top-left forms one component, and the single 1 in the bottom-right forms a second.

Hints

Hint 1

For the throughput problem, consider using a binary search on the potential uniform throughput value or a greedy approach using a min-priority queue.

Hint 2

For the trigger components problem, treat the grid as an adjacency matrix and use Breadth-First Search (BFS) or Depth-First Search (DFS) to traverse and mark visited nodes.

Hint 3

In the throughput problem, remember that the bottleneck limits the entire system, so increasing the throughput of a non-bottleneck stage does not increase overall system throughput.

Follow-up questions

  • How would your throughput solution change if stages had a maximum capacity limit?
  • How would you optimize the trigger counting if the grid was extremely large and sparse, potentially not fitting in memory?
  • What is the time complexity of your component counting approach in terms of grid dimensions R and C?