Snowflake Software Engineer Interview Experience — A Trie Backtracking Bug I Never Fixed

First round: the interviewer — I really feel bad, she kept trying to help me the whole time, but in the end I still didn't get the bug fixed within the hour.

The input is a string array: [California, California/San Francisco, California/San Francisco/7th Street], etc. The other input is an array of the nodes to delete, e.g. [California/San Francisco], and the return should be [California]. LeetCode has this exact problem, but I forgot the number. You're supposed to solve it with a Trie, but in the end I got the backtracking wrong \TAT/ — I debugged it for a long time and still couldn't fix it.

Second round: the interviewer seemed pretty cold, and gave a problem that wasn't easy at all. But he wasn't deliberately ignoring me or anything like that — if I wrote something wrong partway through, he'd point it out right away.

Warm-up: binary tree — given a list of node IDs to delete, after deleting them, move each deleted node's children up to be children of its parent, then compute how many levels the tree has after all the deletions.

Main course: given a binary tree, a number n of nodes you're allowed to delete, and a target tree height k, return a list of every combination of nodes you could delete to reach that target height.