Question

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

Answer 1

We were given with 4 Questions. 2 of them are mentioned below.
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

 

Question: 2
There is a grid of (10^18, 10^18) blocks. The person standing on (i, j) block can move to (2i, j) or (i, 2j) or (i-j, j) or(i, j-i) inside the grid. If he starts from (1, 1) output "Yes" if he/ she could reach (m, n) block else output "No"

 

Input:
t: No of m, n values
List of 2 m, n values

 

Output:
t Yes or No

 

Ex:
Input:
3
1 2
4 7
10 10

Output: 
Yes
Yes
No

Answer 2

#include<iostream>

#include<bits/stdc++.h>

using namespace std;

int solve(vector<vector<int>>grid,int i,int j,int r,int c,int coins,vector<vector<vector<int>>>&dp)

{

    if(coins<0 || i>r ||j>c ||i<0 ||j<0)

    {

        return 100000;

    }

 

    if(i==r and j==c)

    {

        return 0;

    }

    if(dp[i][j][coins]!=-1)

    {

        return dp[i][j][coins];

    }

 

    int right=1+solve(grid,i,j+1,r,c,coins-grid[i][j],dp);

    int down=1+solve(grid,i+1,j,r,c,coins-grid[i][j],dp);

 

    return dp[i][j][coins]=min(right,down);

}

int main()

{

    vector<vector<int>>grid{

{0, 0 ,1},

{1, 0 ,1},

{1 ,0, 1},

{0 ,1, 0},

{0, 0 ,0}

};

int r=4,c=2;

int coins=1;

vector<vector<vector<int>>>dp(grid.size()+1,vector<vector<int>>(grid[0].size()+1,vector<int>(coins+1,-1)));

cout<<solve(grid,0,0,r,c,coins,dp);//it it returs a bigger value it meanns no path exist

}

Answer 3

Solution to the first problem is dynamic programming on graph. Convert grid to graph and mix it up with dijkstra : dp[i][j][k] = Min moves to reach (i,j) if you are allowed to use max k coins..