KN Academy Prep

Capgemini Assessment Guide

Debugging (Alternating Parity Array) & AI Assist (Grid Shortest Path with K Removal)

Section 1: Parity Sequence Debugging

Question 1

Alternating Odd/Even Sequence Counter

Array Sequence Debugging

Requirements & Task –

Take N numbers as input, each processed array-wise.
Verify if elements follow the strict pattern: Odd → Even → Odd → Even...
Count and output the total number of elements in the valid sequence prefix.
Handle negative input values safely using modular arithmetic.

Bugs Identified & Fixes –

Bug 1 (Sequence Start): Expected parity was initialized to 0 (Even) instead of 1 (Odd).
Bug 2 (Negative Modulo): C++ expression -3 % 2 evaluates to -1. Fixed using abs(arr[i]) % 2.
Bug 3 (Sequence Termination): Break early immediately upon pattern breakdown to return correct valid sequence count.

Corrected C++ Solution –

#include <iostream>
#include <vector>
#include <cmath>
using namespace std;

int checkAlternatingSequence(int n, const vector<int>& arr) {
    if (n == 0) return 0;

    int expectedParity = 1; // Start with Odd (1)
    int count = 0;

    for (int i = 0; i < n; i++) {
        int currentParity = std::abs(arr[i]) % 2; // Safe negative modulo

        if (currentParity == expectedParity) {
            count++;
            expectedParity = 1 - expectedParity; // Toggle parity
        } else {
            break; // Pattern broken
        }
    }
    return count;
}

int main() {
    int n;
    if (cin >> n) {
        vector<int> arr(n);
        for (int i = 0; i < n; i++) cin >> arr[i];
        cout << checkAlternatingSequence(n, arr) << endl;
    }
    return 0;
}

Section 2: AI-Assisted Coding (Grid Shortest Path with K Removal)

Problem Context

Shortest Path in Grid with K Obstacle Removals

Given a 2D grid of size N × M (0 = empty, 1 = obstacle), start at (0,0) and reach (N-1, M-1) moving Up, Down, Left, or Right while removing at most K obstacles. Find the minimum steps required, or print -1 if impossible.

Sample Test Cases –

Grid Input (N x M) & K	Output	Explanation
N=5, M=3, K=1 [[0,0,0],[1,1,0],[0,0,0],[0,1,1],[0,0,0]]	6	Wraps around walls to reach end in 6 steps.
N=3, M=3, K=1 [[0,1,1],[1,1,1],[1,0,0]]	-1	Requires breaking 2 obstacles, but K=1. Impossible.

Step 1: Explain Approach

Core Strategy & In-Detail Approach Prompt

🤖 AI Assistant Prompt: “Can you explain your approach to solve this problem step-by-step?”

Candidate Response / Reference Prompt –

To find the shortest path in a grid from top-left to bottom-right with at most K obstacle removals:

1. Strategy: Explore paths level-by-level starting from (0,0) to guarantee finding the path with minimum steps first.
2. State Tracking: At every cell, track current position (row, col), current steps taken, and remaining obstacle quota (K).
3. Handling Obstacles: When moving to an adjacent cell (Up, Down, Left, Right):
   – If cell is 0 (empty), move to it and keep remaining K same.
   – If cell is 1 (obstacle), move to it only if remaining K > 0, and decrease remaining K by 1.
4. Avoid Redundant Visits: Only revisit a cell if we reach it with MORE remaining obstacle quota than before.
5. Termination: Return steps as soon as bottom-right cell is reached. Return -1 if all paths are exhausted.

Final Synthesis

Complete C++ Master Implementation

#include <iostream>
#include <vector>
#include <queue>

using namespace std;

struct State {
    int r, c, k, steps;
};

int shortestPath(vector<vector<int>>& grid, int k) {
    int n = grid.size();
    int m = grid[0].size();

    if (n == 1 && m == 1) return 0;
    if (k >= n + m - 2) return n + m - 2; // Manhattan Distance shortcut

    vector<vector<int>> visited(n, vector<int>(m, -1));
    queue<State> q;

    q.push({0, 0, k, 0});
    visited[0][0] = k;

    int dr[] = {-1, 1, 0, 0};
    int dc[] = {0, 0, -1, 1};

    while (!q.empty()) {
        State curr = q.front();
        q.pop();

        if (curr.r == n - 1 && curr.c == m - 1) return curr.steps;

        for (int i = 0; i < 4; ++i) {
            int nr = curr.r + dr[i];
            int nc = curr.c + dc[i];

            if (nr >= 0 && nr < n && nc >= 0 && nc < m) {
                int nextK = curr.k - grid[nr][nc];

                if (nextK >= 0 && visited[nr][nc] < nextK) {
                    visited[nr][nc] = nextK;
                    q.push({nr, nc, nextK, curr.steps + 1});
                }
            }
        }
    }
    return -1;
}

int main() {
    int n, m, k;
    if (!(cin >> n >> m >> k)) return 0;

    vector<vector<int>> grid(n, vector<int>(m));
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < m; ++j) {
            cin >> grid[i][j];
        }
    }

    cout << shortestPath(grid, k) << endl;
    return 0;
}