Round 1
Questions:
Question
Team of developers at Amazon is working on a feature that checks the strength of a password as it is set by a user.
Analysts found that people use their personal information in passwords, which is insecure. The feature searches for the presence of a reference string as a subsequence of any permutation of the password. If any permutation contains the reference string as a subsequence, then the feature determines the minimum cost to remove characters from password so that no permutation contains the string reference as a subsequence.
The removal of any character has a cost given in an array, cost, with 26 elements that represent the cost to replace 'a' (cost[0]) through 'z' (cost[25]). Given two strings password and reference, determine the minimum total cost to remove characters from password so that no permutation contains the reference string as a subsequence.
Note:
A permutation is a sequence of integers from 1 to n of length n containing each number exactly once, for example [1, 3, 2] is a permutation while [1, 2, 1] is not.
A subsequence is a sequence that can be derived from another sequence by deleting some or elements, without changing the order of the remaining elements. For example, given the string "abcde", the following are subsequences: "a", "ace", "be", "bde" etc. while sequences like "dea", "acbde" are not subsequences.
Example
Suppose password "adefgh", reference "hf", and cost = [1, 0, 0, 2, 4, 4, 3, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0].
Some possible removals from password so that no permutation contains the string reference as a subsequence are:
Case 1:
cost: 1 2 4 4 3 1
character: a d e f g h
remove letter h would result in below and cost of removal = 1
a d e f g
Case 2:
cost: 1 2 4 4 3 1
character: a d e f g h
remove letter f would result in and cost of removal = 4
a d e g h
In Case 1 we are removing only a single letter 'h' so the cost of removal in this case becomes 1.
Similarly in Case 2 we are removing only a single letter 'f' so the cost of removal in this case becomes 4
Since removing either h or f will remove the existence of reference as a subsequence so we optimally choose to remove 'h' (Case 1), therefore the minimum cost is 1.
Function Description
Complete the function minCost in the editor below:
minCost has the following parameters:
string password: the password string
string reference: the string which should not exist as a subsequence in any permutation of password
int cost[26]: the costs to remove each character in the lowercase english alphabet
Returns
long int: the minimum cost to remove characters from password such that no permutation contains the reference string as a subsequence
Sample inputs and outputs:
a)
password "abcdcbcb"
reference "bcb"
cost = [2, 3, 1, 4, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
sample output = 3
b)
password = "kkkk"
reference = "k"
cost = [ 5, 1, 1, 2, 4, 7, 3, 4, 5, 7, 5, 6, 2, 1, 5, 12, 5, 1, 5, 0, 5, 6, 4, 7, 8, 50]
sample output = 20
explanation
remove 5 occurrences of k at a cost of 5*4 = 20
Question
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 a 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.
a b b d
-> a b d a
-> a b c d
-> a b c a
-> a b c b
The lexicographically smallest special string that is greater than "abbd" is "abca".
Function Description
Complete the function getSpecialString in the editor below.
getSpecialString has the following parameter:
s : the input string
Returns
string: the lexicographically smallest string that is greater than s. If no such special string exists, return "-1".
constraints:
1 <= | s | <= 10 ^ 6
s consists of lowercase english letters only
sample input 1:
s = abccde
sample output:
abcdab
explanation: Some of the special strings that are lexicographically greater than s are "abcdde", "abcdab", "abcdbc"
sample input 2:
s = zzab
sample output:
-1
explanation:
There is no special string of length 4 that is lexicographically greater than s
Candidate's Approach
No approach provided.
Interviewer's Feedback
No feedback provided.