Katkat
Back

Solve power jumps and graph tour

MicrosoftSoftware Engineer · Technical Screen
HardSoftware EngineerTechnical ScreenCoding & Algorithms

Last updated

This problem tests your ability to optimize minimal operations using bitwise properties and to determine the existence of a specific graph traversal path.

Part 1: Minimal Power Jumps

Given an integer n (1 <= n <= 10^9), find the minimum number of operations to reach n starting from 0. In each operation, you can either:

  1. Add 1 to your current value.
  2. Multiply your current value by 2.

Example 1

Input: n = 10 Output: 4 Explanation: 0 -> 1 -> 2 -> 5 -> 10 (or 0 -> 1 -> 2 -> 4 -> 5 -> 10, but 4 steps is minimal).

Part 2: Hamiltonian Path Existence

You are given an undirected graph with V vertices and E edges. Determine if the graph contains a Hamiltonian path (a path that visits every vertex exactly once).

Function Signature

def can_complete_tour(n: int, edges: list[list[int]]) -> bool:

Constraints

  • n (vertices) 1 -> 2 visits all vertices.

Example 3

Input: n = 4, edges = [[0, 1], [1, 2], [2, 0]] Output: False Explanation: No path visits all 4 vertices (vertex 3 is isolated).

Hints

Hint 1

For the power jumps, working backwards from n to 0 is often more intuitive: if n is even, divide by 2; if n is odd, subtract 1.

Hint 2

For the Hamiltonian path problem, since n is small (<= 20), consider using dynamic programming with bitmasking to track visited nodes.

Hint 3

The state for the DP should be `dp(mask, current_vertex)`, where `mask` represents the set of visited vertices.

Follow-up questions

  • How would the power jump logic change if you were allowed to subtract 1 as well?
  • What is the time complexity of the Hamiltonian path solution using bitmask DP?
  • If the graph were directed and weighted, how would you find the shortest Hamiltonian path (the Traveling Salesperson Problem)?