Minimum Changes to Satisfy Rules | Dataford Interview Questions

Your question is Minimum Changes to Satisfy Rules. Start with the requirements on the right.

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

Problem

Google Cloud platform configurations contain boolean features with dependency rules. A rule [a, b] means that if feature a is enabled, feature b must also be enabled. Given an initial configuration, compute the minimum number of feature toggles needed to satisfy every rule.

You may enable or disable any feature. Each toggle changes one feature from 0 to 1 or from 1 to 0. Return only the minimum number of toggles, not the repaired configuration.

Formal Specification

Implement min_config_changes(initial, rules).

initial is a list of n integers, where initial[i] is either 0 or 1.
rules is a list of pairs [a, b], with zero-based feature indices. Each pair requires feature[a] = 1 to imply feature[b] = 1.
Return an integer representing the minimum number of toggles required.

A valid final configuration must satisfy every implication, including rules that participate in cycles.

Constraints

1 <= len(initial) <= 1000
0 <= len(rules) <= 10000
Each initial value is either 0 or 1
Each rule is a pair [a, b] of valid zero-based feature indices
Duplicate rules may appear

Function Signature

def min_config_changes(initial, rules):