How do I approach Coding & Algorithms interview questions?

Coding & Algorithms questions require understanding of core concepts and practice. PracHub provides solutions with explanations to help you master coding & algorithms interviews.

What difficulty level is this interview question?

This is a medium difficulty Coding & Algorithms question, commonly asked during Take-home Project rounds at Salesforce.

What role is this question designed for?

This question is commonly asked for Software Engineer candidates at Salesforce during technical interviews.

Solve array duplicate flags and binary swaps | Salesforce Interview Question

Q: Solve array duplicate flags and binary swaps

This question evaluates array and string algorithm skills, specifically hash-based frequency tracking for left/right duplicate detection and reasoning about synchronous substring transformations to determine stabilization time.

Problem 1: Flag duplicates on the left and right

You are given an integer array nums of length n.

For each index i, determine:

Left-duplicate: whether nums[i] has appeared in any index < i .
Right-duplicate: whether nums[i] appears in any index > i .

Construct two binary strings of length n:

left[i] = '1' if nums[i] appears in nums[0..i-1] , else '0' .
right[i] = '1' if nums[i] appears in nums[i+1..n-1] , else '0' .

Return [left, right].

Example

Input: nums = [5, 1, 5, 2, 1]
Output:
- left = "00101" (the second 5 and the second 1 have appeared on the left)
- right = "10110" (the first 5 and first 1 appear again on the right)

Constraints (typical): 1 ≤ n ≤ 2e5, nums[i] fits in 32-bit signed integer.

Problem 2: Synchronous replacement "01" → "10" until stable

You are given a binary string s (characters are only '0' and '1').

Each second, all occurrences of substring "01" are replaced simultaneously with "10".

This is a synchronous update: replacements in the same second do not affect each other.

Repeat this process until the string contains no "01".

Return the number of seconds required.

Example

Input: s = "010110"
Output: ? (compute the number of synchronous steps until no "01" remains)

Notes: A direct step-by-step simulation can be too slow for large strings; the intended solution should account for interactions where multiple '1's can “block” each other.

Constraints (typical): 1 ≤ |s| ≤ 2e5.

Problem 1: Flag duplicates on the left and right

You are given an integer array nums of length n.

For each index i, determine:

Left-duplicate: whether nums[i] has appeared in any index < i .
Right-duplicate: whether nums[i] appears in any index > i .

Construct two binary strings of length n:

left[i] = '1' if nums[i] appears in nums[0..i-1] , else '0' .
right[i] = '1' if nums[i] appears in nums[i+1..n-1] , else '0' .

Return [left, right].

Example

Input: nums = [5, 1, 5, 2, 1]
Output:
- left = "00101" (the second 5 and the second 1 have appeared on the left)
- right = "10110" (the first 5 and first 1 appear again on the right)

Constraints (typical): 1 ≤ n ≤ 2e5, nums[i] fits in 32-bit signed integer.

Problem 2: Synchronous replacement "01" → "10" until stable

You are given a binary string s (characters are only '0' and '1').

Each second, all occurrences of substring "01" are replaced simultaneously with "10".

This is a synchronous update: replacements in the same second do not affect each other.

Repeat this process until the string contains no "01".

Return the number of seconds required.

Example

Input: s = "010110"
Output: ? (compute the number of synchronous steps until no "01" remains)

Notes: A direct step-by-step simulation can be too slow for large strings; the intended solution should account for interactions where multiple '1's can “block” each other.

Constraints (typical): 1 ≤ |s| ≤ 2e5.

Solve array duplicate flags and binary swaps

Quick Overview

Problem 1: Flag duplicates on the left and right

Problem 2: Synchronous replacement "01" → "10" until stable

Submit Your Answer

Solve array duplicate flags and binary swaps

Quick Overview

Problem 1: Flag duplicates on the left and right

Problem 2: Synchronous replacement "01" → "10" until stable

Submit Your Answer