Subsequences and Gold Diggers

A common question you might face during a coding interview is to validate a subsequence. Chances are you’ll have two arrays (possibly more) and you will need to make sure that the numbers in the smallest array will appear in the same order (even if they aren’t adjacent) in the larger array. For example [1,3,5,8] is a valid subsequence of [0,1,2,3,4,5,6,7,8].

While this definition is straight forward enough, comparing numbers in different arrays is pretty darn boring. To make things more exciting consider the hard nosed Gold Digger that always judges books by their covers…

So, a Gold Digger” might have a Wish List of traits for their prospective target spouse in order of ‘importance’. For example:

goldDiggerWishList = ["hot", "rich", "kind", "looking for marriage","going to die soon","elderly","not totally icky","smells nice", "owns a yacht", "won't require a prenup", "likes puppies", "has a jet"]

But they’ll also have a Real List, ALSO in order of importance…

goldDiggerMusts = ["rich","looking for marriage", "going to die soon", "won't require a prenup"]

Now, imagine that Gold Digger thinking of their “Musts List” ONLY in the order they wrote it. For example… they’re at a “tupperware party for life insurance” and eyeing all the potential prospects as they walk up from the parking lot.

Instead of “Wish List” mind set (that’s reserved for online dating), Gold Digger is going through “Observable List”.

Hark!! A “prospect” gasping and heaving from the short walk up the lawn, sweating and greasy, red in the face, about to have a heart attack…

goldDiggerObserves = ["fancy car in the parking lot", "going to die soon"]

They will summon up their list of MUSTS to compare with what they’ve observed thus so far, skipping over ‘rich’ and ‘looking for marriage’ and straight on to ‘going to die soon’. Sadly, because of their hard nosed ways, the gold digger will never get to observe the more tender traits on their must list.

The actual algorithm to solve this might be a while loop where the “observable” or “wish” list is compared to the “list of musts”. Note: any trait on the subsequence that doesn’t match the order it appears on the main list will not register on their brain.

Alternately, one might imagine a For Loop that will ‘break’ if the Wish/Observable List, and the Must List fall out of sync.

Lastly, one might throw away any value on the Wish/Observable List that does not match one on the Must List. The final result would be two lists with the same values. If the lists differed in any way, even if only in the order they’re presented… the Gold Digger would (sadly) miss out on an opportunity for romance.