Infosys interview questions & answers

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

CodingEasyInfosysSoftware 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.
CodingEasyInfosysSoftware Engineer

2. Palindrome Linked List (LeetCode)

Model answer

The task

Determine whether a singly linked list reads the same from front to back and back to front. Return a boolean without relying on access to nodes by index.

Key idea

Find the midpoint with slow and fast pointers, then reverse the second half. Compare the two halves node by node; reverse the second half again afterward to restore the original list.

Approach

  1. Advance slow by one node and fast by two until fast reaches the end.
  2. For an odd-length list, move the start of the second half past the middle node.
  3. Reverse the second half in place.
  4. Compare corresponding values from the head and reversed second half.
  5. Restore the second half before returning the result.
class Solution:
    def isPalindrome(self, head):
        def reverse(node):
            previous = None
            while node:
                following = node.next
                node.next = previous
                previous = node
                node = following
            return previous

        slow = fast = head

        # Find the midpoint. For odd length, fast ends on the final node.
        while fast and fast.next:
            slow = slow.next
            fast = fast.next.next

        # Skip the middle node when the list has odd length.
        second_half_start = slow.next if fast else slow
        reversed_half = reverse(second_half_start)

        # Compare the first half with the reversed second half.
        left = head
        right = reversed_half
        is_palindrome = True

        while right:
            if left.val != right.val:
                is_palindrome = False
                break
            left = left.next
            right = right.next

        # Restore the list to its original structure.
        reverse(reversed_half)
        return is_palindrome

Complexity:

  • Time: O(n), to find the midpoint, reverse, compare, and restore.
  • Space: O(1), using only a few pointers.

Common follow-ups

  • What if the list must not be modified, even temporarily? Use a stack to store values, which takes O(n) extra space.
  • How can recursion solve it? Recursively compare nodes from the ends, using O(n) call-stack space.
  • What about empty or single-node lists? Both are palindromes; the code handles them directly.
CodingEasyInfosysSoftware Engineer

3. Merge Sorted Array (LeetCode)

Model answer

The task

Combine two already sorted arrays into one sorted array, placing the result in the first array. The first array has enough spare capacity to hold all elements from both arrays.

Key idea

Fill the first array from right to left. Comparing the largest remaining elements avoids overwriting values in the first array that have not yet been processed.

Approach

  1. Set pointers to the last valid elements of both arrays.
  2. Set a write pointer to the last slot in the first array.
  3. While the second array still has elements, compare the values at the two read pointers.
  4. Write the larger value at the write pointer, then move the corresponding read pointer and the write pointer left.
  5. Any remaining elements from the second array are copied into the first. Remaining elements from the first are already in place.
class Solution:
    def merge(self, nums1: list[int], m: int, nums2: list[int], n: int) -> None:
        """Merge nums2 into nums1 in-place, keeping nums1 sorted."""
        i = m - 1          # Last initialized element in nums1
        j = n - 1          # Last element in nums2
        write = m + n - 1  # Last available position in nums1

        # Fill from the back so unread nums1 elements are not overwritten.
        while j >= 0:
            if i >= 0 and nums1[i] > nums2[j]:
                nums1[write] = nums1[i]
                i -= 1
            else:
                nums1[write] = nums2[j]
                j -= 1
            write -= 1

Complexity:

  • Time: O(m + n), since each element is considered at most once.
  • Space: O(1), because the merge modifies the first array directly.

Common follow-ups

  • What if the arrays are sorted in descending order? Reverse the comparison or adapt the traversal direction.
  • What if the result must go into a separate array? Use two forward pointers and allocate O(m + n) extra space.
  • What if either array is empty? The loop naturally handles it; if the second is empty, the first is already complete.
  • Why merge from the end? Writing from the front could overwrite unprocessed elements in the first array.
CodingEasyInfosysSoftware Engineer

4. Trionic Array I (LeetCode)

Model answer

The task

Determine whether the array has three nonempty phases: strictly increasing, then strictly decreasing, then strictly increasing.

Key idea

Scan from left to right, consuming each phase in order. Each phase must contain at least one step, and all elements must be consumed by the final increasing phase.

Approach

  1. Start at the second element and consume the initial strictly increasing run.
  2. If that run is empty or ends at the array’s end, return False.
  3. Consume a strictly decreasing run; return False if it is empty or reaches the end.
  4. Consume a strictly increasing run.
  5. Return True only if that final run is nonempty and reaches the end of the array.
