This entry contains two independent coding problems. ## Problem 1: Uniformly connect node groups You are given `k` non-empty, disjoint groups of unique node IDs, for example: ```text groups = [[1], [2, 3], [4, 5, 6]] ``` Treat each group as an already-connected component. You may add an undirected edge only between two nodes that belong to different groups. To add such an edge, choose one node from one group and one node from another group. Implement a function that returns exactly `k - 1` edges such that all groups become connected. The result must be random, and every valid minimal connecting edge set should be sampled uniformly at random. Example valid outputs for the input above include: ```text [(1, 3), (2, 5)] [(1, 6), (3, 4)] ``` Each output contains `k - 1 = 2` edges and connects all three groups. Requirements: - Do not add edges within the same group. - Return a minimal connected structure, so the number of edges must be exactly `k - 1`. - The sampling distribution should be uniform over all valid minimal connecting edge sets. - Be prepared to explain why simple enumeration or a standard randomized minimum-spanning-tree-style approach may not produce a uniform random result. ## Problem 2: Find the best transportation mode on a grid You are given a 2D grid. Each cell contains one of the following values: ```text S = start D = destination X = obstacle 1 = Walk 2 = Bike 3 = Car 4 = Train ``` You are also given arrays `cost[1..4]` and `time[1..4]`, where `cost[m]` and `time[m]` are the per-step cost and per-step time for transportation mode `m`. You may move only up, down, left, or right. Diagonal movement is not allowed. Obstacles cannot be entered. ### Base version You must choose exactly one transportation mode and use that mode for the entire trip from `S` to `D`. For a chosen mode `m`, you may move through cells labeled `m`, plus the start and destination cells. Return the mode that reaches the destination with the smallest total travel time. If multiple modes have the same minimum time, return the one with the smallest total cost. ### Follow-up 1 Now allow switching between transportation modes during the route. Switching modes adds a given penalty. Compute the optimal route from `S` to `D` under the same objective: minimize total time, then minimize total cost. ### Follow-up 2 Add a maximum number of allowed mode switches. Compute the optimal route while respecting this switch limit.