Capgemini interview questions & answers

20 real Capgemini interview questions with full model answers — Coding. Drawn from the same verified bank ChannelPulse drills from (33 Capgemini questions in total).

CodingEasyCapgeminiSoftware Engineer

1. Find the Index of the First Occurrence in a String (LeetCode)

Model answer

The task

Given a text string and a pattern string, return the starting index of the pattern’s first occurrence in the text. Return -1 if it does not occur; an empty pattern matches at index 0.

Key idea

Use Knuth–Morris–Pratt (KMP). Its prefix table lets the search reuse information about matched characters instead of restarting from scratch after a mismatch.

Approach

  1. Build a prefix table for the pattern. At each position, it records the length of the longest proper prefix that is also a suffix.
  2. Scan the text while tracking how many pattern characters currently match.
  3. On a mismatch, use the prefix table to find the next viable match length.
  4. Return the match’s starting index when the entire pattern matches; otherwise return -1.
class Solution:
    def strStr(self, haystack: str, needle: str) -> int:
        if not needle:
            return 0

        # Build the longest-prefix-suffix table for needle.
        lps = [0] * len(needle)
        prefix_len = 0
        i = 1

        while i < len(needle):
            if needle[i] == needle[prefix_len]:
                prefix_len += 1
                lps[i] = prefix_len
                i += 1
            elif prefix_len > 0:
                prefix_len = lps[prefix_len - 1]
            else:
                i += 1

        # Search haystack without rechecking matched characters.
        text_i = 0
        pattern_i = 0

        while text_i < len(haystack):
            if haystack[text_i] == needle[pattern_i]:
                text_i += 1
                pattern_i += 1

                if pattern_i == len(needle):
                    return text_i - pattern_i
            elif pattern_i > 0:
                pattern_i = lps[pattern_i - 1]
            else:
                text_i += 1

        return -1

Complexity:

  • Time: O(n + m), where n and m are the text and pattern lengths.
  • Space: O(m), for the prefix table.

Common follow-ups

  • How would you handle many pattern searches in the same text? Build an index or use a multi-pattern algorithm such as Aho–Corasick.
  • What if the text arrives as a stream? Keep the KMP match state and prefix table between chunks.
  • How would you find all occurrences? After each full match, record its start and reset the pattern index using the final prefix-table value.
CodingEasyCapgeminiSoftware Engineer

2. Roman to Integer (LeetCode)

Model answer

The task

Convert a string of Roman numeral symbols into its integer value. Roman numerals use a small set of symbols, with some smaller values placed before larger ones to indicate subtraction.

Key idea

Scan the string from left to right, comparing each symbol’s value with the next one. If the current value is smaller, subtract it; otherwise, add it. This handles subtractive pairs without needing to process them separately.

Approach

  1. Store the integer value for each Roman numeral symbol in a lookup table.
  2. Initialize a running total to zero.
  3. For each symbol, compare its value with the following symbol’s value, if one exists.
  4. Subtract the current value when it is smaller than the next value; otherwise, add it.
  5. Return the total. This assumes the input is a valid Roman numeral.
class Solution:
    def romanToInt(self, s: str) -> int:
        values = {
            "I": 1,
            "V": 5,
            "X": 10,
            "L": 50,
            "C": 100,
            "D": 500,
            "M": 1000,
        }

        total = 0

        for i, symbol in enumerate(s):
            current = values[symbol]

            # A smaller value before a larger value is subtracted.
            if i + 1 < len(s) and current < values[s[i + 1]]:
                total -= current
            else:
                total += current

        return total

Complexity: Time: O(n), where n is the string length, since each symbol is visited once.

Complexity: Space: O(1), because the lookup table has a fixed number of entries.

Common follow-ups

  • How would you handle invalid Roman numeral strings? Validate symbol order and repetition rules before or during conversion.
  • How would you convert an integer to a Roman numeral? Greedily subtract from a descending list of allowed values, including subtractive pairs.
  • Can the conversion be done scanning right to left? Yes; subtract a value if it is smaller than the largest value already seen to its right, otherwise add it.
