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.

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.

Hints

  1. 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.
  2. 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.
  3. 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.

Hints

  1. 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.
  2. 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.
  3. 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.

Loading coding console...