Amazon OA

Round 1

Questions:

Question 1

Problem: Rate-Limiting Algorithm

Some developers at Amazon are building a prototype for a simple rate-limiting algorithm. There are n requests to be processed by the server, represented by a string requests, where the i-th character represents the region of the i-th client. Each request takes 1 unit of time to process.

There must be a minimum time gap of minGap units between any two requests from the same region.

• The requests can be sent in any order, and there can be gaps in transmission for testing purposes.
• Find the minimum amount of time required to process all the requests such that no request is denied.

Example 1:

Suppose n = 6, requests = "aaabbb", and minGap = 2:

requests: a a a b b b
           | |   | | 
         ab _ ab _ ab (minimum time gap of 2 between same region requests)

The requests can be sent in the order ab_ab_ab where _ represents that no request was sent in that unit time. Here, the minimum time gap between two requests from the same region is minGap = 2.

The total time taken is 8 units.

Example 2:

Input:

12
abacadaeafag
2

Explanation:

• n = 12
• requests = "abacadaeafag"
• minGap = 2

Sample Output:

16

Explanation: One optimal strategy is: "ab_ad_afgae_ac_a"

Function Description:

Complete the function getMinTime in the editor below:

def getMinTime(n: int, requests: str, minGap: int) -> int:

Parameters:

• n: the number of requests
• requests: a string representing the region of each request
• minGap: the minimum time gap required between requests from the same region

Returns:

• The function should return an integer representing the minimum time required to process all requests without denial.

Question 2

Problem: Lexicographically Smallest Special String

Developers at Amazon are working on a text generation utility for one of their new products.

Currently, the utility generates only special strings. A string is special if there are no matching adjacent characters. Given a string s of length n, generate a special string of length n that is lexicographically greater than s. If multiple such special strings are possible, then return the lexicographically smallest string among them.

Notes:

• Special String: A string is special if there are no two adjacent characters that are the same.
• Lexicographical Order: This is a generalization of the way words are alphabetically ordered in dictionaries. For example, "abc" is lexicographically smaller than "abd" because 'c' comes before 'd' in the alphabet.

A string a is lexicographically smaller than a string b if and only if one of the following holds:

• a is a prefix of b, but is not equal to b. For example, "abc" is smaller than "abcd".
• In the first position where a and b differ, the character in a comes before the character in b in the alphabet. For example, "abc" is smaller than "abd" because 'c' comes before 'd'.

Important Considerations:

• If the character is 'z', it is the last character in the alphabet and cannot be increased further. The string should not wrap around to 'a' after 'z'.
• The output string must not have any adjacent characters that are the same.

Example:

Suppose s = "abbd":

Some of the special strings that are lexicographically greater than s are shown below:

abbd -> abca

The lexicographically smallest special string that is greater than "abbd" is "abca".

Function Description:

Complete the function getSpecialString in the editor below:

def getSpecialString(n: int, s: str) -> str:

Parameters:

• n: the length of the string s
• s: the string for which you need to find the lexicographically smallest special string that is greater than s

Returns:

• The function should return the lexicographically smallest special string of length n that is greater than s.