CodingEasyCapgeminiSoftware Engineer

3. Palindrome Number (LeetCode)

Model answer

The task

Determine whether an integer reads the same from left to right and right to left. Negative values are not palindromes.

Key idea

Reverse only the last half of the digits, then compare it with the remaining first half. This avoids converting to a string and keeps the extra space constant.

Approach

  1. Return False for negative integers.
  2. Return False for positive integers ending in zero; zero itself is a palindrome.
  3. Repeatedly move the last digit from the number to a reversed-half accumulator.
  4. Stop when the accumulator has at least as many digits as the remaining number.
  5. Compare the halves directly for even digit counts, or discard the middle digit for odd counts.
class Solution:
    def isPalindrome(self, x: int) -> bool:
        # Negative numbers have a leading minus sign, so they cannot be palindromes.
        if x < 0:
            return False

        # A positive number ending in zero would need a leading zero to be palindromic.
        if x != 0 and x % 10 == 0:
            return False

        reversed_half = 0

        # Move digits until the reversed half is at least as long as the remaining half.
        while x > reversed_half:
            reversed_half = reversed_half * 10 + x % 10
            x //= 10

        # For an odd number of digits, ignore the middle digit.
        return x == reversed_half or x == reversed_half // 10

Complexity:

  • Time: O(log₁₀ n), for processing the digits of the number.
  • Space: O(1), using only a few integer variables.

Common follow-ups

  • How would you check a palindrome by converting to a string? Compare symmetric characters, using O(log n) extra space.
  • How would you avoid integer overflow in a fixed-width language? Reversing only half the digits keeps the accumulator bounded.
  • What about zero and numbers ending in zero? Zero is palindromic; other numbers ending in zero are not.
CodingEasyCapgeminiSoftware Engineer

4. Two Sum (LeetCode)

Model answer

The task

Given a list of integers and a target, return the indices of two distinct elements whose values add up to the target. The usual version guarantees a valid pair.

Key idea

As we scan the list, store each value’s index in a hash table. For the current value, check whether its needed complement has already appeared; this finds a pair in one pass.

Approach

  1. Create a dictionary mapping previously seen values to their indices.
  2. For each element, compute the complement needed to reach the target.
  3. If that complement is in the dictionary, return its stored index and the current index.
  4. Otherwise, store the current value and index, then continue.
from typing import List

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        # Map each value already visited to its index.
        seen = {}

        for index, value in enumerate(nums):
            complement = target - value

            # A match must come from an earlier, distinct element.
            if complement in seen:
                return [seen[complement], index]

            seen[value] = index

        # The standard problem guarantees a solution.
        raise ValueError("No two elements sum to the target")

Complexity:

  • Time: O(n), where n is the number of elements; each lookup and insertion is O(1) on average.
  • Space: O(n), for the dictionary of values seen so far.

Common follow-ups

  • What if there may be multiple valid pairs? Return the first pair found, or keep searching and collect pairs according to the required output rules.
  • What if the input is sorted? Use two pointers from opposite ends for O(1) extra space; preserve original indices if those are required.
  • What if values repeat? The dictionary stores indices, and checking before insertion ensures the current element is not paired with itself.
CodingEasyCapgeminiSoftware Engineer

5. Remove Duplicates from Sorted List (LeetCode)

Model answer

The task

Given the head of a sorted singly linked list, remove repeated values so that each value appears once. Return the head of the resulting list.

Key idea

Because the list is sorted, any repeated values are adjacent. Walk through the list and bypass a node whenever its value matches the current node’s value.

Approach

  1. Start at the head.
  2. While the current node has a next node, compare their values.
  3. If they match, link the current node directly to the node after its duplicate.
  4. Otherwise, advance to the next node.
  5. Return the original head; it remains unchanged, including when the list is empty.
