Google | Onsite Interview 3 questions
Anonymous User
4361

I interviewed with google last days - onsite, there has 3 questions.

1.)

Give you a 2-D matrix which you can started from (0, 0)
You can go up, left, right, down in 4-direction
return True if there has a strickly decreasing path can reach the (m-1, n-1). 
else return False
example1:
20, 100, 12,  11, 10
19, 100, 13, 100,  9
18, 100, 14, 100,  8
17, 16 , 15, 100,  7
return True
example2:
20, 100, 12,  11, 10
19, 100, 13, 100,  9
18, 100, 14, 100,  8
17, 100, 15, 100,  7
return False

2.)

Follow up from question1
If there did no has strickly decreasing path,
It also can go through by cost which if the difference between two integer
And return minimun cost.
example:
20, 100, 12,  11, 10
19, 100, 13, 100,  9
18, 100, 14, 100,  8
17, 100, 15, 100,  7
return 80
explain: 20 -> 100 -> 12 -> 11 -> 10 -> 9 -> 8 -> 7 (min cost is 100-20=80)

3.)

Give you a 2-D matrix
Define cost is difference between two neibor value
which is cost = | matrix[current_value] - matrix[nei_value] |
Find the minimun cost form (0, 0) to (m-1, n-1)
You can go up, left, right, down in 4-direction

example:
1, 1, 1, 1, 1
2, 1, 4, 5, 2
3, 2, 3, 8, 1
4, 3, 4, 0, 1
return 2
explain: 1 -> 1 -> 1 -> 1 -> 1 -> 2 -> 1 -> 1 (min cost is |1-2| + |2-1| = 2)

Can someone give me some solutions?

Comments (12)