Mathworks OA Interview Question: Maximum Operations / Secure The Servers

Maximum Operations

Description

Given a string s of lowercase English characters, the following operation can be performed on it any number of times.

Choose three consecutive characters s[i], s[i + 1], and s[i + 2] (1-based indexing) such that s[i] = s[i + 1] and s[i + 1] != s[i + 2]. Replace s[i + 2] with s[i].

For example, if s = "aabc", then after the operation at i = 1, s = "aaac".

Find the maximum number of operations that can be applied to s.

Example

Consider s = "accept".

The following operations are performed. Bold indicates the changed character.

• In the original string, start at i = 2, "cce". The new string s' = "acccpt".
• Start at i = 3, s'="acccct".
• Start at i = 4, s'="accccc".

There is no other selection available. The operation can be applied a maximum of 3 times.

Secure The Servers

Description

The developers of Hackerworld want to secure a database system consisting of n data servers. The vulnerability of the i-th server is represented by server[i]. An upgrade can be done on any particular server to reduce its vulnerability by 1 unit.

Given the vulnerabilities of the servers represented by the array server, find the maximum possible vulnerability of the smallest element in the final vulnerabilities of the servers after performing exactly k upgrades.

Example

Consider n = 4, server = [2, 2, 3, 3] and k = 3.

Considering 1-based indexing, the following upgrades can be performed:

• Select server[1] and subtract 1 from it to obtain arr = [1, 2, 3, 3].
• Select server[3] and subtract 1 from it to obtain arr = [1, 2, 2, 3].
• Select server[4] and subtract 1 from it to obtain arr = [1, 2, 2, 2].

Return 1, the smallest vulnerability in the final array.

This set includes two classic interview-style problems. In Secure The Servers, the goal is to maximize the minimum value after exactly k decrements, which is typically solved with binary search on the answer plus a feasibility check using the total cost to raise the minimum threshold. In Maximum Operations, the string operation propagates a repeated character through adjacent triples, so the core is to track how far the transformation can spread and how many valid operations can be chained.