# Assumes the usual ListNode definition:
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next

class Solution:
    def deleteDuplicates(self, head: ListNode | None) -> ListNode | None:
        current = head

        while current is not None and current.next is not None:
            if current.val == current.next.val:
                # Skip the duplicate node.
                current.next = current.next.next
            else:
                current = current.next

        return head

Complexity:

  • Time: O(n), where n is the number of nodes; each node is examined a constant number of times.
  • Space: O(1), since the list is modified in place.

Common follow-ups

  • What if the list is not sorted? Use a set to track seen values; this takes O(n) extra space.
  • What if every occurrence of a duplicated value should be removed? Track runs of equal values and connect only values that occur once.
  • What if the list contains no nodes or just one node? The traversal makes no changes and returns the original head.
CodingEasyCapgeminiSoftware Engineer

6. Add Binary (LeetCode)

Model answer

The task

Given two strings representing binary numbers, return their sum as a binary string.

Key idea

Add digits from right to left, keeping a carry just as in ordinary column addition. This avoids converting potentially long strings to integers.

Approach

  1. Start at the last character of each string with a carry of zero.
  2. While either string has digits left or a carry remains, add the available digits and the carry.
  3. Append the sum’s low bit; use the remaining value as the next carry.
  4. Reverse the collected digits to produce the result.
class Solution:
    def addBinary(self, a: str, b: str) -> str:
        i, j = len(a) - 1, len(b) - 1
        carry = 0
        result = []

        while i >= 0 or j >= 0 or carry:
            total = carry

            if i >= 0:
                total += int(a[i])
                i -= 1

            if j >= 0:
                total += int(b[j])
                j -= 1

            result.append(str(total % 2))
            carry = total // 2

        return "".join(reversed(result))

Complexity:

  • Time: O(max(n, m)), where n and m are the input lengths.
  • Space: O(max(n, m)) for the output digits.

Common follow-ups

  • How would you handle signed binary values? Define a representation such as two’s complement, then account for its fixed width.
  • Can you avoid converting each character to an integer? Subtract '0' from each character to obtain its digit.
  • What if the inputs contain leading zeroes? The addition still works; optionally normalize the returned string.
  • How would you add many binary strings? Repeatedly apply pairwise addition, or use a suitable multi-operand addition strategy.
CodingEasyCapgeminiSoftware Engineer

7. Remove Duplicates from Sorted Array (LeetCode)

Model answer

The task

Given a sorted list of integers, modify it in place so each distinct value appears once in the front. Return the length of that unique prefix.

Key idea

Because the values are sorted, duplicates are adjacent. Keep a read pointer to scan the list and a write pointer for the next position where a new value belongs.

Approach

  1. If the list is empty, return 0.
  2. Start the write pointer at 1, since the first value is already unique.
  3. Scan from left to right.
  4. When the current value differs from the last value written, copy it to the write position and advance the pointer.
  5. Return the write pointer as the unique-prefix length.
from typing import List

class Solution:
    def removeDuplicates(self, nums: List[int]) -> int:
        if not nums:
            return 0

        write = 1

        # Copy each newly encountered value into the unique prefix.
        for read in range(1, len(nums)):
            if nums[read] != nums[write - 1]:
                nums[write] = nums[read]
                write += 1

        return write

Complexity:

  • Time: O(n), where n is the length of the list.
  • Space: O(1), since the list is modified in place using only a fixed number of variables.

Common follow-ups

  • What if the list is not sorted? Use a set to track seen values while compacting unique values in their original order.
  • What if each value may appear at most twice? Write a value when fewer than two values have been written, or when it differs from the value two positions back.
  • What if the list is very large and cannot fit in memory? Process sorted chunks while carrying the last value across chunk boundaries.
CodingEasyCapgeminiSoftware Engineer

8. Merge Two Sorted Lists (LeetCode)

