I got following sum for my phone interview.
https://leetcode.com/discuss/interview-question/1367130/Doordash-Phone-Interview
I asked following clarifying questions
would the keys repeat?
what is the input?
would the input root node in the new tree or old tree be none?
I explained to the interviewer my strategy, we talked about it for some time.
I mentioned the time and space complexity. I was off in my space complexity. He corrected it and I jumped into coding.
I wrote my code talking all the time, explaining him what my code does. I finished coding and I ran all the tests. There was a single issue with my code, I corrected it. All the tests passed.
Then he asked me to find corner cases. He asked me to modify the given input examples. I came up with following corner cases:
1: both the nodes are null
2: one of the nodes are null
3: the root values are changed
I struggled to modify my code to pass the final scenario. At this moment he stopped me because the time was almost over and he started giving me feedback then and there. He was sympathetically negative. As in his tone was sympathetic but he was not impressed by the end result.
He said, the tests passed for sure but I did not cover all the corner cases. He said he will give a honest feedback to the rercuiter and that pass and fail is not in his hands. He was very polite and good guy but he was totally negative at the end.
Now I am not able to figure out what corner cases I missed.
I think one corner case which I missed is, should we maintain a visited set for the nodes.
for eg:
old_tree =
a
/ \
b c
/
e
new_tree
a
/ \
d c
/
b
/
e
in the above case, we will consider subtree starting with node d in the new tree as the diff so the count of nodes is 3
at the same time, b is not in the new_tree at that level so we will again calculate total nodes in the subtree starting with node b in the old tree - this count will be 2
so total count will be 3 + 2 = 5
however this is wrong, because only three nodes are changed, d,b and e. I think this is what he meant. Any thoughts?