1
$\begingroup$

I was once asked a question, given a series of units and their ratios, such as inch, cm, gram vs pound, and a lot of potentially cryptic units and ratios, such as A, B, C, D, ... if I am given n times to do the add() to the table, and m time to do lookup() to get the conversion, such as from "mile" to "inch" and to "cm" and to "meter" if that was the originally given ratio pairs, then what is the time complexity? (Big O). (I think this is the question -- can't remember every single detail. Probably not temperature F conversion to C, because 0°F is not 0°C, while all other conversions are like 0 inch = 0 cm, meaning they can be converted by multiplying by a k factor).

Does this problem actually belong to Union-Find, and therefore can be solved by Weighted Quick Union as described by Sedgewick? Or does it belong to any other areas in CS?

$\endgroup$
1
$\begingroup$

In a union-find data structure, each item is either a root or points at a parent. For us, units will be items, and each pointer to a parent will be annotated with the appropriate conversion. You can maintain this annotation while running the usual operations on the union-find data structure.

Using this annotation union-find data structure, you can implement each add() using union and each lookup() using find, with only a constant factor overhead.

$\endgroup$
  • $\begingroup$ so is it union-find? I was given the problem saying that there can be millions or billions of conversions (maybe they are not units but some kind of ratio relationship) Or maybe we can think of it as billions of stars in the universe and the ratio of mass between two stars $\endgroup$ – nopole Aug 27 at 14:18
  • $\begingroup$ What union-find will give you is whether you can convert between two units. $\endgroup$ – Yuval Filmus Aug 27 at 14:20
  • $\begingroup$ it can be a modified version of union-find. I think the person asking is mostly interested whether I can come up with a $O((m+n) \log (m+n))$ type of algorithm vs a $O(m^2+n^2)$ one $\endgroup$ – nopole Aug 27 at 14:31
  • $\begingroup$ Union-find allows you to convert your graph into an equivalent one which is very shallow. Each query should take time proportional to your union-find's lookup. $\endgroup$ – Yuval Filmus Aug 27 at 14:33

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.