Round 1
Questions: Data Scientists at Amazon are working on cleansing a machine learning dataset. The dataset is represented as a string dataset consisting of an even number of lowercase English letters. The goal is to clean the dataset efficiently by performing specific operations.
Here's how the operations work:
- In each operation, two characters from the dataset are selected and removed.
- Each operation has an associated cost:
- x: the cost of removing two identical characters.
- y: the cost of removing two different characters.
The task is to determine the optimal strategy that minimizes the total cost to completely clean up the dataset. In other words, find the minimum cost required to remove all characters and make the dataset empty.
Example:
dataset = "ouio" x = 2 y = 4
- Initial String: dataset = "ouio"
- Operation 1:
- Action: Remove the first and last characters of the dataset, resulting in the string dataset = "ui".
- Cost: x = 2 (since both removed characters, 'o' and 'o', are the same).
- Operation 2:
- Action: Delete the remaining characters of "ui", making dataset an empty string.
- Cost: y = 4 (since the removed characters, 'u' and 'i', are different).
Total Cost: x + y = 2 + 4 = 6.
Function Description:
Complete the function cleanupDataset in the editor below.
cleanupDataset has the following parameters:
- string dataset: a string that denotes a machine learning dataset
- int x: the cost of operation when the removed characters are equal
- int y: the cost of operation when the removed characters are unequal
Returns:
- int: the minimum cost to clean up the dataset or make the string empty.
Constraints:
- 2 ≤ |dataset| ≤ 10^5
- /dataset/ is even
- 1 ≤ x, y ≤ 10^4
Sample Case 0: Sample Input 0:
aaabca 3 2
Sample Output 0:
7
Explanation: In the first operation, the first and second characters are deleted from the dataset, resulting in dataset = "abca". The cost of this operation is x = 3 because both removed characters are equal ('a'). In the next operation, the first and third characters are deleted, making dataset = "ba". The cost of this operation is y = 2 because the removed characters are not equal. In the final operation, the remaining two characters are deleted, making the dataset an empty string. The cost of this operation is y = 2 because the removed characters are not equal. Hence, the total cost is 3 + 2 + 2 = 7.
Candidate's Approach
No approach provided.
Interviewer's Feedback
No feedback provided.