Permutations, Graph Traversal, and Tick-Tak-Toe

Tech screening was a task to generate all possible permutations given a set of rules. Main coding challenge: graph traversal problem (DFS or BFS is enough). System design: Design an online game of a Tick-Tak-Toe.

Implement the permutation portion as generate_permutations(items, rules). items is a list of unique strings, and rules[item] lists permitted next items. A permutation must use every item exactly once, follow each selected directed edge, and end at an item with no permitted next items. Return results in DFS traversal order. Missing rule keys mean the item is terminal.

Constraints

1 <= len(items) <= 10
items contains unique strings
Every rule target is an item in items
rules may omit terminal items
Return permutations in DFS traversal order

Function Signature

def generate_permutations(items, rules):

Your question is Permutations, Graph Traversal, and Tick-Tak-Toe. 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

Constraints

1 <= len(items) <= 10
items contains unique strings
Every rule target is an item in items
rules may omit terminal items
Return permutations in DFS traversal order

Function Signature

def generate_permutations(items, rules):

Your question is Permutations, Graph Traversal, and Tick-Tak-Toe. 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.