Compute ring window max and deletion indices

Q: Compute ring window max and deletion indices

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.

Q: How do I approach Coding & Algorithms interview questions?

Coding & Algorithms questions require understanding of core concepts and practice. PracHub provides solutions with explanations to help you master coding & algorithms interviews.

Question

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.

Compute ring window max and deletion indices

Overview

Comments (0)