Cognizant GenC Elevate Coding Questions - Set 2

Cognizant GenC Elevate Coding Questions – Set 2 (Intermediate)

Previously asked Cognizant GenC Elevate Coding Questions – Set 2 (Intermediate)

These coding questions are crafted for Cognizant GenC Elevate preparation, reflecting the intermediate difficulty level observed in recent exams (2022-2024). Solutions are provided in C++ and Python with detailed explanations.

Question 1: Fibonacci Number (Recursive with Memoization)

Given a number n, find the nth Fibonacci number (0-based index) efficiently.

Input: n = 6
Output: 8 (Sequence: 0, 1, 1, 2, 3, 5, 8)

Solution in C++

#include 
using namespace std;

int fib(int n, vector& memo) {
    if (n <= 0) return 0;
    if (n == 1) return 1;
    if (memo[n] != -1) return memo[n];
    memo[n] = fib(n-1, memo) + fib(n-2, memo);
    return memo[n];
}

int fibonacci(int n) {
    vector memo(n + 1, -1);
    return fib(n, memo);
}

int main() {
    int n = 6;
    cout << fibonacci(n) << endl;
    return 0;
}

Solution in Python

def fibonacci(n, memo=None):
    if memo is None:
        memo = {}
    if n <= 0:
        return 0
    if n == 1:
        return 1
    if n in memo:
        return memo[n]
    memo[n] = fibonacci(n-1, memo) + fibonacci(n-2, memo)
    return memo[n]

n = 6
print(fibonacci(n))

Explanation

Approach: Use recursion with memoization to avoid redundant calculations. Store computed Fibonacci values in a memo array/dictionary. Time Complexity: O(n), Space Complexity: O(n).

Relevance: Recursion with optimization is a GenC Elevate topic.

Question 2: Longest Common Prefix

Given an array of strings, find the longest common prefix among them.

Input: arr = ["flower", "flow", "flight"]
Output: "fl"

Solution in C++

#include 
using namespace std;

string longestCommonPrefix(vector& arr) {
    if (arr.empty()) return "";
    string prefix = arr[0];
    for (int i = 1; i < arr.size(); i++) {
        while (arr[i].find(prefix) != 0) {
            prefix = prefix.substr(0, prefix.size() - 1);
            if (prefix.empty()) return "";
        }
    }
    return prefix;
}

int main() {
    vector arr = {"flower", "flow", "flight"};
    cout << longestCommonPrefix(arr) << endl;
    return 0;
}

Solution in Python

def longest_common_prefix(arr):
    if not arr:
        return ""
    prefix = arr[0]
    for s in arr[1:]:
        while s.find(prefix) != 0:
            prefix = prefix[:-1]
            if not prefix:
                return ""
    return prefix

arr = ["flower", "flow", "flight"]
print(longest_common_prefix(arr))

Explanation

Approach: Start with the first string as the prefix. For each subsequent string, shorten the prefix until it matches the start. Time Complexity: O(S) where S is the sum of all characters, Space Complexity: O(1).

Relevance: String prefix problems test pattern matching in GenC Elevate.

Question 3: Move Zeros to End

Given an array of integers, move all zeros to the end while maintaining the relative order of non-zero elements.

Input: arr = [0, 1, 0, 3, 12]
Output: [1, 3, 12, 0, 0]

Solution in C++

#include 
using namespace std;

void moveZeros(vector& arr) {
    int nonZeroPos = 0;
    for (int i = 0; i < arr.size(); i++) {
        if (arr[i] != 0) {
            arr[nonZeroPos++] = arr[i];
        }
    }
    while (nonZeroPos < arr.size()) {
        arr[nonZeroPos++] = 0;
    }
}

int main() {
    vector arr = {0, 1, 0, 3, 12};
    moveZeros(arr);
    for (int x : arr) cout << x << " ";
    cout << endl;
    return 0;
}

Solution in Python

def move_zeros(arr):
    non_zero_pos = 0
    for i in range(len(arr)):
        if arr[i] != 0:
            arr[non_zero_pos], arr[i] = arr[i], arr[non_zero_pos]
            non_zero_pos += 1

arr = [0, 1, 0, 3, 12]
move_zeros(arr)
print(arr)

Explanation

Approach: Move all non-zero elements to the front using a pointer, then fill the rest with zeros. Time Complexity: O(n), Space Complexity: O(1).

Relevance: In-place array manipulation is a GenC Elevate classic.

Question 4: Check if Array is Sorted and Rotated

Given an array, check if it is sorted (ascending) and rotated.

Input: arr = [3, 4, 5, 1, 2]
Output: true (Sorted: [1, 2, 3, 4, 5], rotated once)

Solution in C++

#include 
using namespace std;

bool isSortedRotated(vector& arr) {
    int n = arr.size(), drops = 0;
    for (int i = 0; i < n; i++) {
        if (arr[i] > arr[(i + 1) % n]) {
            drops++;
        }
        if (drops > 1) return false;
    }
    return drops == 1;
}

int main() {
    vector arr = {3, 4, 5, 1, 2};
    cout << (isSortedRotated(arr) ? "true" : "false") << endl;
    return 0;
}

Solution in Python

def is_sorted_rotated(arr):
    n = len(arr)
    drops = 0
    for i in range(n):
        if arr[i] > arr[(i + 1) % n]:
            drops += 1
        if drops > 1:
            return False
    return drops == 1

arr = [3, 4, 5, 1, 2]
print(is_sorted_rotated(arr))

Explanation

Approach: Count the number of "drops" where an element is greater than the next (considering wrap-around). A sorted and rotated array has exactly one drop. Time Complexity: O(n), Space Complexity: O(1).

Relevance: Array properties and cyclic checks are GenC Elevate-level challenges.

Ready to conquer GenC Elevate? Access more intermediate problems and prep strategies to shine in your exam!

Master Your Prep with Jobs Addaa Resources