Amazon SDE II Online Assessment

I was given these two problems:

Question 1: Minimize Handler Preparation Time

In an Amazon Distribution Center, two handlers prepare a sequence of n packing stations. Each packing station requires a specific workflow type before it can be operated.

The type required for the ith packing station is given by workflowList[i], where each workflow type is a number between 1 and k. The time it takes a handler to prepare a station depends on what they prepared last:

• If a handler prepares the same workflow type as their previous station, it takes shortStationPrepTimes[type] minutes.
• If they switch to a different type (or it’s their first station), it takes longStationPrepTimes[type] minutes.

Only one handler works at a time, each station must be assigned in order from 1 to n to one of the two handlers. Determine the minimum total time needed to prepare all stations.

Example:

1. workflowList = [1, 2, 2], longStationPrepTimes = [4, 5], shortStationPrepTimes = [2, 3], result = 12 minutes
2. workflowList = [1, 2, 1, 2], longStationPrepTimes = [10, 6, 5], shortStationPrepTimes = [4, 2, 4], result = 22 minutes
3. workflowList = [2, 1, 2, 1, 1], longStationPrepTimes = [15, 20], shortStationPrepTimes = [10, 5], result = 60 minutes

Constraints:

• 1 ≤ n ≤ 2000
• 1 ≤ k ≤ 2 * 10^5
• 1 ≤ workflowList[i] ≤ k
• 1 ≤ shortStationPrepTimes[i] ≤ longStationPrepTimes[i] ≤ 10^9
• k = longStationPrepTimes.size () = shortStationPrepTimes.size () = types of workflows
• n = workflowList.size () = number of stations

Question 2: Reconstruct Configuration from Erased Digits

The software developers at Amazon are working on detecting configuration anomalies in a server. They are provided with a set of configurations represented by config, a string of concatenated decimal digits (0-9). However, some digits in these configurations have been inadvertently erased.

These configurations were initially generated using a specific procedure involving two integer parameters, x and y.

The procedure begins with the two numbers, x and y, and initializes a current value (cur) to 0. The following operation can be performed any number of times.

• In each step, either x or y is added to cur.
• Compute the unit digit of cur (cur % 10) after each addition.
• Record this digit as part of the configuration sequence.

Unfortunately, some of these recorded digits are missing due to data corruption, complicating the reconstruction of the original sequence. Additionally, it is known that the first character of each given configuration string corresponds to either x or y.

The task is to identify the final configuration with the minimum possible decimal value from which the given configuration config can be constructed by removing specific digits of the final configuration.

If multiple valid configurations can be formed by reconstruction the missing digits, return the one with the minimum decimal value among all possible valid configurations.

Conversely, if no valid configuration can be restored using the described procedure, then in that case return the string “-1”.

Note:

• Each configuration is represented as a string of concatenated decimal digits (0-9) that forms a decimal number. The value of a configuration refers to the decimal number it represents.
• The given configuration config, represents the server configuration after data corruption, i.e., configuration after some of it’s digits have been erased from the original configuration.

Example:

1. config = “27”, x = 2, y = 3, result = “247”
2. config = “324”, x = 2, y = 3, result = “36924”
3. config = “521”, x = 5, y = 5, result = “-1”

Constraints:

• 2 ≤ |config| ≤ 2 * 10^5
• 1 ≤ x, y ≤ 9