The recruitment process :

I was looking at the jobs at https://careers.google.com/jobs/. I made a resume and I applied for a software engineer junior position.
They reached out to me very promptly. I had the first HR interview where it wasn't actually an interview but more like an information session to present Google and the recruitment process at Google. The second interview was the same HR and it was a fairly easy question about the project that I worked on and what was I looking for at Google. After 3 weeks they reached out again to organize a technical phone screening in the coming week.

The phone interview was on a shared Google Doc (So prepare on writing code on Google Docs) and the interviewer was very helpful and gave me two hints.

I was so nervous and even though I solved the problem in the way the interviewer wanted me to apparently that wasn't enough

So my advice to you guys is to try not to be nervous and prepare, prepare, prepare. Finally good luck

The coding problem:

Given an array of integers, find the second max using only the function compare(a, b) that compares two integers and returns the maximum of the two. The solution must use the function compare(a, b) minimum number of times.

PS: You can assume that the array doesn't contain any duplicates and all the integers are positive

1st Edit: Adding Some Hints That was given to me by the interviewer and my solution

2nd Edit: Recruitment Process

4  7  2  0  1  3  5  6

compare adjacent:
(4  7)  (2  0)   (1  3)  (5  6)

Array after each iteration: 
(4  7)  (2  0)   (1  3)  (5  6)        4 compare()
    (7       2)      (3      6)          2 compare()
         (  7            6  )                1 compare()

4  7  2  0  1  3  5  6

compare adjacent:
(4  7)  (6  0)   (1  3)  (5  2)

Array after each iteration: 
(4  7)  (6  0)   (1  3)  (5  2)        4 compare()
    (7       6)      (3      2)          2 compare()
         (  7            2  )                1 compare()

Attention : A lot of people in the comments are making the same mistake I made, by making a normale time complexity analysis (which is not the case here). The question clearly is about the number of times you call the function compare.