Super disappointing and depressing. I was also mocked by roommate (PM, not an engineer, doesn't know algo or coding) that it's taking too long for me. It's LC medium, but I think it's considered easy/warmup in actual interviews. I'm doing top down DFS recursively, searching for a, b and helper returns if a is found or b is found. The first time both are true, I set a mutable variable (python list) to node.val. The problem is for all other nodes above they're both true too and it always returns root. There's a problem in my recursion logic. Recursion is hard.
Hey man, I feel your pain. It is hard to understand recursion if you try to generalize for all cases. Try solving for trivial cases first (for one node, 2 nodes etc) and then see how your code behaves. What if root is already a or b? If it is not, what about left children of root? What about right children? Try to break down the problem first and try really hard to visualize the recursion stack. Trust me, you will get better.
BFS? This should be post order traversal.
The common ancestor is the node for which a search on its children, left and right, combined, return the two sought after nodes. Then you solve the edge case, when the two nodes are in the same path.
Typo, I meant DFS. Mistake was that I did preorder traversal
Recursion can be tricky if you haven’t done it in awhile. Walk over a short example and draw it out at each step.
Ok don’t feel bad. You just need to know about different strategies like DFS. And lmao at your PM roommate mocking you. Why does he say anything if he doesn’t know how to code.
it's ok as you are learning. I wouldn't recommend spending on a problem 3-4 hours. In real interview you will be given about 15-30 minutes to solve a medium problem. For this one I think expectation will be around 10-15 minutes. So if 20 minutes have passed and you still have no clue about correct algorithm, just mark it as failed interview, learn a solution(pattern) and move on.
don’t try to remember the solution but the thinking process.
I find this problem to be easier to solve iteratively. Simply do a dfs and build a map from child to parent. Now you just need to find the intersection of two lists.
I go straight to the discussion board if I can’t figure out a problem within like 10-20 minutes. Feels like cheating but dramatically speeds up learning in the long run.
I've done that. Has not helped me personally in retaining. I forget after a few weeks and can't solve a similar problem or sometimes the same problem quickly. I think looking at solutions is helpful when it's tricky, but what I'm getting stuck as is fundemental.
I agree with the suggestion that looking at the discussion board as soon as I spend more than 20mins on a question. What helps with retention is redoing the question a couple of times with cooldown in-between.