Former Google engineer breaks down interview problems he uses to screen candidates. Lots of good coding, algorithms, and interview tips.

But then you just iterate to convert everything to meters since you only need to do this once it being inefficient isn't really a concern.

  1. Convert your list into a two way mapping storing twoWayMap[a][b] = c; twoWayMap[b][a] = 1/c so your list is easily worked with.
  2. Pick a unit(keyUnit = twoWayMap.keys.Any()), doesn't really matter which.
  3. Make a new dict storing your key unit 1:1 toKeyUnitMap[keyUnit] = 1
  4. Pull out everything that directly maps to your key unit: possibleDirectMap = twoWayMap.keys.Filter(key, value => toKeyUnitMap.hasKey(key))
  5. For each of these get rid of the entries in the two way map and add them to your direct map: foreach (possibleDirectMap as unitWithConversion : void) { foreach (twoWayMap[unitWithConversion] as unitWithoutConversion : nonDirectConversionFactor) { if (toKeyUnitMap.hasKey(unitWithoutConversion)) { // Skip any keys we've already got the ability to convert to continue; } toKeyUnitMap[unitWithoutConversion] = nonDirectConversionFactor * toKeyUnitMap[unitWithConversion]; } twoWayMap.deleteKey(unitWithConversion); }
  6. If twoWayMap isn't empty and actually added new units to toKeyUnitMap loop back to step 4 and repeat.

Since you only do this once you don't need to build anything complicated, you can flatten it with just a 2d dictionary for the existing conversions and a single 1d dict for the final factors.

/r/programming Thread Parent Link - medium.com