I recently had a problem to solve at work where I had two lists: a master list, and a smaller list that contains a subset of the items in the master list potentially in a different order. I needed to reorder the master list in such a way that the items in the subset would appear in the same order without changing the order of the items not found in the list and keeping items in the same location whenever possible. Okay, that probably sounds confusing, so I'll break it down:
- The master list defines the default order of items.
- The subset list defines relative order of certain items.
- Where the master list has two elements out of order according to the subset list, the item that is earlier in the master list should be moved to the earliest index where it is in the correct location relative to other items within the subset list. (i.e. immediately after the later item)
Your task is to implement this reordering algorithm.
Example Test Cases
Master: [1, 2, 3] Subset:  Result: [1, 2, 3]
Master: [9001, 42, 69, 1337, 420] Subset:  Result: [9001, 42, 69, 1337, 420]
Master: [9001, 42, 69, 1337, 420, 99, 255] Subset: [69, 9001, 1337] Result: [42, 69, 9001, 1337, 420, 99, 255]
Master: [1, 2, 3, 4, 5] Subset: [2, 5] Result: [1, 2, 3, 4, 5]
Master: [apple, banana, carrot, duck, elephant] Subset: [duck, apple] Result: [banana, carrot, duck, apple, elephant]
Master: [Alice, Betty, Carol, Debbie, Elaine, Felicia, Georgia, Helen, Ilene, Julia] Subset: [Betty, Felicia, Carol, Julia] Result: [Alice, Betty, Debbie, Elaine, Felicia, Carol, Georgia, Helen, Ilene, Julia]
Master: [snake, lizard, frog, werewolf, vulture, dog, human] Subset: [snake, werewolf, lizard, human, dog] Result: [snake, frog, werewolf, lizard, vulture, human, dog]
Master: [Pete, Rob, Jeff, Stan, Chris, Doug, Reggie, Paul, Alex] Subset: [Jeff, Stan, Pete, Paul] Result: [Rob, Jeff, Stan, Pete, Chris, Doug, Reggie, Paul, Alex]
Master: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12] Subset: [8, 1, 2, 12, 11, 10] Result: [3, 4, 5, 6, 7, 8, 1, 2, 9, 12, 11, 10]
Master: [lol, rofl, lmao, roflmao, lqtm, smh, jk, wat] Subset: [wat, lmao, rofl] Result: [lol, roflmao, lqtm, smh, jk, wat, lmao, rofl]
- Standard loopholes, yadda yadda, convenient I/O, blah blah.
- Even though the examples use numbers and strings, you only need to support one element type, whether that's integers, strings, or anything else with well-defined equality semantics, including heterogeneous lists if that's convenient in your language.
- You may assume both the master list and the subset list contain no duplicates
- You may assume that all items found in the subset list are found in the master list
- Either list may be empty
- You must, at minimum, support arrays up to 100 elements long.
- Reordering may be implemented in-place or through the creation of a new list/array.