I got two problems:
A variation of 589. N-ary Tree Preorder Traversal
I worked on two solutions based on recrusion and BFS based traversal. The interviewer asked for a constanct space solution but I was not able to come up with a constant space solution. I am still not sure if it is possible.
We can divide the list into chunks of size square root(len(list)).
Then we can create a temp array of the same size which will store the heads of each chunk of root(n).
Now, one by one, we can start printing the nodes in reverse order using a stack starting from the last chunk.
This means, that at any given time, we will only store root(n) nodes in our recursive stack.
TC -> O(n)
SC -> O(root(n))Next day, I got an automated rejection email from the recruiter. Not sure what the exact reasons of rejection are. Thanks!