How do I practice coding and algorithm questions?

Use PracHub's coding console to write, test, and debug your solutions in Python or JavaScript. View hints, test against sample inputs, and compare with official solutions.

What difficulty level is this coding question?

This is a medium difficulty Coding & Algorithms question, commonly asked during Onsite rounds at Bytedance.

What role is this question designed for?

This question is commonly asked for Data Engineer candidates at Bytedance during technical interviews.

Connect Points With Minimum Total Distance

Q: Connect Points With Minimum Total Distance

This question evaluates a candidate's competency in graph modeling, geometric distance metrics, and algorithmic complexity analysis for optimizing total connection cost among spatial points.

Company: Bytedance

Role: Data Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Onsite

You are given an array `points`, where `points[i] = [xi, yi]` represents a point on a 2D plane. The cost to connect two points `i` and `j` is their Manhattan distance: `|xi - xj| + |yi - yj|` You need to connect all points so that every point is reachable from every other point, directly or indirectly. Return the minimum possible total connection cost. ### Constraints - `1 <= points.length <= 1000` - `-1_000_000 <= xi, yi <= 1_000_000` - All points are distinct. ### Example ```text Input: points = [[0,0],[2,2],[3,10],[5,2],[7,0]] Output: 20 ``` ### Follow-up Explain which graph algorithm you would use and analyze its time and space complexity.

Quick Answer: This question evaluates a candidate's competency in graph modeling, geometric distance metrics, and algorithmic complexity analysis for optimizing total connection cost among spatial points.

You are given an array `points`, where `points[i] = [xi, yi]` represents a distinct point on a 2D plane. The cost to connect two points `i` and `j` is their Manhattan distance: `|xi - xj| + |yi - yj|`. Connect all points so that every point is reachable from every other point, directly or indirectly, and return the minimum possible total connection cost. As a follow-up, be ready to explain which graph algorithm you would use and analyze its time and space complexity.

Constraints

1 <= len(points) <= 1000
-1_000_000 <= xi, yi <= 1_000_000
All points are distinct
Use 64-bit integer types in fixed-width languages, since the total cost can exceed 32-bit integer range

Examples

Input: ([[0,0],[2,2],[3,10],[5,2],[7,0]],)

Expected Output: 20

Explanation: One optimal set of connections has costs 4, 3, 4, and 9, for a total of 20.

Input: ([[3,4]],)

Expected Output: 0

Explanation: A single point is already fully connected, so no cost is needed.

Input: ([[0,0],[1,1],[1,0],[-1,1]],)

Expected Output: 4

Explanation: An optimal way is to connect [0,0] to [1,0] (1), [1,0] to [1,1] (1), and [0,0] to [-1,1] (2), totaling 4.

Input: ([[-1000000,-1000000],[1000000,1000000],[1000000,-1000000]],)

Expected Output: 4000000

Explanation: Connect [-1000000,-1000000] to [1000000,-1000000] for 2000000, then [1000000,-1000000] to [1000000,1000000] for 2000000.

Hints

This is a minimum spanning tree problem: each point is a node, and the edge weight between two nodes is their Manhattan distance.
Because the graph is complete, you can avoid explicitly storing all edges and instead keep track of the cheapest way to connect each unvisited point.

Quick Overview

This question evaluates a candidate's competency in graph modeling, geometric distance metrics, and algorithmic complexity analysis for optimizing total connection cost among spatial points.