Virtusa | Neural-Hack-2.0 | OA Coding Questions and Solutions | Set - 5 | 2022

Question

All past online assesments of Virtusa can be found using the tag "virtusa_oa" in the search bar.

Here is the link : https://www.desiqna.in/tag/virtusa_oa

Answer 1

 

// C++ program to solve Gold Mine problem
#include<bits/stdc++.h>
using namespace std;

const int MAX = 100;

// Returns maximum amount of gold that can be collected
// when journey started from first column and moves
// allowed are right, right-up and right-down
int getMaxGold(int gold[][MAX], int m, int n)
{
    // Create a table for storing intermediate results
    // and initialize all cells to 0. The first row of
    // goldMineTable gives the maximum gold that the miner
    // can collect when starts that row
    int goldTable[m][n];
    memset(goldTable, 0, sizeof(goldTable));

    for (int col=n-1; col>=0; col--)
    {
        for (int row=0; row<m; row++)
        {
            // Gold collected on going to the cell on the right(->)
            int right = (col==n-1)? 0: goldTable[row][col+1];

            // Gold collected on going to the cell to right up (/)
            int right_up = (row==0 || col==n-1)? 0:
                            goldTable[row-1][col+1];

            // Gold collected on going to the cell to right down (\)
            int right_down = (row==m-1 || col==n-1)? 0:
                            goldTable[row+1][col+1];

            // Max gold collected from taking either of the
            // above 3 paths
            goldTable[row][col] = gold[row][col] +
                            max(right, max(right_up, right_down));
                                                    
        }
    }

    // The max amount of gold collected will be the max
    // value in first column of all rows
    int res = goldTable[0][0];
    for (int i=1; i<m; i++)
        res = max(res, goldTable[i][0]);
    return res;
}

// Driver Code
int main()
{
    int gold[MAX][MAX] ; 
    int m , n ; 
    cin>>m>>n ; 
    int i = 0 ; 
    while(i<m)
    {
        int j = 0 ; 
        while(j<n)
        {
            cin>>gold[i][j] ; 
            j++;
        }
        i++;
    }
    cout << getMaxGold(gold, m, n);
    return 0;
}