How do I practice coding and algorithm questions?

Use PracHub's coding console to write, test, and debug your solutions in Python or JavaScript. View hints, test against sample inputs, and compare with official solutions.

What difficulty level is this coding 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

Company: Salesforce

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Take-home Project

## Problem 1: Flag duplicates on the left and right You are given an integer array `nums` of length `n`. For each index `i`, determine: 1. **Left-duplicate:** whether `nums[i]` has appeared in any index `< i`. 2. **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`.

Quick Answer: 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.

Flag duplicates on the left and right

You are given an integer array `nums` of length `n`. For each index `i`, determine two things: 1. **Left-duplicate:** whether `nums[i]` has already appeared at some index `< i`. 2. **Right-duplicate:** whether `nums[i]` appears again at some index `> i`. Build 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 the pair `[left, right]`. **Example** - Input: `nums = [5, 1, 5, 2, 1]` - `left = "00101"` — the second `5` (index 2) and the second `1` (index 4) have each appeared earlier. - `right = "11000"` — index 0's `5` recurs later (at index 2) and index 1's `1` recurs later (at index 4); the remaining values never recur to their right. > Note: an earlier draft of this prompt listed `right = "10110"`, but that is inconsistent with the definition above ("appears at any index `> i`"). The definition-correct answer is `"11000"`. **Constraints:** `1 ≤ n ≤ 2·10^5`, each `nums[i]` fits in a 32-bit signed integer.

Constraints

1 ≤ n ≤ 2·10^5
Each nums[i] fits in a 32-bit signed integer
Output strings have exactly length n, characters only '0' or '1'

Examples

Input: ([5, 1, 5, 2, 1],)

Expected Output: ["00101", "11000"]

Explanation: Left: indices 2 and 4 repeat an earlier value. Right: index 0's 5 recurs at 2, index 1's 1 recurs at 4; nothing else recurs to its right.

Input: ([7],)

Expected Output: ["0", "0"]

Explanation: Single element: no duplicates on either side.

Input: ([3, 3, 3],)

Expected Output: ["011", "110"]

Explanation: left: positions 1,2 saw a 3 earlier; right: positions 0,1 see a 3 later.

Input: ([1, 2, 3, 4],)

Expected Output: ["0000", "0000"]

Explanation: All distinct, so no duplicates in either direction.

Input: ([-1, -1, 0, 0, -1],)

Expected Output: ["01011", "11100"]

Explanation: Negatives and zeros handled like any other value; left and right computed by the same set logic.

Input: ([4, 4],)

Expected Output: ["01", "10"]

Explanation: Index 1 saw a 4 before; index 0 sees a 4 after.

Hints

A single left-to-right pass with a hash set of already-seen values fills `left`: before inserting nums[i], check whether it is already in the set.
Symmetrically, a right-to-left pass with a fresh hash set fills `right`: before inserting nums[i], check whether it is already in the set.
Two linear passes give O(n) time; no nested loops needed.

Synchronous "01" → "10" replacement until stable

You are given a binary string `s` containing only `'0'` and `'1'`. Each second, **every** occurrence of the substring `"01"` is replaced **simultaneously** by `"10"`. The update is synchronous: all replacements within one second use the string as it was at the start of that second, so overlapping/adjacent replacements in the same second do not chain. Repeat until the string contains no `"01"` (i.e. it becomes all `1`s followed by all `0`s). Return the number of seconds the process takes. **Example** - Input: `s = "010110"` - Step 1: `"010110"` → `"101010"` - Step 2: `"101010"` → `"110100"` - Step 3: `"110100"` → `"111000"` (stable) - Output: `3` A naive step-by-step simulation is O(n²) in the worst case (e.g. `"000…0111…1"`). The intended O(n) solution reasons about how each `'1'` is delayed ("blocked") by the `'1'`s ahead of it. **Constraints:** `1 ≤ |s| ≤ 2·10^5`.

Constraints

1 ≤ |s| ≤ 2·10^5
s contains only the characters '0' and '1'
Return 0 when s is already stable (no "01" substring)

Examples

Input: ("010110",)

Expected Output: 3

Explanation: 010110 -> 101010 -> 110100 -> 111000; 3 synchronous steps.

Input: ("",)

Expected Output: 0

Explanation: Empty string is already stable.

Input: ("0",)

Expected Output: 0

Explanation: No '1', nothing to move.

Input: ("1",)

Expected Output: 0

Explanation: No '0' after the '1'; already stable.

Input: ("01",)

Expected Output: 1

Explanation: One step turns 01 into 10.

Input: ("0011",)

Expected Output: 3

Explanation: 0011->0101->1010->1100; the trailing '1's queue up behind the leading zeros, taking 3 steps.

Input: ("1100",)

Expected Output: 0

Explanation: Already in stable (1s then 0s) form.

Input: ("0001",)

Expected Output: 3

Explanation: A single '1' behind three zeros must hop each, one per second.

Input: ("010101",)

Expected Output: 3

Explanation: Interleaved pattern stabilizes to 111000 in 3 synchronous steps.

Input: ("00110",)

Expected Output: 3

Explanation: Blocking between the two '1's plus the leading zeros yields 3 steps.

Hints

Think of each '1' moving left past the '0's in front of it. A '1' with no '0' before it never moves and contributes 0.
Scan left to right tracking the number of zeros seen so far. When you reach a '1' that has at least one zero before it, its finish time is at least `zeros` (it must hop over that many zeros) but also at least one more than the previous '1''s finish time, because the previous '1' can block it for a second.
So maintain `t = max(t + 1, zeros)` at each '1' (only when zeros > 0); the answer is the final `t`. This is O(n) and avoids the O(n²) simulation blowup.

Quick Overview

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.