Hi all,
Just want to share my google interview experience hope it helps someone

Screening by recruiter:-

Recruiters also do a minor screening process for me they asked the following questions

1. What is complexity of Merge sort (Best , average and worst)
2. When would you use BFS to determine the shortest path ? (Unweighted graph)
3. Calculate 2^22 ( 2^10 approx 1000 so 1000 * 1000 * 4)

Elimination round

Given a binary tree find the length of the longest Arithmetic progression from top to bottom.

                                     20
                        16                       18    
                  2          12               16      16
            -1          14     8           1                14
                                 7                        12
                               6                            10                   
                            5
                          4
                      3
                    2
                 1 
			  -1

For this tree from top to bottom we have multiple APs

20->18->16->14->12->10
20->18->16
20->16->12->8 Edge Case Node is shared
8->7->6->5->4->3->2->1 Edge Case Node is shared
........
(There are many :P APs of shorter length ! )

Among all the APs 8->7->6->5->4->3->2->1 this sequence has the longest length so our answer is 8

Solution :- I was able to solve it using BFS

Follow up:- How would the code change if the question is changed to horizontal for example

				  9
			3           4
		5      6      7   8	
		

For this find the longest length from 5 -->3 ---> (9,6,7)---> 4--->7 which becomes an n-arry tree

		              5
					  3
				9	  6     7
				      4
					  7
		

I got call from my recruiter that I'm eligible for Onsite interview. I took 3 weeks to prepare for my onsite

Round1 :-

Given a set of words find the longest sequence of words where each previous word is the prefix of the next word and the next word has just one new character (Let me give an example )

[a,ab,abc,abcd,abcdef,abcdefg,abcdefgh,abcdefghi]

Two sequences

1. a--> ab-->abc-->abcd
2. abcdef--->abcdefg--->abcdefgh--->abcdefghi--->abcdefghij

I had to return the the second sequence .

Similar question:-
Thanks @smpavlenko for bringing this to my notice
https://leetcode.com/problems/longest-string-chain/

Solution :- I solved it using Trie and DFS .

Result:- Although I solved it but I missed one edge case which was a red flag and also my code quality and efficiency was poor. They also said I was a little slow

Round 2:-

Given a processor it should pick up a job from set of available jobs and execute the job which has the least running time duration . Jobs are given in the format

[jobId, jobStartTime, durationOfThejob]

Job ID is always unique and there could be multiple jobs starting in the same time

i.e if I've jobs

[1,3,2],[2,3,8],[3,4,1]

answer should be [1,3,2] the sequence of the jobId

Solution :-

I solved it using PriorityQueue and a timer . (I solved this question in 15 mins :P )

Followup:-
What if there were 2 processors how would your code change ?

I used a variable timer to track duration. I just added 2 more timers and made some slight modifications

Similar question :-
The closest question I came across in leetcode for this question was
(1353. Maximum Number of Events That Can Be Attended)

Please feel free to comment if there's a exact match of this question

Result:- Overall result of this round of positive my code quality was improved, speed also improved

Round 3:-

Exactly this question (947. Most Stones Removed with Same Row or Column) . I didn't see this question before the interview although I was able to explain the logic to the interviewer in 5-10 mins but I got stuck in one portion while coding

Result:- -ve couldn't complete the code on time .

I got a call from my recruiter the next day that they've decided not to go ahead with me :'(

I'm gonna try again after sometime

PS:- Please forgive me for my bad english .

I notice I got some downvotes as well . Can you please help me understand why you downvoted the post so that I can improve it ?