Publicis Sapient Coding Questions: Three Patterns with Worked Solutions

Recognising code is easier than explaining why it works. Practise three patterns through Java methods, exact traces, invariants and edge cases before your next coding assessment.

KnowledgeGate Team

Exam prep & CS education

Updated 17 Nov 20265 min read
Publicis Sapient Coding Questions: Three Patterns with Worked Solutions

You recognise a familiar solution, but explaining why it works under interview pressure is harder. These three methods give you traces, complexity checks and tests to practise that explanation. These are original practice examples for Publicis Sapient preparation, not verified previous questions, an official paper or a forecast of the next assessment.

1. Turn a coding question into an invariant

First restate the required output. Confirm constraints, describe brute force, then identify the state worth retaining. An invariant is a fact that stays true after each iteration. It connects your code to a reason the answer is correct.

Required result

Pattern

Invariant

Pair with target sum

Complement lookup

Map contains only earlier indices

Longest substring without repeats

Sliding window

Current window has unique characters

Overlapping ranges

Sort and merge

Completed ranges cannot overlap later input

Use these as recognition cues in your coding and DSA preparation. The examples assume non-null, in-memory input and use zero-based indices. Submitted input and output must follow the actual prompt: returning indices and printing values are different requirements.

2. Complement lookup: return two distinct indices

Given int[] a = {4, 7, 1, 9} and target 10, return any valid pair of distinct indices, here [2,3], or [-1,-1] if none exists. Values and target lie between -1,000,000 and 1,000,000, so int subtraction is safe. Brute force checks pairs in O(n²) time with O(1) auxiliary space.

Instead, remember earlier values in a map. For each value x, search for target - x before inserting x.

java
static int[] twoSum(int[] a, int target) {
    java.util.Map<Integer, Integer> seen = new java.util.HashMap<>();
    for (int i = 0; i < a.length; i++) {
        int need = target - a[i];
        Integer j = seen.get(need);
        if (j != null) return new int[]{j, i};
        seen.put(a[i], i);
    }
    return new int[]{-1, -1};
}

Trace the subtraction and lookup:

i

x

Needed

Action

0

4

10 − 4 = 6

Miss; insert 4→0

1

7

10 − 7 = 3

Miss; insert 7→1

2

1

10 − 1 = 9

Miss; insert 1→2

3

9

10 − 9 = 1

Hit index 2; return [2,3]

Indexed array values and complement lookups identify indices 2 and 3, whose values sum to the target.

The complement belongs to an earlier, distinct index. Every valid pair is detected when its second member arrives, unless another valid pair has already been returned. Expected time is O(n) under normal hashing assumptions; space is O(n). Continue with HashMap and HashSet practice.

Test target 10: [5,5] returns [0,1]; [5] and [] each return [-1,-1].

3. Sliding window: keep the longest duplicate-free substring

For lowercase English input "abba", return length 2. A substring is contiguous; a subsequence may skip positions. Store each character's last index and keep a window from left through right.

java
static int longestUnique(String s) {
    java.util.Map<Character, Integer> last = new java.util.HashMap<>();
    int left = 0, best = 0;
    for (int right = 0; right < s.length(); right++) {
        char c = s.charAt(right);
        Integer previous = last.get(c);
        if (previous != null) left = Math.max(left, previous + 1);
        last.put(c, right);
        best = Math.max(best, right - left + 1);
    }
    return best;
}

right

Character

left

Window

Length

best

0

a

0

a

0 − 0 + 1 = 1

1

1

b

0

ab

1 − 0 + 1 = 2

2

2

b

2

b

2 − 2 + 1 = 1

2

3

a

2

ba

3 − 2 + 1 = 2

2

Sliding-window rows show the window shifting across repeated characters while the best unique length remains 2.

At the final a, its previous index is 0. Moving left back to 1 would include bba, which repeats b. Taking the maximum preserves uniqueness. Each step gives the longest valid window ending there; best retains the largest length overall.

Expected time is O(n), with O(min(n, alphabet size)) map entries. Test "" → 0, "aaaa" → 1, and "abc" → 3. Broader Unicode support needs a separately agreed definition of character.

4. Sort and merge: combine overlapping intervals

Take closed intervals [[6,8],[1,3],[2,4],[8,10]], each with start ≤ end. Touching closed intervals overlap. Sort by start using Java's Integer.compare(x[0], y[0]), giving [[1,3],[2,4],[6,8],[8,10]].

  1. Start with [1,3].

  2. Since 2 ≤ 3, merge [2,4] into [1,4].

  3. Since 6 > 4, emit [1,4]; reset current to [6,8].

  4. Since 8 ≤ 8, extend current to [6,10].

  5. Emit the final current interval. Result: [[1,4],[6,10]].

The pseudocode is:

Code
if intervals is empty: return []
sort intervals by start
result = []
current = copy of first interval
for each remaining interval next:
    if next.start <= current.end:
        current.end = max(current.end, next.end)
    else:
        append current to result
        current = copy of next
append current to result
return result

Sorting ensures later starts cannot reach back into an emitted range. Time is O(n log n), with O(n) output storage; sorting's extra storage depends on implementation. Test [] → [] and [[1,5],[2,3]] → [[1,5]]. For different interval semantics, clarify whether touching endpoints merge.

5. Three mistakes that break otherwise correct code

  • Insert before lookup: [5], target 10, can reuse index 0. Query earlier values first.

  • Move the window boundary backwards: the last a in abba can make you count bba as length 3. Preserve left with max.

  • Forget the final append: merging inside the loop feels complete, but [6,10] disappears. Emit the remaining current interval after the loop.

Do not silently mutate input when the caller requires it preserved. Sorting intervals changes their order, so copy the input when necessary. State return semantics, empty-input behaviour and complexity aloud before declaring the solution finished.

6. How to practise explaining these patterns in an assessment

Publicis Sapient's early-career page describes its internship and graduate opportunities. It does not establish a universal coding format. Consult your role description and assessment invitation for duration, permitted languages and environment.

Try this author-designed 30-minute rehearsal, separate from any company test duration: 3 minutes to clarify and outline brute force, 15 to implement, 7 to test an adversarial case, and 5 to explain the invariant and complexity. That is 3 + 15 + 7 + 5 = 30. Use coding-round time management to practise allocating that effort.

Answer follow-ups using the worked values: lookup before insertion prevents [5] from matching itself; keeping left=2 excludes bba; sorting places [2,4] before [6,8], so [1,4] can be finalised safely.

7. Your next step: reproduce, then vary one constraint

Remember earlier values for complements. Maintain a valid window for contiguous uniqueness. Sort ranges before deciding which can be finalised.

Reproduce all three traces without looking. Then change one condition: duplicate pair values, repeated characters or endpoint overlap. Predict the answer before coding, and explain which invariant protects it.

For optional structured practice, use the DSA using Java course to organise your preparation around these skills.