Solve array duplicate flags and binary swaps

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.

Q: 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.

Q: What difficulty level is this interview question?

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

Q: What role is this question designed for?

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

Question

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

Comments (0)