Tree Question in Interview

Oct 2, 2019 14 Comments

Can any one shed light on how to solve this tree question? I was asked during my Facebook phone interview. Given a tree, the algorithm should print node values in a certain order.

______________________ A
_______________ /________________\
________ B__________________________ C
_____/_______\_____________________/______\
__D__________(null)___________E___________F

It should print
ABD
ACE
ACF

I came up with a solution to do that and went through each line of my code with the above input node values and verified that the code produces the desired output.

After that, the interview added one more node as shown below, and said the output should be as shown below. The thing I had a difficulty with was the K value on its own on the last line while the other lines all start with root node value A. I struggled for trying to come up with an algorithm that would leave only K on the 4th iteration(pass) about several minutes and I ran out of time.

______________________ A
_______________ /________________\
________ B____________________________C
_____/_______\_____________________/_______\
___D__________(null)_____________E_____________F
_/_____\______________________/_____\__________/_____\
(null)__(null)_______________(null)___(null)__(null)_______K

should print
ABD
ACE
ACF
K

comments

Want to comment? LOG IN or SIGN UP
TOP 14 Comments
  • Apple
    fu2

    Go to company page Apple

    PRE
    Amazon
    fu2
    So obviously depth first traversal...and you’d need to ask more questions. Output could be wrapping after 3 characters? At least that’s what it looks like to me. Since the final traversal would be ACFK
    Oct 2, 2019 3
    • Apple
      fu2

      Go to company page Apple

      PRE
      Amazon
      fu2
      Depth first for each full route. If you see, the leaves are printed in depth first order.

      So imagine that each time you hit a leaf node, you print the entire route so far, wrapping at 3 characters. Meaning something like

      temp_route = route
      while temp_route.length > 3:
      ....print(temp_route[:3])
      ....temp_route = temp_route[3:]
      Oct 2, 2019
    • Infosys / Eng
      BRY47

      Go to company page Infosys Eng

      BRY47
      Yea I didn’t see the condition was added as an extra after the first solution. I think you’re right about it wrapping after 3.
      Oct 2, 2019
  • Disney
    VaderD

    Go to company page Disney

    VaderD
    This is the iterative version of dfs traversal, basically iterate upto 3 levels and start next levels as new root nodes
    Oct 2, 2019 4
  • F5 Networks / Eng
    h689qbQ75

    Go to company page F5 Networks Eng

    h689qbQ75
    I'm confused why should it be K and not ACFK?
    Oct 2, 2019 1
    • Infosys / Eng
      BRY47

      Go to company page Infosys Eng

      BRY47
      It seems like it was an additional constraint added after op coded the solution where he would get ACFK as the output.
      Oct 2, 2019
  • HID Global / Other
    AtomBox

    Go to company page HID Global Other

    AtomBox
    I had the exact same problem asked last week without the k. It was easy solution. Write a depth first tree trivarsal function, with a string being appended on every node visited and add an extra if condition to only print the string if the node is leaf.
    I guess since it was easy they made little harder with the K.
    Oct 2, 2019 0
  • Microsoft / R&D
    RajaDKing!

    Go to company page Microsoft R&D

    PRE
    Microsoft
    RajaDKing!
    Can you please post the right tree output. It's impossible to understand what the question is asking
    Oct 2, 2019 0