from typing import List

class Solution:
    def isTrionic(self, nums: List[int]) -> bool:
        n = len(nums)
        i = 1

        # First phase: strictly increasing.
        while i < n and nums[i] > nums[i - 1]:
            i += 1

        # Require a nonempty first phase and room for the next one.
        if i == 1 or i == n:
            return False

        # Second phase: strictly decreasing.
        decreasing_start = i
        while i < n and nums[i] < nums[i - 1]:
            i += 1

        # Require a nonempty second phase and room for the last one.
        if i == decreasing_start or i == n:
            return False

        # Third phase: strictly increasing.
        increasing_start = i
        while i < n and nums[i] > nums[i - 1]:
            i += 1

        # The final phase must be nonempty and consume the rest.
        return i > increasing_start and i == n

Complexity:

  • Time: O(n), since each element is checked at most once.
  • Space: O(1), using only a few indices.

Common follow-ups

  • What if equal adjacent values are allowed? Change the comparisons to allow equality in the relevant phases.
  • How would you return the turning points? Record the index where each phase ends during the scan.
  • How would you support more alternating phases? Track the expected direction and count completed nonempty runs.
CodingEasyInfosysSoftware Engineer

5. 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.
CodingEasyInfosysSoftware Engineer

6. Implement Queue using Stacks (LeetCode)

Model answer

The task

Build a queue that supports adding to the back, removing or inspecting the front, and checking whether it is empty, using only stacks.

Key idea

Use one stack to collect newly added items and another to serve items in queue order. When the serving stack is empty, move all items from the collection stack into it; this reverses their order so the oldest item is on top.

Approach

  1. Initialize an input stack and an output stack.
  2. For push, append the new item to the input stack.
  3. Before pop or peek, transfer items from input to output if output is empty.
  4. For pop, remove and return the top of output; for peek, return it without removing.
  5. For empty, report whether both stacks are empty.
class MyQueue:
    def __init__(self):
        self.input_stack = []
        self.output_stack = []

    def push(self, x: int) -> None:
        # New items are collected here.
        self.input_stack.append(x)

    def _prepare_output(self) -> None:
        # Reverse the input stack only when needed.
        if not self.output_stack:
            while self.input_stack:
                self.output_stack.append(self.input_stack.pop())

    def pop(self) -> int:
        self._prepare_output()
        return self.output_stack.pop()

    def peek(self) -> int:
        self._prepare_output()
        return self.output_stack[-1]

    def empty(self) -> bool:
        return not self.input_stack and not self.output_stack

Complexity:

  • Time: O(1) amortized per operation; each item moves between stacks at most once.
  • Space: O(n), for the items stored across both stacks.

Common follow-ups

  • What is the worst-case time for one pop? O(n), if it triggers a transfer of all queued items.
  • Can you use a single stack? Yes, but preserving queue order generally requires recursion or another storage mechanism.
  • What happens if pop or peek is called on an empty queue? Define an error or sentinel behavior, depending on the API contract.
CodingEasyInfosysSoftware Engineer

7. Maximum Units on a Truck (LeetCode)

Model answer

The task

Given box types with a count and a number of units per box, choose at most the truck’s capacity in boxes to maximize the total units loaded.

Key idea

A box with more units is always at least as valuable as one with fewer units, since each box uses the same amount of capacity. So consider box types in descending order of units per box and take as many as possible from each.

Approach

  1. Sort the box types by units per box, highest first.
  2. Keep track of the remaining box capacity and the total units collected.
  3. For each type, take the smaller of its available count and the remaining capacity.
  4. Add the units from those boxes and reduce the remaining capacity.
  5. Stop when the truck is full or there are no more box types.
class Solution:
    def maximumUnits(self, boxTypes: list[list[int]], truckSize: int) -> int:
        # Consider the most valuable boxes first.
        boxTypes.sort(key=lambda box_type: box_type[1], reverse=True)

        total_units = 0
        remaining_capacity = truckSize

        for box_count, units_per_box in boxTypes:
            boxes_to_load = min(box_count, remaining_capacity)
            total_units += boxes_to_load * units_per_box
            remaining_capacity -= boxes_to_load

            if remaining_capacity == 0:
                break

        return total_units

Complexity:

  • Time: O(n log n), to sort the n box types.
  • Space: O(n), for the sorting implementation’s temporary storage.

