Applied on the Google Career site and got the call in 5-7 days.

Recruiter Call (15 Mins)

• What is motivation to work with Google?
• Would you be willing to relocate to EU if you get the offer.
• Some algorithimic and DS questions to identify If you are prepared enough to take the interviews.
• Discussed about the phone screening process and onsite location.
• Recruiter did not disclose the position I am being interviewed for (so that they can easily downlevel me :( ).

After a day, I got the schedule for the phone screening interviews.

Phone Interview I (45 Mins)

Interviewer introduced himself and discussed about the motivation to work with Google (weird since this was the coding round, couldn't understand why he was interested in the answer).

After that we moved to one warm up question.

Q1- Implement Level order traversal of the Binary Tree.
Follow up - How would you extend your solution for n-ary tree.
Another follow up - why did you use class instead of struct?

class TreeNode {
public:
	//Binary Tree
	TreeNode *left, *right;
	int val;
	//n-ary
	vector<TreeNode*> children;
};

void bfs(TreeNode *root) {
	if (root == nullptr) return ;
	queue<TreeNode*> q;
	q.push(root);
	while(q.size() > 0) {
		int N = q.size();
		while(N--) {
			TreeNode *cur = q.front();
			q.pop();
			cout << cur->val << " ";
			//for Binary Tree
			if (cur->left) q.push(cur->left);
			if (cur->right) q.push(cur->right);
			//for n-ary tree
			for (auto child: cur->children) {
				if (child != nullptr)	q.push(child);
			}
		}
		cout << endl;
	}
}

Q2- Given the array of integers, find the number of pairs which satisfy the below expression
A[i] - A[j] = j - i, such that j > i

int solve (vector<int>&arr) {
	int n = arr.size();
	unordered_map<int, int> m;
	int ans = 0;
	for (int i = n - 1; i >= 0; --i) {
		int lookUpValue = arr[i] + i;
		ans += m[lookUpValue];
		++m[lookUpValue];
	}
	return ans;
}

We finished all the questions while 3-4 mins were left, so discussed about his role & responsibilities etc.

Phone Interview II (45 Mins)

He joined the call after 4-5 mins, so we already lost a couple of mins and he directly jumpde into the coding question after discussing the expectation from the interview.

Q Given a matrix of size mxn where each cell of the matrix represents height of that cell and two citiies c1(p, q), c2(x, y).

We can place a water source on any of the cell in the matrix, we need to find a cell, If we place the water source on that cell then water would reach both the cities.

Condition how water can flow from one cell to another cell within the matrix -

• If we put the water source at (x, y) then water can flow to only 4 neighbouring cells if and only if height of the current (x, y) cell is greater than or equal to the adjacent cell (x + 1, y), (x - 1, y), (x, y + 1), (x, y - 1).

I wrote two DFSs, one to mark the nodes and another one to search the node. He asked me refactor the in such a way, where we can use the one function only to achieve the purpose. Changed the code and he seemed satisfied.

Best of luck !