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.

Discover more from Jobs Addaa

Subscribe to get the latest posts sent to your email.

Discover more from Jobs Addaa

Subscribe now to keep reading and get access to the full archive.

Continue reading