Had a phone screen with Google. After formal introduction, the interview started:
The initital problem was that given an original word e.g. “Hello” and an expressive word “Heeeellooo”, return the starting and ending index of repeating charcters which are not present in original string. For example, “e” is being repeated three times and “o” is being repeated two times so you have to return [[“e”, 2, 4], [“o”, 8, 9]]
A = [1, 0 , 0, 7, 1, 2, 2, 2, 3 ,7]
Start at index 0.
You may travel to indx i - 1, index i + 1 or any index j where A[i] == A[j]
The goal is return the min step to reach the last elemt
The expected output is 3
[0, 4, 3, 9]->3
Given a string and a dictionary, output a sentence by adding spaces to the string. If there were multiple valid sentences I only needed to output one of them.
e.g. "theskyisblue" -> "the sky is blue" and "theseapplesaregood" -> "these apples are good"
When I first saw the questions I intially thought DP and thought that I was screwed because I am pretty bad at DP but the interviewer was very helpful and walked me through a different approach.
My initial approach was using greedy with 2 pointers. Basically just getting the first string that was in the dict and then saving it in a string builder. Interviewer asked me to improve my solution since it wouldn’t work for the second example since it would give the sea applesaregood which would be incorrect.
I then tried using DP and got stuck so my interviewer recommend I go back to the 2 pointer approach which I did.
The approach used 2 pointers and a Stack . I would add all valid words and increment the pointers respectively. If I got to the end and had a garabage string I would pop off the last string from the stack and reset my start and end position to be at the beginning and ending of the popped off string. I did this using the following class
static class Word {
int start;
int end;
String word;
Word(int start, int end, String word) {
this.start = start;
this.end = end;
this.word = word;
}
}
and creating a Stack<Word> .
The interviewer seemed happy about this approach and asked me about runtime. I said O(n^2) worst case and best case O(n) which he also agreed with.
Wasn’t a coding question but a code refactor question. The interviewer gave me some Java code and I needed to refactor variables and redundant logic. Changing variable names from things like s to input and adding null checks here and there. Overall pretty simple and the interviewer was really helpful.
The final question was create a binary tree given an inorder and preorder traversal. I’ve done this question before but I explicitly remember not reviewing it because I assumed they would never ask (just my luck). I ended up not being able to solve it but the interviewer said I was headed in the right direction at the end. This interviewer seemed much less engaged than the other two.
Overall I think I did okay, I felt very confident with my progress after the first two rounds but the third round was definitely much tougher.
A drop of water falls on the root node.
And water flows from each node to it’s children through edges with varying stickiness - means that it takes different amount of time for the water to go from a node to one of it’s child.
Question: How much time does it take for the entire tree to get wet?
Follow up 1: use a stack instead of recursion
Follow up 2: It is a Graph instead of tree
Follow up 3: design API :addNode, updateNode, deleteNode