Jobs Addaa Jobs Addaa India's no-1 platform for Engineering Fresher Jobs updates.

Cognizant GenC Next Coding Questions 2025 – Set 1

Jobs Addaa , ,
Cognizant GenC Next Coding Questions – Intermediate to Hard Level

Cognizant GenC Next Coding Questions – Previously Asked (Intermediate to Hard Level)

Below are intermediate to hard-level coding questions inspired by previous Cognizant GenC Next exams, designed to test problem-solving and conceptual understanding. Solutions are provided in C++ and Python with detailed explanations.

Question 1: Find the Number of Islands

Given a 2D boolean matrix where 1 represents land and 0 represents water, count the number of islands. An island is formed by connected 1s (horizontally or vertically, not diagonally). Assume the matrix is surrounded by water.

Input: 
[
  [1, 1, 0, 0],
  [0, 1, 0, 1],
  [1, 0, 1, 1],
  [0, 0, 0, 0]
]
Output: 3

Solution in C++

#include 
using namespace std;

void dfs(vector>& grid, int i, int j, int rows, int cols) {
    if (i < 0 || i >= rows || j < 0 || j >= cols || grid[i][j] != 1) return;
    grid[i][j] = 0; // Mark as visited
    dfs(grid, i+1, j, rows, cols); // Down
    dfs(grid, i-1, j, rows, cols); // Up
    dfs(grid, i, j+1, rows, cols); // Right
    dfs(grid, i, j-1, rows, cols); // Left
}

int countIslands(vector>& grid) {
    if (grid.empty()) return 0;
    int rows = grid.size(), cols = grid[0].size(), islands = 0;
    for (int i = 0; i < rows; i++) {
        for (int j = 0; j < cols; j++) {
            if (grid[i][j] == 1) {
                islands++;
                dfs(grid, i, j, rows, cols);
            }
        }
    }
    return islands;
}

int main() {
    vector> grid = {{1, 1, 0, 0}, {0, 1, 0, 1}, {1, 0, 1, 1}, {0, 0, 0, 0}};
    cout << countIslands(grid) << endl;
    return 0;
}

Solution in Python

def dfs(grid, i, j, rows, cols):
    if i < 0 or i >= rows or j < 0 or j >= cols or grid[i][j] != 1:
        return
    grid[i][j] = 0 # Mark as visited
    dfs(grid, i+1, j, rows, cols) # Down
    dfs(grid, i-1, j, rows, cols) # Up
    dfs(grid, i, j+1, rows, cols) # Right
    dfs(grid, i, j-1, rows, cols) # Left

def count_islands(grid):
    if not grid:
        return 0
    rows, cols, islands = len(grid), len(grid[0]), 0
    for i in range(rows):
        for j in range(cols):
            if grid[i][j] == 1:
                islands += 1
                dfs(grid, i, j, rows, cols)
    return islands

grid = [[1, 1, 0, 0], [0, 1, 0, 1], [1, 0, 1, 1], [0, 0, 0, 0]]
print(count_islands(grid))

Explanation

Approach: Use Depth-First Search (DFS) to explore connected 1s. When a 1 is found, increment the island count and use DFS to mark all connected 1s as visited (change to 0). Repeat for each unvisited 1. Time Complexity: O(rows * cols), Space Complexity: O(rows * cols) due to recursion stack.

Understanding Tested: Recursion, graph traversal, and matrix manipulation.

Question 2: Minimum Path Sum in Triangle

Given a triangle array, find the minimum path sum from top to bottom. Each step, you can move to adjacent numbers on the row below.

Input: triangle = [[2],[3,4],[6,5,7],[4,1,8,3]]
Output: 11 (Path: 2 -> 3 -> 5 -> 1)

Solution in C++

#include 
using namespace std;

int minPathSum(vector>& triangle) {
    int n = triangle.size();
    vector dp(triangle[n-1].begin(), triangle[n-1].end());
    for (int i = n-2; i >= 0; i--) {
        for (int j = 0; j <= i; j++) {
            dp[j] = triangle[i][j] + min(dp[j], dp[j+1]);
        }
    }
    return dp[0];
}

int main() {
    vector> triangle = {{2}, {3, 4}, {6, 5, 7}, {4, 1, 8, 3}};
    cout << minPathSum(triangle) << endl;
    return 0;
}

