r1
Given a connections array, where connections[x] is a list representing the neighboring nodes of x in a graph, and a broken value representing a damaged node, return the minimum number of nodes that must be traversed from start to destination without passing through broken.
The solution could use DFS or BFS. I used DFS.
The follow-up allowed traversal through broken nodes.
r2
Implement a word predictor that can process training data and, for a given word, predict the next word. The prediction should be the next word with the highest frequency.
I used a dictionary and also maintained a cache. During processing, the cache updates the next word with the highest count, which guarantees that prediction is O(1).
Although I finished both problems, I still felt that I was probably out because I received hints. One interviewer was based in Poland, another was based in Brazil, and I am based in Europe. The r1 interviewer in Poland was quite friendly, but at the end he helped me correct one small point and then ended the interview before I had time to explain what I had gotten wrong. The r2 interviewer in Brazil was interviewing me at 7 a.m. his time. He did not talk much, but he kept following my reasoning. At first I said I wanted to add a cache, and he would not let me because he wanted me to update during process. He mistakenly thought I meant updating during predict. It may also have been because the name cache was a little confusing. I felt that the hint in r2 could have been avoided if our communication had gone more smoothly.
Oh well. Now that the interviews are over, I am letting them go. I will be going home for a vacation in another two weeks. Everything is up to fate now.
Discussion
Loading comments…