How do I approach Coding & Algorithms interview questions?

Coding & Algorithms questions require understanding of core concepts and practice. PracHub provides solutions with explanations to help you master coding & algorithms interviews.

What difficulty level is this interview question?

This is a hard difficulty Coding & Algorithms question, commonly asked during Technical Screen rounds at Microsoft.

What role is this question designed for?

This question is commonly asked for Software Engineer candidates at Microsoft during technical interviews.

Group GPUs by node and partition by links | Microsoft Interview Question

Q: Group GPUs by node and partition by links

This question evaluates understanding of graph algorithms and combinatorial optimization, specifically skills in graph traversal, grouping by node attributes, and partitioning to maximize intra-group edges.

Problem: GPU graph grouping and link-maximizing partition

You are given a cluster of GPUs represented as a graph:

Each GPU has a unique gpuId and belongs to a physical machine identified by nodeId .
GPUs can be connected by bidirectional links (edges). A link (u, v) indicates GPU u and v have a direct high-speed connection.
The graph may be disconnected.

Part 1 — Group GPUs by `nodeId`

Return a grouping of GPUs such that all GPUs belonging to the same nodeId appear in the same output group.

Input (one possible representation)

gpus : list of GPU objects, each with fields {gpuId, nodeId}
links : list of undirected edges (gpuId1, gpuId2)

Output

A mapping (or list of groups) where each group contains all gpuId s with the same nodeId .

Notes

Assume you may need to traverse via the link graph to discover all GPUs if the input is not presented as a fully materialized list.

Part 2 (Follow-up) — Partition into exactly `X` groups to maximize internal links

Now ignore nodeId for grouping, and instead partition all GPUs into exactly X disjoint groups.

Goal: maximize the total number of links whose endpoints fall within the same group (i.e., maximize intra-group edges).

Output

A partition assignment group[gpuId] in {1..X} (or X lists of gpuId s).

Clarifications/constraints to discuss

Are groups required to be balanced in size? (If not specified, assume no.)
Expected approach: explain an algorithmic strategy and its trade-offs (exact vs heuristic/approximation), and analyze time complexity.

Problem: GPU graph grouping and link-maximizing partition

You are given a cluster of GPUs represented as a graph:

Each GPU has a unique gpuId and belongs to a physical machine identified by nodeId .

GPUs can be connected by bidirectional links (edges). A link (u, v) indicates GPU u and v have a direct high-speed connection.

The graph may be disconnected.

Part 1 — Group GPUs by nodeId

Return a grouping of GPUs such that all GPUs belonging to the same nodeId appear in the same output group.

Input (one possible representation)

gpus : list of GPU objects, each with fields {gpuId, nodeId}

links : list of undirected edges (gpuId1, gpuId2)

Output

A mapping (or list of groups) where each group contains all gpuId s with the same nodeId .

Notes

Assume you may need to traverse via the link graph to discover all GPUs if the input is not presented as a fully materialized list.

Part 2 (Follow-up) — Partition into exactly X groups to maximize internal links

Now ignore nodeId for grouping, and instead partition all GPUs into exactly X disjoint groups.

Goal: maximize the total number of links whose endpoints fall within the same group (i.e., maximize intra-group edges).

Output

A partition assignment group[gpuId] in {1..X} (or X lists of gpuId s).

Clarifications/constraints to discuss

Are groups required to be balanced in size? (If not specified, assume no.)

Expected approach: explain an algorithmic strategy and its trade-offs (exact vs heuristic/approximation), and analyze time complexity.

Group GPUs by node and partition by links

Quick Overview

Problem: GPU graph grouping and link-maximizing partition

Part 1 — Group GPUs by `nodeId`

Part 2 (Follow-up) — Partition into exactly `X` groups to maximize internal links

Comments (0)

Group GPUs by node and partition by links

Quick Overview

Problem: GPU graph grouping and link-maximizing partition

Part 1 — Group GPUs by `nodeId`

Part 2 (Follow-up) — Partition into exactly `X` groups to maximize internal links

Comments (0)

Group GPUs by node and partition by links

Quick Overview