Round 1
Questions:
Implement an encryption algorithm to encrypt the string originalString
per the following:
Initialize two empty strings: temporaryString
and encryptedString
.
At each step, perform one of the following two operations. Choose the order of operations to produce the lexicographically minimum possible encryptedString
.
- Take the first letter from
originalString
and append it to the end oftemporaryString
. - Take the last letter from
temporaryString
and append it to the end of theencryptedString
.
Example:
-
originalString = "dby" output = "bdy"
-
originalString = "vgxgpu" output = "ggpuxv"
Candidate's Approach
I pushed all characters in a multiset and started iterating over the originalString
. If originalChar[i] <= current char in multiset
, I append it to my encryptedString
and move the iterator next (of multiset). If temporaryString
is not empty and its last character <= current char in multiset, I append it to my encryptedString
and move the iterator next (of multiset). This second operation is done in a loop until the last char of temporaryString
is greater than the current iterator. Otherwise, I append it to temporaryString
. At the end, if any characters are remaining in temporaryString
, I append those chars starting from the end.
My code passed 7/15 test cases for this question.
Interviewer's Feedback
No feedback provided.