I was told that there will be 3 coding rounds and 1 googlyness round.
Round1: A 2D matix with 0s and 1s is valid if the 1s do not touch each other from left, right or corners
ex
Valid
0 1 1 0 0
0 0 0 0 1
0 1 1 0 0
Invalid cases
0 1 1 0 0
0 0 0 1 1
0 0 0 0 0
0 1 1 0
0 1 1 0
0 0 0 0Round went well.
Round2: Given a 2D matrix with 0s and 1s, return true if it is possible to reach (N-1, N-1) from (0,0). Catch: you cannot move through 1s but you have 1 bullet that you can use to turn any 1 to 0 but only once.
Round went well, went from O(2nn) to O(nn) after he gave hints.
Round3: Given a horizontal line, you have to paint coordinates and tell the amount of paint required at every step.
Ex - [(4, 10), (7, 13), (20, 30)]
ans - [7, 3, 11]
Note that 4-10 was already painted in the first index so when (7,13) comes, you only paint from 11-13(inclusive).
I was able to explain the approach it is kinda like merging overlapping intervals but as soon as I told him that I will be using stack, he stopped me and told me to change the data structure. I told him we could use TreeMap but I didnt know the syntax so I went to linkedlist but it got too complicated and I was unable to code it.
Googlyness Round: Basic behavioural questions.
HR told me that you need to give another coding round
Round 5: https://leetcode.com/discuss/interview-question/763001/count-number-of-freshwater-lakes-in-2d-matrix
Note: there can be a lake inside lake
This was hard af. I told him that first we will mark the sea as -1 using dfs and then we will do a dfs on the 1s and if we see any 0, we will increase the count and do dfs on 0s, incase during dfs we meet any 1 that is not visited, we will put it in a list/stack and after dfs for 0 is done, we will pop elements from stack and run dfs to get lakes inside lake. Interviewer was not at all helpful and he told me to code it and I was not able to code it because I took too much time to come up with the approach.
Now waiting for results/rejections :P