Meta Phone screen | E5

Got two questions :

1. Random pick index : https://leetcode.com/discuss/interview-question/451431/facebook-onsite-generate-random-max-index . I gave the solution where we can look for all indexes of maxElement after finding it, store them in an array and then randomly pick up one of the indexes from that array. Coded it perfectly and gave correct time complexity and space comlexity. Interviewer asked how to optimise it. I told the optimisation that in the second pass we can use reservoir samling to update the chosen index. Didn't have time to implement it. But he said he gets the approach. F

2. Vertical order traversal of binary tree : https://leetcode.com/problems/binary-tree-vertical-order-traversal/description/ : Explained the bfs approach using map for storing the column as key and values in tree as value in vector . He seemed fine with the solution. Coded it perfectly. Gave time complexity as O(n) and space complexity as O(n) . He asked whether map would change the time complexity . I said that map insertion would take logN and hence corrected the time complexity to O(nlogn). 40 mins finished . After the interview, I looked through the editorial and it seems there's a O(n) approach where you can store max and min column value . F

I know you guys can't tell what the results would be , but do you think that was enough to go to onsites? Code didn't have any bugs and was perfect for both. Not sure if they look for O(n) solution for vertical order traversal. I could have implemented the reservoir samping it too 20 mins were over so he asked to move to next question.