Amazon Interview Question
SDE1sCountry: India
<?php
function min_cost($route, &$cache) {
if (isset($cache[$route])) return $cache[$route];
if (strlen($route) == 1) return 0;
$min_cost = null;
$bs = [];
$changed_route = 'C';
for ($i = 1; $i < strlen($route); $i++) {
$char = $route[$i];
switch ($char) {
case 'A': $changed_route = $changed_route . 'C'; break;
case 'B': $changed_route = $changed_route . 'A'; $bs[] = $i; break;
case 'C': $changed_route = $changed_route . 'B'; break;
}
}
foreach ($bs as $pos) {
$cost = $pos * $pos;
$rest_route = substr($changed_route, $pos);
$rest_cost = min_cost($rest_route, $cache);
if ($rest_cost !== false) {
$sum = $cost + $rest_cost;
if ($min_cost === null || $min_cost > $sum) {
$min_cost = $sum;
}
}
}
if ($min_cost === null) {
$cache[$route] = false;
return false;
}
$cache[$route] = $min_cost;
return $min_cost;
}
function find_min_cost($route) {
$cache = [];
return min_cost($route, $cache));
}
Make a weighted graph for each station for possible stations.
- Nitin January 29, 2014problem reduces to finding the shortest path on the graph