Round - 1 : DSA

//Warm up question:
Given a grid of size (N x N), cells S and T, impassable cells with water,
find if an S->T path exists, assuming we can only move horizontally/vertically.
No coding required, only explain how you would solve this problem.

// Main Question:
A mouse is trying to get from its starting position S to a target T.
The problem is that there is a sleeping cat C on the grid.
The closer the mouse approaches the cat, the higher the chance of
the cat to wake up. So, the mouse wants to get to T, staying as far
away as possible from the cat C.

Formally, assume again a square grid of size (N x N), allowing only
horizontal and vertical moves, impassable cells with water,
and cells S, T, and C. We want to find a path from S to T
for which the minimal distance to C along the path is maximal.

Example
........
.....S.
.C**.**
........
.......
.......
....T...

Output - 4

Round - 2 : DSA
//First Question
Design a data structure that supports the following three operations.

1. a constructor that takes a parameter K
2. add(x) -- inserts the number x
3. get() -- returns the product of the last K elements inserted

ex:
K = 2
add(2)
add(3)
get() -> 6
add(4)
get() -> 12

Clarifications:
Q: What to return if less than K elements have been inseted? A: Return the product of all inserted elements.
Q: Can the result overflow / should we use a long? A: The result of get() will always fit in an integer.
Q: Values of K? A: K is a positive integer.
Q: Values of x? A: x can be any integer.

//Follow-up
What if K is given in the get() function instead of in the constructor?
My answer-
•storing all numbers in the array instead of removing from queue
•could compute the product of last K elements in get(K), but this increase the time complexity O(K)
•how could we improve time complexity, reusing the same ideas?

• store prefix products in an array -> O(1) time complexity
• do not make the product zero, record the last found 0

Round - 3 : DSA
An stone array is given.
A mouse is on index 0 initially, he starts jumping towards right.
Score of a jump is = (len of jump * value of stone mouse is jumping on to)
for eg : Score of jump from i to j, score would be = (j-i)*stone[j]

Mouse can make any number of jumps, find what is the maximum score that can be achieved.

ex
3 5 4 7 2 12 8 10 1

ex: 3 to 12 (512) + 12 to 10 (210) + 10 to 1 (1*1) = 81

Round - 4 : G&L

1. Tell me about yourself.
2. Tell me about a challenging project you worked on and how you handled.
3. Two feature of any google product you use you like most and what improvement you would want to do.
4. Time when you had conflicting situation and how did you handled it.
5. Time when you agreed with manager even though he was wrong.

Update
Round - 5 : Additional technical round
Write a function which, given an array of integers, returns the length of the longest subsequence where every next value is 1 bigger than the previous one.
Subsequence might not be consecutive, but must be in the same order as the given array.

Example:
Input: 2 1 3 2 4 3 2 5 4 5
^ ^ ^ ^ ^
Output: 5

Follow up - 1
You are given an integer D together with the array. You need to return the length of the longest subsequence where every next value is between 1 and D bigger than the previous one.

Follow up - 2
Instead of returning the length of the longest subsequence, you need to return the path of it, i.e. the indexes of the elements which forms the longest subsequence.

Pleasse upvote if it helps!!