Solve island connectivity and string multiplication
Company: Meta
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Technical Screen
##### Question
Given N distinct islands (e.g., a, b, c…) and a list of existing undirected paths between them, compute the minimum number of additional paths required so that all islands become connected. LeetCode 43. Multiply Strings – Given two non-negative integers represented as strings, return their product as a string. (Clarify whether the carry can exceed 10.)
https://leetcode.com/problems/multiply-strings/description/
Overview: This question evaluates graph connectivity reasoning (computing minimum edges to unify components) and string-based big-integer arithmetic (multiplying numbers represented as strings), testing competency in graph theory, component analysis, and numeric string manipulation.
You are given n islands labeled from 0 to n-1 and a list of existing undirected paths (connections) between them. Each connection is a pair [u, v] with 0 <= u, v < n and u != v. Determine the minimum number of additional paths needed to make all islands belong to a single connected component. You may add a path between any two distinct islands.
Constraints
- 1 <= n <= 200000
- 0 <= len(connections) <= 200000
- connections[i] = [u, v], where 0 <= u, v < n and u != v
- Islands are distinct and labeled 0 to n-1
- Multiple or duplicate connections may be present and should be treated as a single connection for connectivity
Hints
- The minimum number of additional paths required equals the number of connected components minus one.
- Use DFS/BFS or Union-Find (Disjoint Set Union) to count connected components efficiently.
- Be careful to handle duplicate connections without affecting the component count.