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.

Solve power jumps and graph tour | Microsoft Coding Question

Quick Overview

This pair of problems evaluates algorithmic problem-solving in number representation and combinatorial graph optimization, focusing on competencies in bitwise/number reasoning for minimal operations and graph traversal/route optimization for a Hamiltonian tour.

Loading coding console...

Part 2: Shortest Round Trip Visiting All Nodes

You are given a directed weighted graph with nodes numbered from 0 to n - 1, a list of edges, and a starting node s. Find the minimum total distance of a tour that starts at s, visits every node exactly once, and returns to s. If no such tour exists, return -1. This is a shortest Hamiltonian cycle problem with a fixed starting node.

Constraints

1 <= n <= 15
0 <= s < n
0 <= u, v < n
1 <= w <= 10^9
The graph is directed and may be incomplete
There may be multiple edges between the same ordered pair of nodes

Examples

Input: (1, [], 0)

Expected Output: 0

Explanation: With only one node, the tour starts and ends at the same node without traveling.

Input: (4, [(0, 1, 10), (0, 2, 15), (0, 3, 20), (1, 0, 10), (1, 2, 35), (1, 3, 25), (2, 0, 15), (2, 1, 35), (2, 3, 30), (3, 0, 20), (3, 1, 25), (3, 2, 30)], 0)

Expected Output: 80

Explanation: One optimal tour is 0 -> 1 -> 3 -> 2 -> 0 with total cost 10 + 25 + 30 + 15 = 80.

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

Expected Output: -1

Explanation: There is no way to visit every node exactly once and return to 0.

Input: (4, [(2, 0, 4), (0, 1, 6), (1, 3, 5), (3, 2, 3), (2, 1, 10), (1, 0, 2), (0, 3, 8), (3, 0, 7)], 2)

Expected Output: 18

Explanation: The best tour is 2 -> 0 -> 1 -> 3 -> 2 with cost 4 + 6 + 5 + 3 = 18.

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

Expected Output: 9

Explanation: Use the cheaper duplicate edge 0 -> 1 with weight 2. Then 0 -> 1 -> 2 -> 0 costs 2 + 4 + 3 = 9.

Hints

A normal shortest-path algorithm is not enough because you must visit every node exactly once. Think of Traveling Salesman Problem style DP.
Use a bitmask to represent which nodes have been visited, and store the best cost for each possible last node.

Quick Overview