Capgemini Interview Questions & Placement Prep (2026)

1. Second-largest distinct element (C++)

int secondLargest(vector<int>& a) {
    long first = LONG_MIN, second = LONG_MIN;
    for (int x : a) {
        if (x > first) { second = first; first = x; }
        else if (x > second && x != first) second = x;
    }
    return second == LONG_MIN ? -1 : second;
}

2. First non-repeating character (C++)

char firstNonRepeating(string s) {
    int freq[256] = {0};
    for (char c : s) freq[(unsigned char)c]++;
    for (char c : s) if (freq[(unsigned char)c] == 1) return c;
    return '\0';
}

3. Maximum subarray sum — Kadane's algorithm (C++)

long long maxSubArraySum(vector<int>& a) {
    long long current = a[0], best = a[0];
    for (size_t i = 1; i < a.size(); i++) {
        current = max((long long)a[i], current + a[i]);
        best = max(best, current);
    }
    return best;
}

4. Balanced brackets (C++)

bool isBalanced(string s) {
    stack<char> st;
    unordered_map<char, char> match = {{')','('}, {'}','{'}, {']','['}};
    for (char c : s) {
        if (c == '(' || c == '{' || c == '[') st.push(c);
        else if (match.count(c)) {
            if (st.empty() || st.top() != match[c]) return false;
            st.pop();
        }
    }
    return st.empty();
}

5. Count subarrays with sum K (C++)

long long countSubarraysWithSumK(vector<int>& a, long long k) {
    unordered_map<long long, int> freq;
    freq[0] = 1;
    long long sum = 0, answer = 0;
    for (int x : a) {
        sum += x;
        answer += freq[sum - k];
        freq[sum]++;
    }
    return answer;
}

6. Number of islands — BFS (C++)

int numIslands(vector<vector<char>>& grid) {
    int rows = grid.size(), cols = grid[0].size(), count = 0;
    vector<vector<bool>> visited(rows, vector<bool>(cols, false));
    int dx[] = {0,0,1,-1}, dy[] = {1,-1,0,0};
    for (int i = 0; i < rows; i++) {
        for (int j = 0; j < cols; j++) {
            if (grid[i][j] == '1' && !visited[i][j]) {
                count++;
                queue<pair<int,int>> q;
                q.push({i, j});
                visited[i][j] = true;
                while (!q.empty()) {
                    auto [r, c] = q.front(); q.pop();
                    for (int d = 0; d < 4; d++) {
                        int nr = r + dx[d], nc = c + dy[d];
                        if (nr >= 0 && nr < rows && nc >= 0 && nc < cols &&
                            grid[nr][nc] == '1' && !visited[nr][nc]) {
                            visited[nr][nc] = true;
                            q.push({nr, nc});
                        }
                    }
                }
            }
        }
    }
    return count;
}

7. Merge overlapping intervals (C++)

vector<vector<int>> mergeIntervals(vector<vector<int>>& intervals) {
    sort(intervals.begin(), intervals.end());
    vector<vector<int>> result;
    for (auto& iv : intervals) {
        if (!result.empty() && iv[0] <= result.back()[1]) {
            result.back()[1] = max(result.back()[1], iv[1]);
        } else {
            result.push_back(iv);
        }
    }
    return result;
}

8. Prime, GCD and Armstrong (C++)

bool isPrime(int n) {
    if (n < 2) return false;
    for (int i = 2; i * i <= n; i++) if (n % i == 0) return false;
    return true;
}

int gcd(int a, int b) {
    while (b) { int t = b; b = a % b; a = t; }
    return a;
}

bool isArmstrong(int n) {
    int original = n, sum = 0;
    while (n > 0) { int d = n % 10; sum += d * d * d; n /= 10; }
    return sum == original;
}

9. Bank account — encapsulation (Python)

class Bank:
    def __init__(self):
        self.__balance = 0        # private

    def deposit(self, amount):
        self.__balance += amount

    def get_balance(self):
        return self.__balance

class Animal:
    def sound(self):
        print('Some sound')

class Dog(Animal):
    def sound(self):
        print('Bark')

10. Sorting fundamentals (Python)

def bubble_sort(arr):
    n = len(arr)
    for i in range(n):
        for j in range(0, n - i - 1):
            if arr[j] > arr[j + 1]:
                arr[j], arr[j + 1] = arr[j + 1], arr[j]
    return arr

def insertion_sort(arr):
    for i in range(1, len(arr)):
        key, j = arr[i], i - 1
        while j >= 0 and arr[j] > key:
            arr[j + 1] = arr[j]
            j -= 1
        arr[j + 1] = key
    return arr