Model answer

The task

Given the heads of two sorted singly linked lists, combine their nodes into one sorted list. Return the head of the merged list.

Key idea

At each step, append the smaller of the two current nodes, then advance that list. A dummy node simplifies handling the merged list’s head.

Approach

  1. Create a dummy node and set a pointer to it.
  2. While both lists have nodes, compare their values.
  3. Link the smaller node after the pointer and advance its source list.
  4. Advance the pointer.
  5. Link any remaining nodes and return the node after the dummy.
# LeetCode provides the ListNode class.
class Solution:
    def mergeTwoLists(self, list1, list2):
        dummy = ListNode(0)
        tail = dummy

        # Repeatedly attach the smaller current node.
        while list1 and list2:
            if list1.val <= list2.val:
                tail.next = list1
                list1 = list1.next
            else:
                tail.next = list2
                list2 = list2.next

            tail = tail.next

        # At most one list remains; it is already sorted.
        tail.next = list1 if list1 else list2
        return dummy.next

Complexity:

  • Time: O(m + n), where m and n are the lengths of the lists.
  • Space: O(1) extra space; the existing nodes are relinked.

Common follow-ups

  • How would you implement this recursively? Choose the smaller head and recursively merge the rest; this uses O(m + n) call-stack space.
  • What if the lists are sorted in descending order? Adjust the comparison or reverse the merged result, depending on the desired output order.
  • What if one list is empty? The remaining list is returned directly.
CodingEasyCapgeminiSoftware Engineer

9. Longest Common Prefix (LeetCode)

Model answer

The task

Given a list of strings, return the longest string that is a prefix of every entry. If there is no shared prefix, return an empty string.

Key idea

Compare characters at the same position across all strings, starting from the first string. Stop at the first mismatch or when any string runs out.

Approach

  1. If the list is empty, return an empty string.
  2. Scan each character of the first string from left to right.
  3. For each position, compare that character with the character at the same position in every other string.
  4. If a string is too short or a character differs, return the matching prefix before that position.
  5. If all positions match, return the first string.
from typing import List

class Solution:
    def longestCommonPrefix(self, strs: List[str]) -> str:
        if not strs:
            return ""

        first = strs[0]

        for i, char in enumerate(first):
            for word in strs[1:]:
                if i == len(word) or word[i] != char:
                    return first[:i]

        return first

Complexity:

  • Time: O(S), where S is the total number of characters inspected.
  • Space: O(1) auxiliary space, excluding the returned prefix.

Common follow-ups

  • How would you handle many prefix queries over the same set of strings? Build a trie once, then traverse it to find shared prefixes.
  • Could sorting help? Yes. Sort the strings and compare only the first and last; their common prefix is shared by all strings.
  • What if strings arrive as a stream? Keep a running prefix and shorten it as each new string arrives.
CodingEasyCapgeminiSoftware Engineer

10. Best Time to Buy and Sell Stock (LeetCode)

Model answer

The task

Given daily stock prices, find the greatest profit possible from one buy followed by one later sale. If no sale would make money, return zero.

Key idea

As we scan the prices, keep the lowest price seen so far. Treat each current price as a possible sale and update the best profit using the difference from that minimum.

Approach

  1. Initialize the minimum price to a value larger than any price and the best profit to zero.
  2. Visit each price in order.
  3. Update the minimum price with the current price.
  4. Check the profit from selling today and update the best profit.
  5. Return the best profit.
class Solution:
    def maxProfit(self, prices: list[int]) -> int:
        min_price = float("inf")
        best_profit = 0

        for price in prices:
            # The current price can be a new best day to buy.
            min_price = min(min_price, price)

            # Or it can be the day to sell after the cheapest earlier buy.
            best_profit = max(best_profit, price - min_price)

        return best_profit

Complexity:

  • Time: O(n), where n is the number of prices; each is processed once.
  • Space: O(1), since only a few variables are stored.