Common follow-ups

  • What if box types arrive as a stream? Use a max-heap if you must choose among types seen so far; otherwise, exact optimality may require seeing all types first.
  • What if each box type has a different weight? Rank boxes by units per unit of weight only for the fractional variant; indivisible boxes become a knapsack problem.
  • What if the truck has no capacity? The method returns zero because it loads no boxes.
CodingEasyInfosysSoftware Engineer

8. Symmetric Tree (LeetCode)

Model answer

The task

Determine whether a binary tree is symmetric around its center: its left and right subtrees must be mirror images.

Key idea

Compare nodes in mirrored pairs. For each pair, their values must match, and their outer children and inner children must also match as mirrored pairs.

Approach

  1. Put the root’s left and right children into a queue as a pair.
  2. Remove a pair; if both nodes are absent, continue. If only one is absent or their values differ, return False.
  3. Add the outer pair of children and the inner pair of children to the queue.
  4. If every pair matches, return True.
from collections import deque
from typing import Optional

class Solution:
    def isSymmetric(self, root: Optional[TreeNode]) -> bool:
        if root is None:
            return True

        queue = deque([(root.left, root.right)])

        while queue:
            left, right = queue.popleft()

            # Missing nodes must occur in matching positions.
            if left is None or right is None:
                if left is not right:
                    return False
                continue

            if left.val != right.val:
                return False

            # Compare mirrored child positions.
            queue.append((left.left, right.right))
            queue.append((left.right, right.left))

        return True

Complexity:

  • Time: O(n), where n is the number of nodes; each node is checked at most once.
  • Space: O(n) in the worst case for the queue.

Common follow-ups

  • Can this be solved recursively? Yes; define a helper that checks a pair of mirrored nodes and recursively compares their outer and inner children.
  • What if node values are not unique? The method still works because it checks both values and structure.
  • What if the tree is very deep? The iterative queue avoids recursion-depth limits; its memory use depends on the tree’s maximum width.
CodingEasyInfosysSoftware Engineer

9. Can Place Flowers (LeetCode)

Model answer

The task

Given a row of plots where 1 marks an occupied plot and 0 an empty one, decide whether at least n flowers can be added without placing flowers in neighboring plots.

Key idea

Scan from left to right, planting in an empty plot whenever both neighboring plots are empty or outside the row. Greedily planting at the earliest available plot cannot reduce the number of later planting opportunities.

Approach

  1. Return True immediately if n is zero.
  2. Visit each plot from left to right.
  3. For an empty plot, check its left and right neighbors, treating the row boundaries as empty.
  4. If both are empty, plant there and decrement n.
  5. Return True once n reaches zero; otherwise return whether it reached zero by the end.
from typing import List

class Solution:
    def canPlaceFlowers(self, flowerbed: List[int], n: int) -> bool:
        if n == 0:
            return True

        for i in range(len(flowerbed)):
            if flowerbed[i] == 0:
                left_empty = i == 0 or flowerbed[i - 1] == 0
                right_empty = (
                    i == len(flowerbed) - 1 or flowerbed[i + 1] == 0
                )

                if left_empty and right_empty:
                    flowerbed[i] = 1
                    n -= 1

                    if n == 0:
                        return True

        return False

Complexity:

  • Time: O(m), where m is the number of plots; each plot is checked at most once.
  • Space: O(1), using only a fixed amount of extra space.

Common follow-ups

  • What if the input must not be modified? Track the previous plot’s occupancy instead of planting in the array.
  • How would you return the planting positions? Record each plot index when the greedy rule permits planting.
  • What if plots wrap around in a circle? Handle the first and last plots as neighbors, with special care for rows of length one or two.
CodingEasyInfosysSoftware Engineer

10. 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.
CodingEasyInfosysSoftware Engineer

11. 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.
CodingEasyInfosysSoftware Engineer

12. Valid Palindrome (LeetCode)

Model answer

The task

Determine whether a string reads the same forward and backward after disregarding characters that are not letters or digits and treating uppercase and lowercase as equivalent.

Key idea

Compare characters from both ends, skipping anything that should be ignored. If every remaining pair matches, the string is a palindrome.

Approach

  1. Initialize pointers at the start and end of the string.
  2. Move the left pointer past non-alphanumeric characters.
  3. Move the right pointer past non-alphanumeric characters.
  4. Compare the lowercase forms of the characters at the pointers; return False if they differ.
  5. Move both pointers inward and continue. If they meet or cross, return True.
