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.

Solve power jumps and graph tour

Company: Microsoft

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: hard

Interview Round: Technical Screen

This online assessment contained two coding problems: 1. **Minimum operations using signed powers of two** Given an integer `n`, you want to make it equal to `0`. In one operation, choose any integer `i >= 0` and either add or subtract `2^i` from the current value. Return the minimum number of operations needed. 2. **Shortest round trip visiting all nodes** Given a weighted graph 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`.

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

Part 1: Minimum Operations Using Signed Powers of Two

You are given an integer n. In one operation, you may choose any integer i >= 0 and either add 2^i to the current value or subtract 2^i from it. Return the minimum number of operations needed to make n equal to 0. You may use the same power of two multiple times if you want, but your goal is to minimize the total number of operations.

Constraints

-10^18 <= n <= 10^18
Each operation may add or subtract exactly one power of two
The answer should be computed efficiently in O(log |n|) time

Examples

Input: 0

Expected Output: 0

Explanation: It is already 0, so no operations are needed.

Input: 7

Expected Output: 2

Explanation: One optimal sequence is 7 + 1 = 8, then 8 - 8 = 0.

Input: 10

Expected Output: 2

Explanation: 10 - 2 = 8, then 8 - 8 = 0.

Input: 15

Expected Output: 2

Explanation: 15 + 1 = 16, then 16 - 16 = 0.

Input: -13

Expected Output: 3

Explanation: For example: -13 + 16 = 3, then 3 - 4 = -1, then -1 + 1 = 0.

Hints

Think in binary. If n is even, the lowest bit is already 0, so divide the problem by 2 conceptually.
When n is odd, decide whether adding 1 or subtracting 1 leads to a better future. Checking n % 4 is enough in most cases.

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