Hi folks, I had my Google interview some days back and I got this question in the final Onsite round.

We're given a Grid which is initially empty. Now, we want to play a game on it by placing the character 'X'.
Each time, we can place an 'X' at one of the coordinates in the grid (i, j) and we need to return whether the game has ended or not.

The game is considered to be won when there exists an 'X' path from the first column of the grid to the last column.
We need to efficiently play this game now. 
For a path to be winning, we need to consider only the elements in the 4 directions from it...i.e. we can't take up the diagonal elements. 

Eg. 

  X  _  _  _ 
  _  X  X  X 
  _  X  X  _ 
  _  _  _  _ 
  _  X  _  _ 
  _  _  _  _ 

In the above grid, we can see that there is a diagonal path but diagonal paths aren't considered valid and the game isn't ended at that piont of time. In the above grid itself, if I now place a new 'X' at (0, 1) index, we'll have the below grid

  X  X  _  _ 
  _  X  X  X 
  _  X  X  _ 
  _  _  _  _ 
  _  X  _  _ 
  _  _  _  _ 

And now I can go from the left most colum to the right most column traversing only via X's.

I came up with a DSU based approach in which we can keep a column tracker for each representative node for a component. It wasn't the optimal solution but the interviewer asked me to code that approach in the interest of time.
The whole game was supposed to be made interactive in nature and I needed to give an "online" algorithm for it.

I ended up implementing DSU with both rank and path compression along with the column tracker logic but the TC in the wost case can go upto O(N) for the union operation where M is no. of rows and N is no. of cols.
So, the overall TC in the worst case can go upto O(M * N * N)

The space complexity for my solution was O(M * N). If there's any similar question here, I'd definitely like to take a look at it.

Edit:
I had two more onsites of Google recently and in one of them, I got this question -- https://leetcode.com/problems/shortest-path-in-a-grid-with-obstacles-elimination/
The interviewer had extended the directions from 4 to all 8 and asked to me code up the solution. I coded the optimal solution for this using BFS.

In another interview, I was given a bunch of intervals with timestamps and I needed to find out the first interval which exceeded a certain threshold length. I gave the most optimal solution using an unordered_map<int, list<pair<int, int>>:iterator> and list<pair<int, int>> combination and the interviewer was quite surprised.
Since we have some 10-15 minutes left, he simply asked me how a doubly linked list was implemented and asked me to code up the "insert" and "remove" operations on DLL given a certain pointer. I was able to do both of them in the given time.

I'm now waiting for the results for my onsites. Fingers crossed.

Edit: Here's exact third question which I wrote on another post -- https://leetcode.com/discuss/interview-question/2504930/Google-or-Onsite-or-Bengaluru-or-L4