Question

Phonepe | OA Coding Questions and Solutions | 2022 | Set-8

Answer 1

Question 1:
Aladdin positioned on (0, 0) wants to reach Jasmine at (r-1, c-1). He has k coins. We are given with a grid of cities where each city either charges 1 coin or 0 coins. Aladdin can move either horizontally or vertically one step in this grid to reach Jasmine. Find out the minimum steps taken to reach Jasmine.

 

Ex:
r = 5, c = 3, k = 1

0 0 1
1 0 1
1 0 1
0 1 0
0 0 0

Ans: 6

Answer 2

Q1 :

Python # Approach : Heap

import heapq
from typing import List

def solve(grid:List[List[int]], k:int)->int:
    rows, cols = len(grid), len(grid[0])
    directions = [[0,1],[0,-1],[1,0],[-1,0]]

    pq = ([(0,k,0,0)])      # steps,remainK,r,c

    while pq:
        steps,remK,r,c = heapq.heappop(pq)
        if r == rows-1 and c == cols-1 :
            return steps
        if remK < 0:
            continue
        for dr,dc in directions :
            newR,newC = r+dr, c+dc
            if newR<0 or newR>=rows or newC<0 or newC>=cols :
                continue
            heapq.heappush(pq,(steps+1,remK-grid[newR][newC],newR,newC))


print(solve([[0 ,0, 1], [1, 0, 1],[1, 0, 1],[0 ,1,0],[0, 0, 0]],1))