2 Questions: 40 Minutes

Q1: Write an iterator with two functions, that performs a pre-order traversal on a binary tree.

A

/ \

B C

/ / \

D F G

\ \

H I

The functions were next() and hasNext();

-next() returns the value of the next node

-hasNext() returns whether the tree still has nodes to be traversed

Since the hasNext function needs to return true if we havent traversed the whole tree, we cannot return false at H (in the example above)

My solution was to use a stack, that we push and pop from, at the beginning we push the head, then pop the head and push its left and right children. Once the stack's length === 0, we return false, otherwise we return true. next() is just a normal pre-order traversal. Got through this one with not too much trouble and managed to explain the time and space complexity as it is fairly straightforward

Q2.

q2 was

https://leetcode.com/problems/word-break/
Given a string: "bedbathandbeyond" return true if it contains all valid words in a dictionary

"bedbathandbeyond" -> ["bed","bath","and","beyond"] or ["bed","bat",hand","beyond"] = true

"fdsasdfas" = false as its not made up of any words

Initially i managed to explain that a brute force solution would require checking every possible substring against the dictionary, and that the runtime of it would be 2^N. After thinking of a better solution for a while I couldn't come up with anything, so my interviewer told me to go ahead and code the brute force solution and we would go from there. At this point I got a bit flusted and ran out of time coding my solution, so I don't think ill end up moving on to the next round unfortunately :/

UPDATE: moved forward to virtual onsite