Quick Overview

This assessment evaluates algorithmic proficiency in time-based counting and synchronous string transformation, covering competencies in windowed aggregation, array and binary-string processing, simulation of concurrent swaps, and algorithmic complexity analysis.

Solve Time-Window and Binary Swap Problems

Company: SoFi

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: easy

Interview Round: Technical Screen

This online assessment contained two coding problems: 1. **Maximum requests in a time window** You are given a non-decreasing integer array `requestTimes`, where `requestTimes[i]` is the second at which the `i`-th request arrives, and an integer `windowSize`. Return the maximum number of requests that occur within any inclusive time interval of length `windowSize` seconds. In other words, find the largest number of elements that can fit inside some interval `[t, t + windowSize]`. 2. **Simultaneous swaps in a binary string** You are given a binary string `s` consisting only of `'0'` and `'1'`. Every second, all adjacent occurrences of `'01'` are swapped simultaneously to become `'10'`. Repeat this process until the string no longer contains `'01'`. Return the number of seconds required. Example: `s = "001011"` transforms as follows: `001011 -> 010101 -> 101010 -> 110100 -> 111000` So the answer is `4` seconds.

Quick Answer: This assessment evaluates algorithmic proficiency in time-based counting and synchronous string transformation, covering competencies in windowed aggregation, array and binary-string processing, simulation of concurrent swaps, and algorithmic complexity analysis.

Part 1: Maximum Requests in a Time Window

You are given a non-decreasing integer array `requestTimes`, where `requestTimes[i]` is the second at which the `i`-th request arrives, and a non-negative integer `windowSize`. Return the maximum number of requests that occur within any inclusive time interval of length `windowSize` seconds. In other words, find the largest number of values that can fit inside some interval `[t, t + windowSize]`. Because the interval is inclusive, requests at both endpoints count.

Constraints

  • `0 <= len(requestTimes) <= 200000`
  • `0 <= requestTimes[i] <= 10^9`
  • `requestTimes` is sorted in non-decreasing order
  • `0 <= windowSize <= 10^9`

Examples

Input: ([1, 1, 2, 3, 7, 8], 2)

Expected Output: 4

Explanation: The interval `[1, 3]` contains `1, 1, 2, 3`, so the answer is 4.

Input: ([], 5)

Expected Output: 0

Explanation: There are no requests, so the maximum count is 0.

Hints

  1. Since the array is already sorted, try maintaining a valid range with two pointers.
  2. For a fixed right endpoint, move the left pointer forward until `requestTimes[right] - requestTimes[left] <= windowSize`.

Part 2: Seconds to Eliminate All '01' Pairs

You are given a binary string `s` containing only `'0'` and `'1'`. Every second, all adjacent occurrences of `'01'` are swapped simultaneously, turning each such pair into `'10'`. This process repeats until the string no longer contains `'01'`. Return the number of seconds required. Example: `001011 -> 010101 -> 101010 -> 110100 -> 111000` So the answer is `4`.

Constraints

  • `0 <= len(s) <= 200000`
  • `s[i]` is either `'0'` or `'1'`

Examples

Input: ("001011",)

Expected Output: 4

Explanation: Following the simultaneous swaps gives 4 steps before the string becomes `111000`.

Input: ("",)

Expected Output: 0

Explanation: An empty string has no `'01'` pairs.

Hints

  1. A direct simulation works, but can be too slow for long strings.
  2. Track how many zeros have appeared before each `'1'`. A `'1'` may need to wait not only for zeros, but also for earlier `'1'` characters moving through the same zeros.

Loading coding console...