I have applied for Mobile Applications role in Google Japan through a connection in Linkedin. Firstly I had a short discussion with the recruiter. Then, a phone interview was scheduled a week later.

Question 1 :
Interviewer asked me to implement contains function of Binary Search Tree.
I have provided him with solution using recursion. Then he asked me if I can implement it in array format. I did a level order search using queue, completely forgot the fact that it was BST. Then he asked me if I can optimize it, then I realised it was BST. Modified the changes accordingly.

Question2 :
What is big O time complexity?
I answered it in lay man's terms (Was nervous a bit :p).

Question 3:
There are n cities, cities are connected with flights routes. There are certain cities which are banned, we cannot travel throught the banned city. Start city and Destination are given

1. we need to find the shortest Path if it exists between Start and Destination, otherwise return -1.
2. Return the shortestPath.
3. Give the shortest distance by visiting the minimum number of banned cities.
4. What is the time complexity of the solution

Initially the question was asked and if answer was given, interviewer added the follow-up questions.

I have provided a solution using BFS(with queue) and visited[n] array to mark visited nodes, with timecomplexity O(N^2) and space complexity O(N) where N is the cities.

Waiting for the result, I don't know if I make through it. Little nervous definitely.

[Update] : I got past the phone interview :D