Common follow-ups

  • What if multiple buy-and-sell transactions are allowed? Sum the gains from every adjacent price increase.
  • What if a transaction fee is charged? Track the best holding and non-holding profits, incorporating the fee when selling.
  • What if at most k transactions are allowed? Use dynamic programming over the number of completed transactions and whether a share is currently held.
CodingEasyCapgeminiSoftware Engineer

11. Plus One (LeetCode)

Model answer

The task

Given a non-empty list of decimal digits representing a non-negative integer, return the digits for that number after adding one.

Key idea

Start at the least significant digit. Increment it if possible; otherwise turn it to zero and carry one to the next digit. If every digit was nine, the result needs an extra leading one.

Approach

  1. Scan the digits from right to left.
  2. If a digit is less than nine, increment it and return the list.
  3. Otherwise, set it to zero and continue carrying.
  4. If the scan finishes, return a new list with one at the front.
class Solution:
    def plusOne(self, digits: list[int]) -> list[int]:
        # Propagate the carry from the least significant digit.
        for i in range(len(digits) - 1, -1, -1):
            if digits[i] < 9:
                digits[i] += 1
                return digits

            digits[i] = 0

        # Every digit was 9, so the result has one extra digit.
        return [1] + digits

Complexity:

  • Time: O(n), where n is the number of digits in the worst case.
  • Space: O(n) in the all-nines case for the returned list; otherwise O(1) additional space.

Common follow-ups

  • What if the digits represent a number in another base? Use that base’s maximum digit (base - 1) in place of nine.
  • Why not convert the digits to an integer? The value may exceed the language’s supported integer range, and digit-wise carry works without constructing it.
  • What if the input must remain unchanged? Copy the list first, then apply the same carry process to the copy.
CodingEasyCapgeminiSoftware Engineer

12. Chunk Array (LeetCode)

Model answer

The task

Partition an array into consecutive chunks of a requested maximum size, keeping the original order. The final chunk may be smaller than the others.

Key idea

Advance through the array in steps equal to the chunk size. Each step takes the slice from the current position up to the next chunk boundary.

Approach

  1. Ensure the requested chunk size is positive.
  2. Start at index 0 and move forward by size each iteration.
  3. Append the slice for that range; Python naturally returns a shorter slice for the final chunk if needed.
  4. Return the collected chunks. An empty input produces an empty list.
from typing import List, TypeVar

T = TypeVar("T")

def chunk_array(arr: List[T], size: int) -> List[List[T]]:
    """Split arr into consecutive chunks, each of length at most size."""
    if size <= 0:
        raise ValueError("size must be positive")

    chunks: List[List[T]] = []

    for start in range(0, len(arr), size):
        chunks.append(arr[start:start + size])

    return chunks

Complexity:

  • Time: O(n), where n is the number of array elements copied into chunks.
  • Space: O(n) for the returned chunks; the slices contain copies of the elements’ references.

Common follow-ups

  • What if the final chunk must be padded? Append the required padding values to the final chunk.
  • What if chunks should be produced lazily? Yield each slice from a generator instead of collecting a list.
  • What if the original array must not be copied? Return index ranges or views, if the language and array type support them.
CodingEasyCapgeminiSoftware Engineer

13. Move Zeroes (LeetCode)

Model answer

The task

Rearrange an integer array in place so all zeroes come after the nonzero values. Keep the nonzero values in their original relative order.

Key idea

Use a write pointer to mark where the next nonzero value belongs. Scan the array once, swapping each nonzero value into that position; this keeps the nonzero values stable and uses constant extra space.

Approach

  1. Set write to the first available position for a nonzero value.
  2. Scan each index from left to right.
  3. When a nonzero value is found, swap it with the value at write.
  4. Advance write after each nonzero value.
  5. Once the scan ends, all remaining positions contain zeroes.
from typing import List

