Conversion Ratios
Calculate Conversion Ratios. Given a list of conversion pairs between different units of measurement, write an algorithm that returns the conversion ratio from one unit to another, either directly or through a series of conversions. If no conversion is possible, the algorithm should return None.
For instance, if you have the following conversions: ("USD", "EUR", 0.88), ("EUR", "JPY", 129.53), and ("GBP", "USD", 1.39), the algorithm should be able to deduce the conversion rate from "USD" to "JPY" as well as from "GBP" to "EUR".
Examples:
conversions = [ ('USD', 'EUR', 0.88), ('EUR', 'JPY', 129.53), ('GBP', 'USD', 1.39) ] source = 'USD' destination = 'JPY' output: 114.0064 # 0.88 * 129.53 source = 'GBP' destination = 'EUR' output: 1.2232 # 1.39 / 0.88 source = 'EUR' destination = 'GBP' output: None # No direct or indirect conversion available
from collections import defaultdict, deque
def construct_graph(ratios):
graph = defaultdict(dict)
for source, destination, ratio in ratios:
graph[source][destination] = ratio
graph[destination][source] = 1/float(ratio)
return graph
def calculate_ratio(source, destination, graph):
if source not in graph or destination not in graph:
return None
queue = deque()
queue.append((source, 1))
visited = set()
while queue:
node, curr_product = queue.popleft()
if node == destination:
return curr_product
visited.add(node) # Add node to the visited set to avoid revisiting
for intermediate_node, ratio in graph[node].items(): # Use items() for Python 3
if intermediate_node not in visited:
queue.append((intermediate_node, ratio * curr_product))
return NoneWatch Michael, a software engineer at Google, answer the question "Given a list of conversion items between different symbols, write an algorithm that returns the conversion ratio value for each pair of symbols."
public Double calculateRatio(String source, String destination) { Double ratio=1.0; while(graph.containsKey(source) && !visited.contains(source)) { visited.add(source); Map<String, Double> valueMap=graph.get(source); if(valueMap.containsKey(destination)) { return ratio*=valueMap.get(destination); } Map.Entry<String, Double> firstEntry=valueMap.entrySet().iterator().next(); source=firstEntry.getKey(); ratio*=firstEntry.getValue(); System.out.println("Entered"); } return null; }