Facebook Phone Interview (MLE)| June 2022
Anonymous User
206

I got two problems:

  1. 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.

    1. Print Immutable Linked List in Reverse
      I worked on three solutions based on stack, recursion and reversersing the original list. Then, the interviewer asked for a constant space solution and I was able to come up a solution using the total size and two nested loops (O(n^2)- time complexity).
      I found it can also be done in O(logn) space complexity:
      https://leetcode.com/discuss/interview-question/124617/Print-out-an-immutable-singly-linked-list-in-reverse/
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!

Comments (2)