Unit Conversion I

Unit Conversion I

What is this problem about?

The Unit Conversion I interview question is a classic graph-based problem where you are given a set of relationships between units (e.g., "1 meter = 100 centimeters", "1 kilometer = 1000 meters"). Your goal is to answer queries that ask for the conversion factor between two given units (e.g., "How many centimeters are in 1 kilometer?"). If no path exists between the two units, you should indicate that the conversion is impossible.

Why is this asked in interviews?

Companies like Adobe use the Unit Conversion I coding problem to assess a candidate's ability to model real-world data as a graph. It tests your knowledge of traversal algorithms and how to maintain and propagate weights (conversion factors) through the graph. It also evaluates how you handle potential issues like floating-point precision and cycles (though cycles should be consistent in this case).

Algorithmic pattern used

The most effective Breadth-First Search, Graph, Depth-First Search interview pattern for this involves building an adjacency list where each node is a unit and each edge is a conversion factor. For a query from unitA to unitB, you perform a BFS or DFS starting at unitA. As you move through the graph, you multiply the current cumulative factor by the factor on each edge. If you reach unitB, the final product is your answer.

Example explanation

Given:

• 1 yard = 3 feet
• 1 foot = 12 inches Query: How many inches in 2 yards?

1. Start at yard. Current factor = 1.
2. Move to foot: factor = $1 * 3 = 3$.
3. Move to inch: factor = $3 * 12 = 36$.
4. Answer: $2 * 36 = 72$ inches.

Common mistakes candidates make

One frequent error is not handling the reverse conversion factor (e.g., if "1 m = 100 cm" is given, you must also know "1 cm = 0.01 m"). Another mistake is failing to handle the case where a unit in the query is not in the graph at all. Finally, using DFS without tracking visited nodes can lead to infinite loops if the graph is not a simple tree.

Interview preparation tip

When you see a "relationship" problem, think Graph. BFS is often preferred over DFS for finding the shortest path, but for unit conversion, any path will yield the same result. Practice building adjacency lists for weighted directed graphs, as this structure is common in many advanced interview problems.