Compute max-ons and deletion indices
Company: J.P. Morgan
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: Medium
Interview Round: Technical Screen
Quick Answer: This question evaluates proficiency in array and string algorithms, specifically sliding-window and circular indexing for maximizing contiguous on-states and string comparison for identifying deletion indices, emphasizing correctness in index arithmetic and edge-case handling.
Part 1: Maximum On Computers in a Circular Block
Constraints
- 1 <= len(computers) <= 200000
- Each value in `computers` is either 0 or 1
- 1 <= k <= len(computers)
Examples
Input: ([1, 0, 1, 1, 0], 3)
Expected Output: 2
Explanation: The best length-3 circular blocks contain two `1`s, such as [1, 0, 1] or [0, 1, 1].
Input: ([1, 1, 0, 0, 1], 4)
Expected Output: 3
Explanation: A wrap-around block [0, 1, 1, 1] contains three on computers.
Input: ([0, 0, 0], 2)
Expected Output: 0
Explanation: Every block contains only off computers.
Input: ([1, 0, 1, 1], 4)
Expected Output: 3
Explanation: When `k` equals the array length, every window covers all computers, so the answer is the total number of `1`s.
Input: ([1], 1)
Expected Output: 1
Explanation: Single-element edge case.
Solution
def solution(computers, k):
n = len(computers)
if n == 0 or k == 0:
return 0
window = sum(computers[:k])
best = window
for start in range(1, n):
window -= computers[start - 1]
window += computers[(start + k - 1) % n]
if window > best:
best = window
return best
Time complexity: O(n). Space complexity: O(1).
Hints
- Try computing the number of `1`s in one window of size `k`, then slide the window one step at a time.
- Because the array is circular, use modulo indexing when adding the new element that enters the window.
Part 2: Indices Whose Deletion Produces the Target String
Constraints
- 1 <= len(s1) <= 200000
- len(s2) = len(s1) - 1
- `s1` and `s2` consist of lowercase English letters
Examples
Input: ("abc", "ac")
Expected Output: [1]
Explanation: Removing `b` at index 1 gives `ac`.
Input: ("aab", "ab")
Expected Output: [0, 1]
Explanation: Removing either the first or second `a` produces `ab`.
Input: ("aaaa", "aaa")
Expected Output: [0, 1, 2, 3]
Explanation: Deleting any one `a` still leaves `aaa`.
Input: ("abca", "aba")
Expected Output: [2]
Explanation: Only removing `c` at index 2 yields `aba`.
Input: ("a", "")
Expected Output: [0]
Explanation: Deleting the only character produces the empty string.
Solution
def solution(s1, s2):
n = len(s1)
m = len(s2)
if n != m + 1:
return []
prefix = [False] * (m + 1)
prefix[0] = True
for i in range(m):
prefix[i + 1] = prefix[i] and (s1[i] == s2[i])
suffix = [False] * (m + 1)
suffix[m] = True
for i in range(m - 1, -1, -1):
suffix[i] = suffix[i + 1] and (s1[i + 1] == s2[i])
ans = []
for i in range(n):
if prefix[i] and suffix[i]:
ans.append(i)
return ans
Time complexity: O(n). Space complexity: O(n).
Hints
- Deleting index `i` works only if the prefix before `i` matches and the suffix after `i` also matches.
- Precompute which prefixes match and which suffixes match so each index can be checked in O(1).