class Solution:
    def moveZeroes(self, nums: List[int]) -> None:
        # The next nonzero value belongs at index write.
        write = 0

        for read in range(len(nums)):
            if nums[read] != 0:
                nums[write], nums[read] = nums[read], nums[write]
                write += 1

Complexity:

  • Time: O(n), where n is the array length; each value is examined once.
  • Space: O(1), since rearrangement is done in place.

Common follow-ups

  • What if relative order does not matter? Partitioning zeroes and nonzeroes can be done with two pointers, potentially with fewer assignments.
  • Can you reduce unnecessary writes? Swap only when read != write; this avoids self-swaps.
  • What if the input is a linked list? Relink nonzero nodes in their original order, then append the zero-valued nodes.
CodingEasyCapgeminiSoftware Engineer

14. Reverse Degree of a String (LeetCode)

Model answer

The task

Compute a string’s reverse degree by multiplying each lowercase letter’s reverse-alphabet position by its 1-based position in the string, then summing those products.

Key idea

A letter’s reverse-alphabet position is 26 - (ord(letter) - ord('a')). Scan the string once, using the index to apply its position weight.

Approach

  1. Initialize a running total to zero.
  2. Visit each character along with its zero-based index.
  3. Convert the character to its reverse-alphabet position.
  4. Multiply that value by index + 1 and add it to the total.
  5. Return the total.
class Solution:
    def reverseDegree(self, s: str) -> int:
        total = 0

        for index, char in enumerate(s):
            reverse_position = 26 - (ord(char) - ord('a'))
            total += (index + 1) * reverse_position

        return total

Complexity:

  • Time: O(n), where n is the string length.
  • Space: O(1), using only a few variables.

Common follow-ups

  • How would you handle uppercase letters? Normalize the input to lowercase, or map uppercase letters using the same alphabet-position calculation.
  • What if the alphabet has a different size? Replace 26 with the alphabet’s size and adjust the character-to-position mapping.
  • Can the calculation stop early? Only if a known bound proves the remaining terms cannot change the desired result; for the exact sum, all characters must be processed.
CodingEasyCapgeminiSoftware Engineer

15. Contains Duplicate (LeetCode)

Model answer

The task

Determine whether an integer array contains at least one value that appears more than once. Return True if it does and False otherwise.

Key idea

Track values seen so far in a hash set. If a value is already in the set, a duplicate has been found; otherwise, add it and continue.

Approach

  1. Create an empty set.
  2. Scan the array from left to right.
  3. For each value, check whether it is already in the set.
  4. Return True if it is; otherwise, add the value to the set.
  5. If the scan finishes, return False.
from typing import List

class Solution:
    def containsDuplicate(self, nums: List[int]) -> bool:
        seen = set()

        for value in nums:
            if value in seen:
                return True
            seen.add(value)

        return False

Complexity:

  • Time: O(n) on average; each set lookup and insertion takes O(1) on average.
  • Space: O(n) in the worst case, when all values are distinct.

Common follow-ups

  • Can you reduce auxiliary space? Sort the array in place, then compare each pair of adjacent values; this takes O(1) extra space if in-place sorting is allowed.
  • What if the input is too large to fit in memory? Partition or hash values across storage, then check each partition for repeats.
  • How does the method handle an empty or single-element array? It returns False, since neither can contain a duplicate.
CodingEasyCapgeminiSoftware Engineer

16. Valid Anagram (LeetCode)

Model answer

The task

Determine whether two strings contain the same characters with the same frequencies, regardless of order.

Key idea

Anagrams have identical character counts. Count the characters in each string and compare the resulting frequency maps.

Approach

  1. If the strings have different lengths, return False.
  2. Build a frequency map for each string.
  3. Return whether the maps are equal.
from collections import Counter

class Solution:
    def isAnagram(self, s: str, t: str) -> bool:
        # Different lengths cannot have matching character counts.
        if len(s) != len(t):
            return False

        # Anagrams have exactly the same character frequencies.
        return Counter(s) == Counter(t)

