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 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 Coding Question

Group GPUs by node and partition by links

Company: Microsoft

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: hard

Interview Round: Technical Screen

## 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.

Quick Answer: 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.

Part 1: Group GPUs by nodeId

You are given GPU records as `(gpuId, nodeId)` pairs and an undirected link list between GPUs. Group all GPUs so that every GPU with the same `nodeId` appears in the same group. Return a dictionary mapping each `nodeId` to the sorted list of GPU IDs that belong to it. The `links` list is included to match the cluster setting, but grouping is determined only by `nodeId`.

Constraints

0 <= len(gpus) <= 200000
Each `gpuId` is unique
`nodeId` values may repeat
0 <= len(links) <= 200000
Every GPU ID appearing in `links` is guaranteed to exist in `gpus`

Examples

Input: ([(1, 10), (2, 10), (3, 20), (4, 20), (5, 30)], [(1, 2), (2, 3), (4, 5)])

Expected Output: {10: [1, 2], 20: [3, 4], 30: [5]}

Explanation: GPUs are grouped only by `nodeId`, not by connectivity.

Input: ([(7, 2), (3, 1), (5, 2), (4, 1)], [(7, 5)])

Expected Output: {1: [3, 4], 2: [5, 7]}

Explanation: The input is unsorted, so each group's GPU IDs should be sorted before returning.

Input: ([(42, 99)], [])

Expected Output: {99: [42]}

Explanation: Single-GPU edge case.

Input: ([], [])

Expected Output: {}

Explanation: Empty input should return an empty dictionary.

Hints

A hash map keyed by `nodeId` is enough to collect GPU IDs for each machine.
Sort each group's GPU IDs before returning so the output is deterministic.

Part 2: Partition GPUs into exactly X groups to maximize internal links

You are given a set of unique GPU IDs, an undirected link list, and an integer `x`. Partition all GPUs into exactly `x` non-empty, disjoint groups so that the number of links whose two endpoints end up in the same group is maximized. Because this optimization problem is hard in general, this version limits the number of GPUs to at most 15 so an exact algorithm is possible. If multiple optimal partitions exist, sort each group in ascending order, then sort the list of groups lexicographically, and return the lexicographically smallest optimal partition.

Constraints

1 <= len(gpus) <= 15
1 <= x <= len(gpus)
0 <= len(links) <= n * (n - 1) / 2
Every GPU ID in `links` appears in `gpus`
Links are undirected; duplicate links and self-loops should be ignored

Examples

Input: ([1, 2, 3, 4, 5, 6], [(1, 2), (1, 3), (2, 3), (4, 5), (4, 6), (5, 6)], 2)

Expected Output: [[1, 2, 3], [4, 5, 6]]

Explanation: Each triangle should stay together, giving 3 + 3 = 6 internal links.

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

Expected Output: [[1], [2, 3, 4]]

Explanation: Several partitions achieve 2 internal links; the required tie-breaker picks the lexicographically smallest one.

Input: ([10, 20, 30], [], 2)

Expected Output: [[10], [20, 30]]

Explanation: With no links, every partition has score 0, so the lexicographically smallest valid partition is returned.

Input: ([7], [], 1)

Expected Output: [[7]]

Explanation: Single-GPU edge case.

Input: ([1, 2, 3], [(1, 2), (1, 3), (2, 3)], 3)

Expected Output: [[1], [2], [3]]

Explanation: Boundary case where `x = n`: every GPU must be alone.

Hints

Since `n` is small, think in terms of subsets represented by bitmasks.
To avoid counting the same partition in different orders, always force the smallest remaining GPU into the next group you build.

Quick Overview

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.