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 Technical Screen rounds at J.P. Morgan.

What role is this question designed for?

This question is commonly asked for Software Engineer candidates at J.P. Morgan during technical interviews.

Compute ring window max and deletion indices | J.P. Morgan Coding Question

Quick Overview

This question evaluates algorithmic problem-solving across arrays and strings, covering concepts such as sliding-window techniques on circular arrays, wraparound handling, index recovery after single-character deletion, duplicate-character considerations, and time/space complexity analysis within the Coding & Algorithms domain.

Compute ring window max and deletion indices

Company: J.P. Morgan

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: Medium

Interview Round: Technical Screen

Part A — Ring window maximum: You are given n computers arranged in a circle, represented by an array of bits (1 = on, 0 = off), and an integer k (1 <= k <= n). What is the maximum number of on computers within any k consecutive positions along the ring (wrapping allowed)? Describe an algorithm and analyze its time and space complexity. Part B — Deletion index recovery: You are given two strings s1 and s2 such that s2 can be obtained from s1 by deleting exactly one character (i.e., |s1| = |s2| + 1). Return all 0-based indices i in s1 such that removing s1[i] yields s2. Provide the algorithm and its complexity, and explain how you handle repeated characters and edge cases.

Quick Answer: This question evaluates algorithmic problem-solving across arrays and strings, covering concepts such as sliding-window techniques on circular arrays, wraparound handling, index recovery after single-character deletion, duplicate-character considerations, and time/space complexity analysis within the Coding & Algorithms domain.

Ring Window Maximum

You are given `n` computers arranged in a circle, represented by an integer array `bits` where each element is `1` (on) or `0` (off), and an integer `k` with `1 <= k <= n`. Consider every window of `k` consecutive positions along the ring, where the window is allowed to wrap around from the end of the array back to the beginning. Return the maximum number of on computers (`1`s) contained in any such window. For example, with `bits = [1, 0, 0, 0, 1, 1]` and `k = 3`, the wrapping window covering the last two positions and the first position contains `[1, 1, 1]` = 3 ones, which is the maximum.

Constraints

1 <= n == len(bits) <= 10^5
Each bits[i] is either 0 or 1
1 <= k <= n
The window wraps around the end of the array (circular)

Examples

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

Expected Output: 2

Explanation: Best window of size 2 is [1, 1] (positions 2-3) with 2 ones.

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

Expected Output: 3

Explanation: Wrapping window covering positions 4, 0, 1 = [1, 1, 1] has 3 ones.

Input: ([0, 0, 0, 0], 2)

Expected Output: 0

Explanation: All computers off, so every window has 0 ones.

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

Expected Output: 4

Explanation: k equals n, so the whole ring is the window: 4 ones.

Input: ([1], 1)

Expected Output: 1

Explanation: Single on computer, single-element window.

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

Expected Output: 3

Explanation: Wrapping window over positions 4, 5, 0 = [1, 1, 1] has 3 ones.

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

Expected Output: 1

Explanation: With k = 1 the answer is just whether any single position is on.

Hints

A sliding window of fixed size k works directly; the only twist is wrapping. Compute the sum of the first k elements, then slide one position at a time.
When you slide the window by one, add the element entering at index (i + k - 1) mod n and subtract the element leaving at index i - 1. This keeps each step O(1).
You only need n window positions total (one starting at each index), so a single pass over n positions is sufficient — there is no need to physically duplicate the array.

Deletion Index Recovery

You are given two strings `s1` and `s2` such that `s2` can be obtained from `s1` by deleting exactly one character, so `len(s1) == len(s2) + 1`. Return a list of all 0-based indices `i` in `s1` such that removing `s1[i]` yields exactly `s2`. The indices must be returned in increasing order. When `s1` contains repeated characters, several different deletion positions can produce the same result, so multiple valid indices may exist. For example, `s1 = "aab"`, `s2 = "ab"`: removing index 0 or index 1 both give `"ab"`, so the answer is `[0, 1]`. If `s2` cannot be produced from `s1` by a single deletion, return an empty list.

Constraints

0 <= len(s2) <= 10^5
len(s1) == len(s2) + 1 in the valid case (otherwise return [])
Strings consist of printable characters
Indices in the result are 0-based and returned in increasing order

Examples

Input: ("abcde", "abde")

Expected Output: [2]

Explanation: Only removing index 2 ('c') yields 'abde'.

Input: ("aaa", "aa")

Expected Output: [0, 1, 2]

Explanation: All three characters are identical, so deleting any index yields 'aa'.

Input: ("abc", "ab")

Expected Output: [2]

Explanation: s2 is a prefix of s1; the deletion is the last character at index 2.

Input: ("a", "")

Expected Output: [0]

Explanation: Deleting the only character gives the empty string.

Input: ("aab", "ab")

Expected Output: [0, 1]

Explanation: Removing either of the two leading 'a's produces 'ab'.

Input: ("banana", "banaa")

Expected Output: [4]

Explanation: Only removing index 4 ('n') yields 'banaa'; the run of that character is length one.

Input: ("xyz", "yz")

Expected Output: [0]

Explanation: The first character differs immediately; deleting index 0 gives 'yz'.

Input: ("abb", "ab")

Expected Output: [1, 2]

Explanation: Removing either of the two trailing 'b's produces 'ab'.

Input: ("abc", "xy")

Expected Output: []

Explanation: s2 cannot be obtained from s1 by a single deletion, so the result is empty.

Hints

Scan from the left to find the first index i where s1 and s2 differ. The deleted character must be s1[i]. If no mismatch is found, the deletion happened at the very end (i = len(s2)).
After locating that first mismatch, verify the rest actually lines up: s1[i+1:] must equal s2[i:]. If it does not, s2 was not obtainable by a single deletion, so return an empty list.
Repeated characters create multiple valid answers: any index inside the maximal run of the character s1[i] (extending both left and right from i) is also a valid deletion point. Expand left while s1[lo-1] == s1[i] and right while s1[hi+1] == s1[i], then return the full range [lo, hi].

Quick Overview