Three interviews in the on-site round:

1. Consider a skyline with buildings of different heights. You are scanning them from left to right.
   a. Can you identify if there exist three buildings (not necessarily adjacent) with heights x, 2x and 4x (in that order).
   Example: x, y, 2x, z, 2y, 4x -> Yes, x, y, 4x, z, 2y, 2x -> No
   b. Can you count all such combinations?
   Example: x,2x,4x,2x,4x -> 3 (2 combinations possible for the second 4x). x,2x,2x,4x,8x -> 4 (2 for x,2x,4x and 2 for 2x,4x,8x)
   c. Can you generalise it to be a sequence of any length? Say 5 buildings of lengths x, 2x, 4x, 8x, 16x?

   Solved the first one using dictionaries. Realized that wouldn't work well for the next two parts. Discussed possible alternatives, tried using graphs but couldn't code solution in 35 minutes.

2. Given a sorted array of numbers A which has both negative and positive numbers. There exists an array such that B[i] = |m*A[i] + c|, where m and c could be any number, positive or negative. How do you sort B efficiently?

   I first started with different signs of m and c (+ve or -ve), soon realized it will be very complicated. Interviewer suggested try plotting it. Was able to solve it by finding the point -c/m in A using binary search, and then using two pointers to go in different directions in A. Interviewer was surprised I was able to solve it, and that my code also passed the edge cases he had.

   Because we had some time, he then asked me the approach to a grid path question: given a grid of size mXn, you are to travel from top-left to bottom-right, you can only move along adjacent elements in 4 directions. The cost for the route is the max(|A[i][j] - A[x][y]|) for all adjacent A[i][j] and A[x][y] in that path. Find minimum such cost for that path.
   Solved this using binary search and dfs.

3. Probability Question: You are an examiner in a class. The students in the first row (row-wise) can get caught passing notes between each other with probability of .9, second row with .45, third row with .225 and so on. Students of rows 1 and 2 (column-wise) can get caught while passing notes between each other with probability .50, rows 2 and 3 with .25 and so on. Given two students sitting in the class, what is the probability of them successfully passing notes between each other.

   Took me some time to get the problem, took a case of 1000 notes being passed, then realized have to multiply 1-p.

   Now say the first-row-wise probability is p1 and first column-wise probability is p2. Each student has a skill s associated with them, 0 <=s <= 1. For that student to receive the note, the probability changes to p*(1-s), i.e. a highly skilled student (s = 1) will never get caught, and a less skilled student (s=0), has the same probability as the row-wise/column-wise probability based on the case. Given two students sitting in the class, what is the probability of them successfully passing notes in such a case.

   Didn't have time to code. Explained that it could be done using Djikstra.

   I was kinda annoyed with the questions at this point and politely asked my interviewer if probability was ever used in his work. He said nah, it's to test my problem solving, his day-to-day work was to only look at Google sheets and to test if the algorithm ran correctly, and he wasn't rigorously coding in his daily job.

Overall, it was the most difficult interview that I have ever given as I had never seen similar questions. Though telling it to a couple of friends at Google, they said I got unlucky as I got a difficult set of interviewers.

Recruiter reached out after a month telling me the result and asked me to try again in a year or so.