class Solution:
    def isPalindrome(self, s: str) -> bool:
        left, right = 0, len(s) - 1

        while left < right:
            # Ignore characters that are not letters or digits.
            while left < right and not s[left].isalnum():
                left += 1
            while left < right and not s[right].isalnum():
                right -= 1

            # Compare without regard to letter case.
            if s[left].lower() != s[right].lower():
                return False

            left += 1
            right -= 1

        return True

Complexity:

  • Time: O(n), where n is the string length; each pointer moves only inward.
  • Space: O(1), since the comparisons use no additional data structure.

Common follow-ups

  • What if the input contains no letters or digits? It is considered a palindrome, since there are no mismatching characters.
  • Can you avoid creating a normalized copy of the string? Yes; the two-pointer scan uses constant extra space.
  • How would you handle Unicode normalization? Normalize the string first if canonically equivalent characters should compare as equal; that may require additional space.
CodingEasyInfosysSoftware Engineer

13. Lemonade Change (LeetCode)

Model answer

The task

Given customers’ bill denominations in payment order, determine whether each customer can receive exact change when each lemonade costs $5. Begin with no change in the register.

Key idea

Track the number of $5 and $10 bills. For a $10 bill, give one $5 bill; for a $20 bill, use a $10 and a $5 if possible, preserving $5 bills for later.

Approach

  1. Initialize counts of $5 and $10 bills to zero.
  2. For a $5 bill, add it to the register.
  3. For a $10 bill, require and use one $5 bill, then record the $10.
  4. For a $20 bill, prefer one $10 and one $5; otherwise use three $5 bills.
  5. Return False if any required change is unavailable; otherwise return True.
from typing import List

class Solution:
    def lemonadeChange(self, bills: List[int]) -> bool:
        fives = 0
        tens = 0

        for bill in bills:
            if bill == 5:
                fives += 1
            elif bill == 10:
                if fives == 0:
                    return False
                fives -= 1
                tens += 1
            else:  # bill == 20
                # Prefer using a $10 and a $5, preserving smaller bills.
                if tens > 0 and fives > 0:
                    tens -= 1
                    fives -= 1
                elif fives >= 3:
                    fives -= 3
                else:
                    return False

        return True

Complexity:

  • Time: O(n), where n is the number of customers.
  • Space: O(1), using only two counters.

Common follow-ups

  • What if the price changes? Track received denominations and find a valid change combination for the new price.
  • Why prefer a $10 plus a $5 over three $5 bills? Smaller bills are more flexible for future transactions.
  • What if bills arrive concurrently? Protect the register’s counts and each payment update with a lock.
CodingEasyInfosysSoftware Engineer

14. Merge Strings Alternately (LeetCode)

Model answer

The task

Combine two strings by taking one character from each in turn, starting with the first string. If one string runs out first, add the rest of the other string unchanged.

Key idea

Keep an index for each string and append characters while both indices are valid. Then append whichever suffix remains, if any.

Approach

  1. Initialize two indices at the start of the strings and an empty list of output characters.
  2. While both indices are within their strings, append one character from each and advance both indices.
  3. Append any unprocessed suffix from the first string.
  4. Append any unprocessed suffix from the second string.
  5. Join the output characters into the returned string.
class Solution:
    def mergeAlternately(self, word1: str, word2: str) -> str:
        i = 0
        j = 0
        merged = []

        # Interleave characters while both strings have characters left.
        while i < len(word1) and j < len(word2):
            merged.append(word1[i])
            merged.append(word2[j])
            i += 1
            j += 1

        # Preserve any remaining characters from either string.
        merged.extend(word1[i:])
        merged.extend(word2[j:])

        return "".join(merged)

Complexity:

  • Time: O(m + n), where m and n are the string lengths; every character is processed once.
  • Space: O(m + n) for the resulting character list and returned string.

Common follow-ups

  • What if the second string should be taken first? Swap which character is appended first in each loop iteration.
  • Can the result be built without slicing the leftover suffix? Append remaining characters in a loop, avoiding temporary slice strings.
  • What if there are many strings to interleave? Track an index per string and repeatedly append the next available character from each string in order.
CodingEasyInfosysSoftware Engineer

15. Reverse String II (LeetCode)

Model answer

The task

Given a string and a positive integer k, reverse the first k characters in each consecutive block of 2k characters. If the final block is shorter than k, reverse the entire block.

Key idea

