Google Onsite 2020 pt3

// input: map of states to other states, and current state
// output: boolean if you need manual fix or not

/**

statesMap

{
	"STATE1": ["STATE3", "FIXED"],
	"STATE2": [],
	"STATE3": ["STATE2", "STATE4", STATE5"],
	"STATE4": "STATE3",
	"STATE5": ["FIXED"]
}


Example 1)
input: "STATE5"
output: true - because you can get it autofixed and it is the only outcome not others

Example 2)
input: "STATE1"
output: false
note STATE1 --> ["STATE3", "FIXED"] since not the only result and we need to guarantee we need to be able to autofix, this is false


Example 3)
input: "STATE4"
output: false
note there a loop from 4->3->4->3->etc., state3->2 will end up with [], and state5 is only one with fixed but still this doesn't guarantee

*/



public boolean canAutoFix(Map<String, List<String>> statesMap, String state) {
	// base case
	boolean resultBool = false;
	if (state.equals("FIXED")) return true;
	Set<String> visited = new HashSet<String>();
	Stack<String> dfs = new Stack<>();
	dfs.push(state);

	// iterative approach
	while (!dfs.isEmpty()) {
		String currState = dfs.pop();
		visited.add(currState); // mark as visited

		String[] nextStates = statesMap.get(currState);
		if (nextStates.length == 1 && nextStates[0].equals("FIXED")){
			resultBool = true;
			break;
		}
		for (String s : nextStates) {
			if (!visited.contains(s)) {
				dfs.push(s);
			} else {
				resultBool = false;
				break;
			}
		}
	}
	// by default nothing found then return false
	return resultBool;
}