Round 1
Questions:
-
There is an input string contains only english letters, no spaces. And there is an array of words. The task is to check if it is possible to create and return output string from the input by adding spaces between the words in the array. If not possible return an empty string.
- Example: input = "cathat", array = [rat, cat, hat] => "cat hat".
Candidate's Approach
- I solved the first problem with top-down dynamic programming. I noted that Facebook often asks about dynamic programming and questioned if it could be solved without it.
- For the second problem, I used a heap. I was prepared to mention quickselect in case of a follow-up, but there wasn't one. I initially overcomplicated the solution by computing the square root of the distance, but during the dry run, I realized that calculating the square root in my head was unnecessary.
Interviewer's Feedback
No feedback provided.