How should I practice Find Minimum Inefficienty?

Start by reading the full statement, solve the visible examples, then compare the pattern against related Amazon online assessment problems in FastPrep.

Is Find Minimum Inefficienty associated with Amazon?

FastPrep tags this as a Amazon coding interview or online assessment practice problem when the problem catalog has that company context.

Problem · Dynamic Programming

Find Minimum Inefficienty

Learn this problem

● MediumAmazonINTERNNEW GRADOA

See Amazon hiring insights

Problem statement

Amazon Web Service has n servers, each of them either has high fault tolerance or high reliability. A system works better if all the servers have the same attributes. The inefficiency of a group of server is defined as the number of adjacent pairs of server that have different attributes.

Consider, for example, a set of servers described as 1001001 where '0' means the server has high fault tolerance, '1' means the server has high reliabiity. The inefficiency of this group is 4 as described in the image below:

Given a string serverType of length n consisting of '0', '1', and '?', where '0' means the server has high fault tolerance, '1' means the server has high reliability, and '?' means you can install any type of server there, find the minimum inefficiency you can get after install a server at each '?'.

Function

findMinimumInefficiency(serverType: String) → int

Complete the function findMinimumInefficiency in the editor.

findMinimumInefficiency has the following parameter:

string serverType: the server types

Returns

int: the minimum possible inefficiency

💐 1008th thank you to spike! 👏

Examples

Example 1

serverType = "??011??0"return = 2

In the above example, the number of servers n = 8. One optimal way to install servers is to 1. Install a server having fault tolerance (0) at the first and the second positions. 2. Install a server having high reliability (1) at the sixth and the seventh positions. After making these changes, the server types are '00011110'. The number of adjacent pairs having different server types is 2. It can be shown that the answer cannot be reduced from 2. Return 2. Note that another possible way to achieve a minimum number of different adjancet pairs as 2 would 00011100 and 00011000.

Example 2

serverType = "00?10??1?"return = 3

One optimal way to install servers is to install high-reliability servers at every '?'. The new server types are "001101111" with 3 adjacent dissimilar pairs. Return 3.

Constraints

1 <= n <= 10^5
serverType consists of '0', '1' and '?' only