I was recently in a coding interview where I had heard of the original problem (a version of "transform one word to another one letter at a time, making sure th

I was recently in a coding interview where I had heard of the original problem (a version of "transform one word to another one letter at a time, making sure that each step is a real word") so instead of just skipping the question, we went straight to the "extra credit" question of "can you tell that there is a path from one word to another faster than just calculating the answer?" After hearing the word "memoization" go through my head (part of "Hacking the Coding Interview." which I recommend at least for the wealth of example questions for practice), I basically walked my way through making a disjoint-set data structure using the words as keys and the set number as values. I'm prettyy sure that making that up on the spot is what got me the job.