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