abc Interview Question for Software Engineers
 1of 1 vote
AnswersCross the street
 pbox February 18, 2017 in United States
ABC Company is involved in the logistics business.
The company has many outlets and stockyards in a city. The city is like an
N
×
M
N×M grid. We consider a single cell of the given grid to be a single block in the city. The stockyard is at the upperleft corner and the outlet is located in the lower right corner. Everyday, one of the employees has to travel from the upper left to the lower right corner for supplies. Each block in the city has a height, where the height of the block located at position (i,j) in the grid is equal to
A
[
i
]
[
j
]
A[i][j]. The company wants to change the heights of some of the blocks, so that the employee can enjoy a highspeed drive from the stockyard to the outlet. But this change comes at a certain cost.
Specifically, if they change a block height from x to y, then they must pay exactly

x
−
y

x−y dollars. Please help them find the minimum cost, such that by spending that specific amount, they can get a path from stockyard to the outlet with all blocks along the path having the same height.
In a single move, the employee can move from a block to any of its adjacent blocks. Note that during this journey, the employee is allowed to move in all four directions, fulfilling the condition that he never goes out of the grid at any point in time.
Input :
First line contains two positive integers N and M  number of rows and columns in the city. Then, N lines follow, each containing M integers, where the
j
t
h
jth integer on the
i
t
h
ith line denotes
A
[
i
]
[
j
]
A[i][j].
Output :
The first and only line of output should contain minimum cost.
Constraints :
1<= N, M <=100
1<= height of blocks <=100
Sample Input
5 5
1 1 1 1 1
9 9 9 9 1
1 3 3 3 1
1 9 9 9 9
1 1 1 1 1
Sample Output
6
Explanation
Optimal path taken by the employee will be : (1,1) > (1,2) > (1,3) > (1,4) > (1,5) > (2,5) > (3,5) > (3,4) > (3,3) > (3,2) > (3,1) > (4,1) > (5,1) > (5,2) > (5,3) > (5,4) > (5,5) The height of each block along this path can be changed to
1
1, at a total cost of
6
6. There is no way to get a cost less than this. Report Duplicate  Flag  PURGE
abc Software Engineer Coding
Interview Type: Written Test
Open Chat in New Window