Topological Install Order | Dataford Interview Questions

Given a set of items to install and their dependencies, return a valid install order (Course Schedule II-style topological sort), detecting when no valid order exists.

Asked in the phone screen stage. This was an algorithmic phone screen for Senior FE.

Input and Output

Implement install_order(items, dependencies). items is a list of unique strings. Each dependency [item, prerequisite] means prerequisite must be installed before item. Return a list containing every item exactly once in a valid order, or [] if no valid order exists. Assume every dependency names items in items.

Constraints

0 <= len(items) <= 1000
Each item name is a unique string
Each dependency has the form [item, prerequisite]
Every dependency names items contained in items
The dependency list contains no duplicate pairs

Function Signature

def install_order(items, dependencies):

Your question is Topological Install Order. Start with the requirements in the Question tab.

Run and submit as often as you like. When you're ready, talk me through your approach or go straight to the code.

Problem