Complexity:

  • Time: O(n), where n is the length of either string; counting and comparison are linear.
  • Space: O(k), where k is the number of distinct characters stored in the frequency maps.

Common follow-ups

  • Can you do this without two maps? Update one frequency map using s, then decrement counts using t; verify all counts return to zero.
  • What if the input is guaranteed to contain only lowercase English letters? Use a fixed-size array of 26 counters instead of maps.
  • What if sorting is allowed? Sort both strings and compare them; this takes O(n log n) time.
CodingEasyCapgeminiSoftware Engineer

17. Number of Unique Subjects Taught by Each Teacher (LeetCode)

Model answer

The task

For each teacher, count how many distinct subjects they teach. Return each teacher’s ID and that count.

Key idea

Group rows by teacher and use COUNT(DISTINCT ...) to avoid counting a subject more than once for the same teacher.

Approach

  1. Read the teacher records.
  2. Group them by teacher_id.
  3. Count distinct subject_id values in each group.
  4. Return the teacher ID and the count.
SELECT
    teacher_id,
    COUNT(DISTINCT subject_id) AS cnt
FROM Teacher
GROUP BY teacher_id;

Complexity:

  • Time: O(N log N), where N is the number of records; grouping and distinct counting may require sorting or indexing.
  • Space: O(N) in the worst case for intermediate grouping or distinct-value storage.

Common follow-ups

  • What if a teacher has multiple records for the same subject? COUNT(DISTINCT subject_id) counts it only once.
  • How would you count distinct subjects per teacher and department? Group by both teacher_id and dept_id.
  • Can an index help? An index on (teacher_id, subject_id) may improve grouping and distinct counting.
CodingMediumCapgeminiSoftware Engineer

18. 4Sum (LeetCode)

Model answer

The task

Return all distinct groups of four values from the array whose sum equals the target. Each group should appear only once, regardless of which matching indices produced it.

Key idea

Sort the array, fix two values with nested loops, then use two pointers to find the remaining pair. Skip repeated values at each step to avoid duplicate groups.

Approach

  1. Sort the array.
  2. Choose the first value, skipping duplicates.
  3. Choose the second value, also skipping duplicates.
  4. Search the remaining suffix with left and right pointers, moving them according to the current sum.
  5. When a group matches, add it and advance both pointers past any repeated values.
from typing import List

class Solution:
    def fourSum(self, nums: List[int], target: int) -> List[List[int]]:
        nums.sort()
        n = len(nums)
        result: List[List[int]] = []

        for i in range(n - 3):
            if i > 0 and nums[i] == nums[i - 1]:
                continue

            for j in range(i + 1, n - 2):
                if j > i + 1 and nums[j] == nums[j - 1]:
                    continue

                left, right = j + 1, n - 1

                while left < right:
                    total = nums[i] + nums[j] + nums[left] + nums[right]

                    if total == target:
                        result.append(
                            [nums[i], nums[j], nums[left], nums[right]]
                        )
                        left += 1
                        right -= 1

                        # Skip duplicate values so each group is added once.
                        while left < right and nums[left] == nums[left - 1]:
                            left += 1
                        while left < right and nums[right] == nums[right + 1]:
                            right -= 1
                    elif total < target:
                        left += 1
                    else:
                        right -= 1

        return result

Complexity:

  • Time: O(n³), from two loops and a two-pointer scan.
  • Space: O(n + k), for sorting and the k groups stored in the result.

Common follow-ups

  • How would you avoid sorting the input in place? Sort a copy, at the cost of O(n) additional space.
  • Can this be generalized to k-Sum? Fix one value recursively, reducing k until a two-pointer 2-Sum search remains.
  • What if only the count of groups is needed? Count matches during the scan instead of storing each group.
CodingMediumCapgeminiSoftware Engineer

19. Reverse Words in a String (LeetCode)

