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
originalStringand append it to the end oftemporaryString. - Take the last letter from
temporaryStringand 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.