Solution in Python

def min_path_sum(triangle):
    dp = triangle[-1][:] # Copy last row
    for i in range(len(triangle)-2, -1, -1):
        for j in range(i+1):
            dp[j] = triangle[i][j] + min(dp[j], dp[j+1])
    return dp[0]

triangle = [[2], [3, 4], [6, 5, 7], [4, 1, 8, 3]]
print(min_path_sum(triangle))

Explanation

Approach: Use dynamic programming bottom-up. Start with the last row, and for each number in the row above, add the minimum of the two possible paths below it. Continue up to the top. Time Complexity: O(n^2), Space Complexity: O(n) where n is the number of rows.

Understanding Tested: Dynamic programming, optimization, and array traversal.

Question 3: Longest Palindromic Substring

Given a string, find the longest palindromic substring.

Input: s = "babad"
Output: "bab" (or "aba")

Solution in C++

#include 
using namespace std;

string longestPalindrome(string s) {
    int n = s.size(), start = 0, maxLen = 1;
    vector> dp(n, vector(n, false));
    for (int i = 0; i < n; i++) dp[i][i] = true;
    for (int i = 0; i < n-1; i++) {
        if (s[i] == s[i+1]) {
            dp[i][i+1] = true;
            start = i;
            maxLen = 2;
        }
    }
    for (int len = 3; len <= n; len++) {
        for (int i = 0; i < n-len+1; i++) {
            int j = i + len - 1;
            if (s[i] == s[j] && dp[i+1][j-1]) {
                dp[i][j] = true;
                start = i;
                maxLen = len;
            }
        }
    }
    return s.substr(start, maxLen);
}

int main() {
    string s = "babad";
    cout << longestPalindrome(s) << endl;
    return 0;
}

Solution in Python

def longest_palindrome(s):
    n = len(s)
    dp = [[False] * n for _ in range(n)]
    start, max_len = 0, 1
    for i in range(n):
        dp[i][i] = True
    for i in range(n-1):
        if s[i] == s[i+1]:
            dp[i][i+1] = True
            start, max_len = i, 2
    for length in range(3, n+1):
        for i in range(n-length+1):
            j = i + length - 1
            if s[i] == s[j] and dp[i+1][j-1]:
                dp[i][j] = True
                start, max_len = i, length
    return s[start:start+max_len]

s = "babad"
print(longest_palindrome(s))

Explanation

Approach: Use dynamic programming to build a table where dp[i][j] is true if substring s[i:j+1] is a palindrome. Check single characters, pairs, and expand to longer lengths. Track the longest found. Time Complexity: O(n^2), Space Complexity: O(n^2).

Understanding Tested: String manipulation, DP, and palindrome properties.

Question 4: Maximum Sum Subarray with No Adjacent Elements

Given an array of positive integers, find the maximum sum of a subarray where no two elements are adjacent.

Input: arr = [5, 5, 10, 100, 10, 5]
Output: 110 (Path: 5 + 100 + 5)

Solution in C++

#include 
using namespace std;

int maxSumNoAdjacent(vector& arr) {
    if (arr.empty()) return 0;
    int incl = arr[0], excl = 0;
    for (int i = 1; i < arr.size(); i++) {
        int new_excl = max(incl, excl);
        incl = excl + arr[i];
        excl = new_excl;
    }
    return max(incl, excl);
}

int main() {
    vector arr = {5, 5, 10, 100, 10, 5};
    cout << maxSumNoAdjacent(arr) << endl;
    return 0;
}

Solution in Python

def max_sum_no_adjacent(arr):
    if not arr:
        return 0
    incl, excl = arr[0], 0
    for i in range(1, len(arr)):
        new_excl = max(incl, excl)
        incl = excl + arr[i]
        excl = new_excl
    return max(incl, excl)

arr = [5, 5, 10, 100, 10, 5]
print(max_sum_no_adjacent(arr))

Explanation

Approach: Use two variables: `incl` (max sum including current element) and `excl` (max sum excluding current element). For each element, update `incl` as `excl + current` and `excl` as the previous max. Time Complexity: O(n), Space Complexity: O(1).

Understanding Tested: Dynamic programming, greedy choice, and optimization.