Process the string in steps of 2k. In each step, reverse only the segment from the current position through at most the next k characters. Converting to a list allows the characters to be swapped in place.

Approach

  1. Convert the string to a list of characters.
  2. Visit starting indices 0, 2k, 4k, ....
  3. For each index, set the reversal boundary to at most k characters ahead, or the end of the string.
  4. Swap characters inward from both ends of that segment.
  5. Join the list back into a string.
class Solution:
    def reverseStr(self, s: str, k: int) -> str:
        chars = list(s)
        n = len(chars)

        # Each segment starts every 2k characters.
        for start in range(0, n, 2 * k):
            left = start
            right = min(start + k, n) - 1

            # Reverse the first k characters of this segment,
            # or all remaining characters if fewer than k remain.
            while left < right:
                chars[left], chars[right] = chars[right], chars[left]
                left += 1
                right -= 1

        return "".join(chars)

Complexity:

  • Time: O(n), since each character is visited only a constant number of times.
  • Space: O(n), for the character list used to build the result.

Common follow-ups

  • How would you handle a mutable character array? Swap directly in the array and avoid creating a separate list.
  • What if the reversal length varies by block? Compute each block’s reversal length before swapping.
  • What edge cases should be checked? Empty strings, k = 1, and a final block shorter than k.
CodingEasyInfosysSoftware Engineer

16. Valid Parentheses (LeetCode)

Model answer

The task

Determine whether a string of opening and closing round, square, and curly brackets is correctly nested and matched. Return a boolean.

Key idea

A closing bracket must match the most recent unmatched opening bracket. A stack captures that order: push openings, and check each closing bracket against the stack’s top.

Approach

  1. Return False if the string has odd length.
  2. Map each closing bracket to its matching opening bracket.
  3. Scan the string from left to right.
  4. Push opening brackets onto the stack.
  5. For a closing bracket, return False if the stack is empty or its top does not match; otherwise pop.
  6. Return True only if the stack is empty after the scan.
class Solution:
    def isValid(self, s: str) -> bool:
        pairs = {")": "(", "]": "[", "}": "{"}
        openings = set(pairs.values())
        stack = []

        for char in s:
            if char in openings:
                stack.append(char)
            else:
                # A closing bracket must match the latest unmatched opening.
                if not stack or stack[-1] != pairs.get(char):
                    return False
                stack.pop()

        # Unmatched opening brackets make the sequence invalid.
        return not stack

Complexity:

  • Time: O(n), where n is the string length; each character is processed once.
  • Space: O(n) in the worst case, when all characters are opening brackets.

Common follow-ups

  • How would you support additional bracket types? Add their matching pairs to the map.
  • Can you stop early? Yes; return False as soon as a closing bracket mismatches or has no opening bracket.
  • What if the input includes non-bracket characters? Define how to handle them, then either ignore them or reject them during the scan.
CodingEasyInfosysSoftware Engineer

17. Maximize Sum Of Array After K Negations (LeetCode)

Model answer

The task

Given an integer array and a number of operations, choose an element and negate it on each operation. Return the largest sum possible after exactly that many operations.

Key idea

Negating a negative number increases the sum, so handle negative values first. If an odd number of operations remains, negate the element with the smallest absolute value; any extra pairs of negations cancel out.

Approach

  1. Sort the array so its negative values come first.
  2. Negate negative values while operations remain.
  3. If the remaining operation count is odd, negate the value with the smallest absolute value.
  4. Return the sum.
from typing import List

class Solution:
    def largestSumAfterKNegations(self, nums: List[int], k: int) -> int:
        nums.sort()

        # Use operations on negative values first.
        for i in range(len(nums)):
            if k == 0 or nums[i] >= 0:
                break
            nums[i] = -nums[i]
            k -= 1

        # An odd leftover means one value must be negated once more.
        if k % 2 == 1:
            smallest_index = min(range(len(nums)), key=lambda i: nums[i])
            nums[smallest_index] = -nums[smallest_index]

        return sum(nums)

Complexity:

  • Time: O(n log n) for sorting.
  • Space: O(n) for Python’s sort implementation; the input list is sorted in place.

Common follow-ups

  • What if the array contains zero? A leftover odd negation can be spent on zero with no change to the sum.
  • Can you avoid sorting? Track the smallest absolute value and process negatives using a min-heap, typically O(n + k log n).
  • What if each element can be negated at most once? Then the leftover-operation parity rule may not apply; choose a valid subset of distinct elements instead.
