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 max-ons and deletion indices | J.P. Morgan Coding Question

Quick Overview

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.

Compute max-ons and deletion indices

Company: J.P. Morgan

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Technical Screen

##### Question Given a circular array of n computers represented by 0 (off) and 1 (on), determine the maximum possible number of on computers within any contiguous block of k adjacent computers. Given two strings s1 and s2 where |s1| = |s2| + 1 and s2 can be obtained by deleting exactly one character from s1, return all indices in s1 whose removal yields s2.

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

You are given a circular array `computers` of length `n`, where each element is either `0` (off) or `1` (on). Because the array is circular, the element after the last one is the first element again. Find the maximum number of on computers that can appear in any contiguous block of exactly `k` adjacent computers.

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.

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

You are given two strings `s1` and `s2` such that `len(s1) = len(s2) + 1`. Find all indices `i` in `s1` where deleting the character `s1[i]` makes the remaining string exactly equal to `s2`. Return the indices in increasing order.

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`.

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).

Quick Overview