Position: Software Engineer - Entry Level
Date: Feb 2020

I received an email from the recruiter asking me to select a date for a phone interview.
On the day of the interview, the interviewer called me, asked me a few questions about my current role. Then he shared the question with me on a shared HackerRank link. At the end of the interview, he offered to answer any questions I might have. I asked him a question about mentorship and training for engineers at Bloomberg.

Question:
An intelligence officer has intercepted a payload over-the-wire. Some of the engineers have been able to reconstruct it into it's original data structure (a binary tree). Each node in the tree represents a char. A credible source believes the message will reveal itself by printing the characters from left-to-right (ie. starting with the leftmost node and working your way over to the rightmost node). Write an algorithm that decrypts the message. (See input #1 for example)

Examples:

1.
        i
       / \
      r   y
     / \ 
    p   v

 result: privy

 2.
        a
       /
      i
     /
    c

 result: cia

 3. 
         c
          \
           i
            \
             a

 result: cia

 4.
         r
        / \
       e   t
          /
         e
        /
       c
      /
     s

 result: secret

 5.
         e
        / \
       s   r
        \
         c
          \
           e
            \
             t

 result: secret

I solved the question in O(NLogN) time. The interviewer hinted that the question could be solved with better time and space complexity. Immediately after the call ended, I realized how I could solve this question in O(N) time using a map (so with O(N) space), but I'm still not sure if this is the best answer. I'm curious to see answers shared by the community.

After 2 days, I received a rejection email from them. I asked for feedback but they said they can't share any specific feedback.

I think I communicated well and found a way to solve the question even though I was lost initially. However, I didn't have the most optimal answer, and perhaps there were candidates who solved this much faster and more optimally.

It was a great learning experience and I feel more confident about phone interviews since I know that if I learn to think aloud and ask the right questions off the interviewer, I can make progress and won't be stuck forever.