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