9 real Publicis Sapient interview questions with full model answers — Coding. Drawn from the same verified bank ChannelPulse drills from (9 Publicis Sapient questions in total).
9 Publicis Sapient questions in the bank
1 categories covered
1 roles: Software Engineer
CodingEasyPublicis SapientSoftware Engineer
1. 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
Return False if the string has odd length.
Map each closing bracket to its matching opening bracket.
Scan the string from left to right.
Push opening brackets onto the stack.
For a closing bracket, return False if the stack is empty or its top does not match; otherwise pop.
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.
CodingEasyPublicis SapientSoftware Engineer
2. 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
If the list is empty, return an empty string.
Scan each character of the first string from left to right.
For each position, compare that character with the character at the same position in every other string.
If a string is too short or a character differs, return the matching prefix before that position.
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.
CodingMediumPublicis SapientSoftware Engineer
3. Largest Palindromic Number (LeetCode)
Model answer
The task
Rearrange the supplied digit string into the numerically largest palindrome possible, using each digit no more times than it appears. Return the result as a string, without unnecessary leading zeros.
Key idea
A palindrome is determined by its left half and optional center digit. Use as many pairs as possible, placing larger digits first; if there is a choice of center digit, use the largest available one.
Approach
Count how many times each digit occurs.
Build the left half from digits 9 down to 0, taking count // 2 copies of each.
Do not start the left half with zeros; skip zero pairs if no nonzero pair has been used.
Choose the largest digit with an odd count as the center.
If both halves are empty, return "0"; otherwise mirror the left half around the center.
from collections import Counter
class Solution:
def largestPalindromic(self, num: str) -> str:
counts = Counter(num)
left_parts = []
# Build the largest possible left half.
for digit in range(9, -1, -1):
pairs = counts[str(digit)] // 2
# Leading zeros would make the number smaller.
if digit == 0 and not left_parts:
continue
if pairs:
left_parts.append(str(digit) * pairs)
left = "".join(left_parts)
# The center can use any digit with an odd remaining count.
center = ""
for digit in range(9, -1, -1):
if counts[str(digit)] % 2:
center = str(digit)
break
# No nonzero digits can form a palindrome larger than zero.
if not left and not center:
return "0"
return left + center + left[::-1]
Complexity:
Time: O(n), to count the digits and construct the result.
Space: O(n), for the output; the digit counts use O(1) space.
Common follow-ups
What if the input is extremely long? Build the halves in chunks and stream them if the output need not be held in memory.
Why skip zero pairs only when the left half is empty? Once a nonzero leading digit exists, zeros can safely appear later in the half.
What if no digits can be paired? Return the largest available single digit, or "0" if the only possible result is zero.
CodingMediumPublicis SapientSoftware Engineer
4. Longest Repeating Character Replacement (LeetCode)
Model answer
The task
Find the length of the longest substring that can be made entirely of one repeated character by changing at most k characters.
Key idea
Use a sliding window and track the most frequent character in it. The number of replacements needed is the window length minus that frequency, so shrink the window whenever this exceeds k.
Approach
Keep a frequency count for characters in the current window.
Expand the right edge one character at a time and update the highest frequency seen.
If the window would need more than k replacements, move its left edge forward.
Record the largest window length.
The maximum frequency is intentionally not recomputed when the window shrinks. It may be stale, but this still gives the correct maximum length: the window only stays large when its length is supported by a frequency seen in a previously valid window.
class Solution:
def characterReplacement(self, s: str, k: int) -> int:
counts = {}
left = 0
max_frequency = 0
longest = 0
for right, char in enumerate(s):
counts[char] = counts.get(char, 0) + 1
max_frequency = max(max_frequency, counts[char])
# Shrink until the window can be made uniform with at most k changes.
if (right - left + 1) - max_frequency > k:
counts[s[left]] -= 1
left += 1
longest = max(longest, right - left + 1)
return longest
Complexity:
Time: O(n), where n is the string length; each pointer moves at most n times.
Space: O(1), since the frequency map has at most 26 entries for uppercase English letters.
Common follow-ups
What if the string can contain arbitrary Unicode characters? Use a dictionary for counts; the space then depends on the number of distinct characters.
Can the method return the substring as well as its length? Store the best window’s start and end indices whenever the best length increases.
What if replacements have different costs? Track the minimum cost to make the window uniform and shrink while that cost exceeds the budget.
CodingMediumPublicis SapientSoftware Engineer
5. Minimum Sideway Jumps (LeetCode)
Model answer
The task
Find the fewest times a frog must switch lanes to travel along a path from its starting point to the end, without occupying a lane blocked at any point.
Key idea
Track the minimum side jumps needed to reach each of the three lanes at the current position. When a lane is blocked, invalidate it, then allow a single side jump from the cheapest available lane to any other open lane.
Approach
Initialize the costs at the starting point: the middle lane costs zero jumps, and each other lane costs one.
Move through the path one position at a time.
Mark the lane blocked at the current position as unreachable.
Find the cheapest reachable open lane; update each open lane with the option of jumping from it.
Return the cheapest cost among the three lanes.
from typing import List
class Solution:
def minSideJumps(self, obstacles: List[int]) -> int:
# Costs for lanes 1, 2, and 3 at the starting position.
dp = [1, 0, 1]
infinity = float("inf")
for position in range(1, len(obstacles)):
blocked_lane = obstacles[position] - 1
# The frog cannot occupy the lane blocked at this position.
if blocked_lane >= 0:
dp[blocked_lane] = infinity
# A side jump can be made from the cheapest currently open lane.
cheapest_open = min(dp)
for lane in range(3):
if lane != blocked_lane:
dp[lane] = min(dp[lane], cheapest_open + 1)
return int(min(dp))
Complexity:
Time: O(n), processing each position with a constant amount of work.
Space: O(1), storing costs for only three lanes.
Common follow-ups
What if there are more than three lanes? Track one cost per lane and update all open lanes from the cheapest available cost.
What if side jumps have different costs? Use the minimum transition cost from each reachable lane instead of adding one.
How can you return the actual lane sequence? Store predecessor choices for each position and lane, then backtrack from the cheapest final lane.
CodingMediumPublicis SapientSoftware Engineer
6. Container With Most Water (LeetCode)
Model answer
The task
Given nonnegative heights arranged along a line, choose two positions to form a container with the greatest possible area. Its area is the distance between the positions multiplied by the shorter of their two heights.
Key idea
Start with the widest possible pair, at the two ends. The shorter side limits the area, so moving the taller side inward cannot improve that limiting height and only reduces the width. Move the shorter side instead, hoping to find a taller boundary.
Approach
Set pointers to the first and last positions.
Compute the area using their distance and the shorter height; update the best area.
Move the pointer at the shorter height inward by one position.
Repeat until the pointers meet.
Return the greatest area seen.
from typing import List
class Solution:
def maxArea(self, height: List[int]) -> int:
left = 0
right = len(height) - 1
best_area = 0
while left < right:
width = right - left
limiting_height = min(height[left], height[right])
best_area = max(best_area, width * limiting_height)
# The shorter side limits this container's area.
# Moving the taller side inward cannot improve that limit.
if height[left] <= height[right]:
left += 1
else:
right -= 1
return best_area
Complexity:
Time: O(n), because each pointer moves inward at most n times.
Space: O(1), since only a few variables are used.
Common follow-ups
What if heights can be negative? A negative height does not describe a valid container; clarify the input rules, or treat invalid heights as unusable.
Why is it safe to discard the shorter side? With the same shorter boundary, every inward pair has less width, so it cannot produce a larger area.
Can this be done with extra memory? Not usefully for this objective; the two-pointer scan already processes the candidates in linear time with constant space.
CodingMediumPublicis SapientSoftware Engineer
7. Longest Substring Without Repeating Characters (LeetCode)
Model answer
The task
Find the length of the longest contiguous section of a string in which every character appears at most once.
Key idea
Maintain a sliding window with no repeated characters. When a character repeats within the window, move the left edge just past its previous occurrence.
Approach
Track each character’s most recent index in a dictionary.
Keep left as the window’s starting index and best as its longest length so far.
For each character, move left forward if its previous occurrence is inside the current window.
Record the character’s current index and update best using the window length.
class Solution:
def lengthOfLongestSubstring(self, s: str) -> int:
last_seen = {}
left = 0
best = 0
for right, char in enumerate(s):
# Skip past a repeated character if it is in the current window.
if char in last_seen and last_seen[char] >= left:
left = last_seen[char] + 1
last_seen[char] = right
best = max(best, right - left + 1)
return best
Complexity:
Time: O(n), because each character is processed once.
Space: O(k), where k is the number of distinct characters encountered.
Common follow-ups
Return the substring itself: store the best window’s start and end indices when updating best.
Handle a stream of characters: keep the same window state and process each arriving character incrementally.
Use a fixed-size character set: replace the dictionary with an array of last-seen indices.
CodingHardPublicis SapientSoftware Engineer
8. Trapping Rain Water (LeetCode)
Model answer
The task
Given an array of nonnegative bar heights, compute how much water remains trapped between the bars after rainfall. Each bar has unit width.
Key idea
Water above a position is limited by the shorter of the tallest bars to its left and right. With two pointers, process the side whose current height is lower: its boundary already determines the maximum water that position can hold, so no arrays of prefix and suffix maxima are needed.
Approach
Start pointers at both ends and track the greatest height seen from each side.
While the pointers have not crossed, compare their current heights.
If the left height is lower, update the left maximum and add any water above the left bar, then advance the left pointer.
Otherwise, do the symmetric operation on the right.
Return the accumulated water.
from typing import List
class Solution:
def trap(self, height: List[int]) -> int:
left, right = 0, len(height) - 1
left_max = right_max = 0
water = 0
while left < right:
if height[left] < height[right]:
# The right side is tall enough that the left maximum
# determines the water level at this position.
left_max = max(left_max, height[left])
water += left_max - height[left]
left += 1
else:
# Symmetrically, the right maximum determines this level.
right_max = max(right_max, height[right])
water += right_max - height[right]
right -= 1
return water
Complexity:
Time: O(n), because each pointer moves across the array at most once.
Space: O(1), because the algorithm uses only a fixed number of variables.
Common follow-ups
How can this be solved with dynamic programming? Precompute the maximum height to each position from the left and right, then sum the trapped water at each position.
How can a monotonic stack solve it? Keep indices of decreasing bar heights; when a taller bar arrives, pop a basin bottom and calculate the bounded layer.
What if bars have different widths? Track each bar’s width and use area rather than unit-width contributions; the boundary logic must account for the resulting horizontal spans.
CodingHardPublicis SapientSoftware Engineer
9. Sum of Subsequence Widths (LeetCode)
Model answer
The task
For an integer array, add the difference between the largest and smallest values for every non-empty subsequence. Return the total modulo \(10^9+7\).
Key idea
Sort the values. At sorted position i, the value is the maximum in \(2^i\) subsequences and the minimum in \(2^{n-1-i}\) subsequences. Its net contribution is therefore its value times the difference between those counts.
Approach
Sort the array.
For each position, compute the number of subsequences where its value is the maximum.
Compute the number where it is the minimum.
Add the value’s net contribution, reducing modulo \(10^9+7\).
Return the accumulated total.
class Solution:
def sumSubseqWidths(self, nums: list[int]) -> int:
mod = 10**9 + 7
nums.sort()
n = len(nums)
total = 0
for i, value in enumerate(nums):
max_count = pow(2, i, mod)
min_count = pow(2, n - 1 - i, mod)
total = (total + value * (max_count - min_count)) % mod
return total
Complexity:
Time: O(n log n) for sorting; modular exponentiation adds O(n log n) in total.
Space: O(n) for Python’s sorting implementation.
Common follow-ups
What if the array contains duplicates? Treat positions as distinct; the contribution counts remain valid.
Can the exponentiations be made linear-time overall? Precompute powers of two iteratively, then use them for each position.
What if the input is empty? The loop does not run, so the result is 0.
Can this avoid sorting? In general, the maximum and minimum roles depend on value order, so sorting is needed for this approach.
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.