CodingEasyInfosysSoftware Engineer

18. Binary Search (LeetCode)

Model answer

The task

Given an array sorted in ascending order and a target value, return the target’s index if it is present; otherwise return -1.

Key idea

Use binary search to repeatedly discard the half of the remaining range that cannot contain the target. Because the array is sorted, each comparison tells us which half to keep.

Approach

  1. Set left and right to the first and last valid indices.
  2. While the range is nonempty, choose its midpoint.
  3. If the midpoint value matches the target, return its index.
  4. If it is smaller, continue in the right half; otherwise, continue in the left half.
  5. If the range becomes empty, return -1.
class Solution:
    def search(self, nums: list[int], target: int) -> int:
        left = 0
        right = len(nums) - 1

        while left <= right:
            # This form avoids overflowing fixed-width integer types.
            mid = left + (right - left) // 2

            if nums[mid] == target:
                return mid
            if nums[mid] < target:
                left = mid + 1
            else:
                right = mid - 1

        return -1

Complexity:

  • Time: O(log n), since each iteration halves the search range.
  • Space: O(1), since the search uses only a fixed number of variables.

Common follow-ups

  • How would you find the first occurrence when duplicates are allowed? Record a match and keep searching the left half.
  • How would you find the insertion position for a missing target? Return left after the loop; it is the first index whose value is not less than the target.
  • What if the sorted array is rotated? Use a modified binary search that identifies which half is sorted, then checks whether the target lies in that half.
CodingEasyInfosysSoftware Engineer

19. Split a String in Balanced Strings (LeetCode)

Model answer

The task

Given a string made of L and R, divide it into as many contiguous balanced pieces as possible. A piece is balanced when it contains the same number of each character.

Key idea

Track the difference between the number of Ls and Rs seen in the current piece. Whenever that difference returns to zero, the current prefix is balanced, so we can safely finish a piece and start counting the next one.

Approach

  1. Initialize a balance counter and a piece counter to zero.
  2. Scan the string from left to right.
  3. Add one for L and subtract one for R.
  4. When the balance is zero, increment the piece counter. This greedy cut is safe because no earlier prefix of the current piece was balanced.
  5. Return the number of pieces.
class Solution:
    def balancedStringSplit(self, s: str) -> int:
        balance = 0
        pieces = 0

        for char in s:
            if char == "L":
                balance += 1
            else:  # char == "R"
                balance -= 1

            # A zero balance means this prefix has equal counts.
            if balance == 0:
                pieces += 1

        return pieces

Complexity:

  • Time: O(n), where n is the length of the string; each character is processed once.
  • Space: O(1), using only a few counters.

Common follow-ups

  • What if the input can contain other characters? Define how those characters contribute to balance, or reject invalid input.
  • Can the balanced pieces be returned, rather than just counted? Record the start index whenever the balance returns to zero.
  • What if the string is streamed? Maintain the balance and piece count as characters arrive; the completed count is available at each balanced boundary.
CodingEasyInfosysSoftware Engineer

20. Search Insert Position (LeetCode)

Model answer

The task

Given a sorted array of distinct integers and a target, return its index if present. Otherwise, return the index where it should be inserted to keep the array sorted.

Key idea

Use binary search to find the first position whose value is at least the target. That position is both the target’s index when it exists and its insertion point otherwise.

Approach

  1. Set left to the start of the array and right to its length, treating right as an exclusive bound.
  2. While the search interval is nonempty, inspect its midpoint.
  3. If the midpoint value is less than the target, search to its right.
  4. Otherwise, search the portion including the midpoint and to its left.
  5. When the interval is empty, left is the answer. It can equal the array length if the target belongs at the end.
class Solution:
    def searchInsert(self, nums: list[int], target: int) -> int:
        # Find the first index whose value is at least target.
        left, right = 0, len(nums)

        while left < right:
            mid = left + (right - left) // 2

            if nums[mid] < target:
                left = mid + 1
            else:
                right = mid

        return left

Complexity:

  • Time: O(log n), since each step halves the search interval.
  • Space: O(1), using only a fixed number of variables.

Common follow-ups

  • What if the array is empty? The result is 0, which is the correct insertion position.
  • What if duplicates are allowed? This algorithm returns the first position containing the target, or where it should first be inserted.
  • How would you find the last position of a target? Use a binary search for the first value greater than the target, then subtract one.

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