Model answer

The task

Return the words of a string in reverse order, with exactly one space between words and no leading or trailing spaces. Treat any run of whitespace as a separator.

Key idea

Reverse the entire character array, then reverse each word to restore its letters. While scanning, compact words in place and write only one space between them.

Approach

  1. Convert the string to a mutable character array and reverse it.
  2. Scan past whitespace to find each word.
  3. Reverse the letters within that word.
  4. Copy the word to the next write position, inserting one space if needed.
  5. Join the compacted portion of the array.
class Solution:
    def reverseWords(self, s: str) -> str:
        chars = list(s)
        n = len(chars)

        def reverse(left: int, right: int) -> None:
            while left < right:
                chars[left], chars[right] = chars[right], chars[left]
                left += 1
                right -= 1

        # Reversing the whole string puts the words in reverse order.
        reverse(0, n - 1)

        read = 0
        write = 0

        while read < n:
            # Skip any whitespace between words.
            while read < n and chars[read].isspace():
                read += 1

            if read == n:
                break

            start = read

            # Find the end of the current word.
            while read < n and not chars[read].isspace():
                read += 1

            end = read - 1
            reverse(start, end)

            # Keep exactly one space between output words.
            if write > 0:
                chars[write] = " "
                write += 1

            # Compact this word into the output prefix.
            for i in range(start, end + 1):
                chars[write] = chars[i]
                write += 1

        return "".join(chars[:write])

Complexity:

  • Time: O(n), where n is the string length.
  • Space: O(n) for the mutable character array.

Common follow-ups

  • How would you handle only ordinary spaces as separators? Replace isspace() with comparisons to " ".
  • Can this be done in place? The character operations are in place, but Python strings are immutable, so the array requires O(n) space.
  • What if the input is a stream too large to fit in memory? Use an external or chunked representation, while preserving word boundaries between chunks.
CodingMediumCapgeminiSoftware Engineer

20. Find First and Last Position of Element in Sorted Array (LeetCode)

Model answer

The task

Given a sorted array and a target value, return the indices of its first and last occurrences. If the target is absent, return [-1, -1].

Key idea

Use binary search twice: once to find the first index whose value is at least the target, and once to find the first index whose value is greater than the target. The second boundary, minus one, is the target’s last index.

Approach

  1. Write a binary search that finds the first index meeting a chosen comparison.
  2. Find the first index with a value at least the target.
  3. If that index is past the array or does not contain the target, return [-1, -1].
  4. Find the first index with a value greater than the target.
  5. Return the first index and the second boundary minus one.
from typing import List

class Solution:
    def searchRange(self, nums: List[int], target: int) -> List[int]:
        def first_index(strictly_greater: bool) -> int:
            """Return the first index with value > target, or >= target."""
            left, right = 0, len(nums)

            while left < right:
                mid = (left + right) // 2
                qualifies = (
                    nums[mid] > target
                    if strictly_greater
                    else nums[mid] >= target
                )

                if qualifies:
                    right = mid
                else:
                    left = mid + 1

            return left

        first = first_index(strictly_greater=False)

        if first == len(nums) or nums[first] != target:
            return [-1, -1]

        after_last = first_index(strictly_greater=True)
        return [first, after_last - 1]

Complexity:

  • Time: O(log n), from two binary searches.
  • Space: O(1), excluding the returned list.

Common follow-ups

  • Can the search be done with one binary search? A single search finds only one occurrence; additional work is needed to locate both boundaries.
  • What if the array is empty? The first boundary is zero, so the method returns [-1, -1].
  • How would you count occurrences instead? Subtract the first index from the first index greater than the target.

Practice these out loud, don't memorise them

Reading an answer is not the same as being able to give one under pressure. ChannelPulse plays the interviewer, asks the follow-ups, and scores each answer with feedback and a model answer so you can hear the gap between what you said and what lands.

Get ChannelPulse Browse all questions