6 hours ago

admin 1.9k

Hyderabad

Question: Citywide Internal Communication Network

Problem Statement:

Uber is designing a citywide internal communication network between its operational hubs such as driver support centers, regional dispatch hubs, and surge-control nodes. Every hub must be able to communicate with every other hub, either directly or indirectly.

The city is modeled as a complete network of Uber hubs. However, some connections already require paid infrastructure upgrades, while others can be connected at no additional cost.

You are given an undirected complete graph with g_nodes Uber hubs. The cost of connecting any two hubs is either 1 or 0.

There are exactly g_edges connections listed that require an upgrade with cost equal to 1. These connections are provided using two arrays, g_from and g_to, where each pair represents an undirected connection between two hubs that costs 1. All other possible connections between hubs have a cost of 0.

Given the list of upgrade-required connections, determine the minimum total upgrade cost required to connect all Uber hubs.

Example:

Consider the number of Uber hubs to be g_nodes = 4 and the number of upgrade-required connections g_edges = ... (Example data continues based on specific test cases).

Function Description:

Complete the findMinimumCost function. It has the following parameters:

• int gNodes: The total number of Uber hubs.

• List<Integer> gFrom: An array representing one end of the connections that cost 1.

• List<Integer> gTo: An array representing the other end of the connections that cost 1.

Returns:

• int: The minimum total upgrade cost required to connect all Uber hubs.

6 hours ago

admin 1.9k

Hyderabad

Problem1-: Citywide Internal Communication Network Solution

Topics Involved / Prerequisites

• Graph Theory (0-1 Minimum Spanning Tree)
• Breadth-First Search (BFS)
• Complement Graph Traversal

Overview

• To minimize the total upgrade cost, we must maximize the use of the free connections by finding the connected components of the zero-cost complement graph.
• Any nodes that cannot be reached using only free connections must be bridged using the required paid upgrades, acting as bridges between these free clusters.
• By counting the number of isolated zero-cost clusters and subtracting one, we mathematically determine the absolute minimum number of paid upgrades needed.

Approach

1. The Complement Graph Traversal

Instead of building a massive complete graph (which would cause memory limits to exceed), we store the explicitly given weight-1 edges in an array of Hash Sets for fast lookups. We then maintain an unvisited set containing all the nodes from 1 to N. We use a Breadth-First Search (BFS) to explore all the free (weight-0) connections.

2. Finding the Free Components

For every unvisited node, we increment our component counter and start a BFS. During the BFS, we iterate through the remaining unvisited nodes. If an unvisited node does not share a weight-1 edge with our current node, it implies a free weight-0 edge exists! We immediately remove it from the unvisited set and add it to our BFS queue. The final upgrade cost is simply the total number of free components minus 1.

Code Implementation

#include <iostream>
#include <vector>
#include <unordered_set>
#include <queue>

using namespace std;

int findMinimumCost(int gNodes, vector<int>& gFrom, vector<int>& gTo) {
    // Step 1: Build adjacency sets for the weight-1 edges for O(1) lookups
    vector<unordered_set<int>> adj(gNodes + 1);
    for (size_t i = 0; i < gFrom.size(); i++) {
        adj[gFrom[i]].insert(gTo[i]);
        adj[gTo[i]].insert(gFrom[i]);
    }

    // Keep track of all nodes we haven't placed into a 0-cost component yet
    unordered_set<int> unvisited;
    for (int i = 1; i <= gNodes; i++) {
        unvisited.insert(i);
    }

    int components = 0;

    // Step 2: Find all connected components in the complement (0-cost) graph
    for (int i = 1; i <= gNodes; i++) {
        if (unvisited.count(i)) {
            components++;
            unvisited.erase(i);
            
            queue<int> q;
            q.push(i);

            while (!q.empty()) {
                int curr = q.front();
                q.pop();

                vector<int> toRemove;
                
                // Check remaining unvisited nodes for 0-cost connections
                for (int node : unvisited) {
                    // If no 1-cost edge exists, it must be a 0-cost edge
                    if (adj[curr].find(node) == adj[curr].end()) {
                        toRemove.push_back(node);
                    }
                }

                // Remove discovered nodes from unvisited and push to the BFS queue
                for (int node : toRemove) {
                    unvisited.erase(node);
                    q.push(node);
                }
            }
        }
    }

    // The minimum cost to connect 'C' components is 'C - 1' edges
    return components - 1;
}

Time Complexity

• Time: O(N + E) - We visit each node and edge a limited number of times. By continually shrinking the unvisited set, we bypass the heavy O(N^2) traversal normally required for dense graphs.
• Space: O(N + E) - To store the adjacency sets for the weight-1 edges and the unvisited nodes.