Katkat
Back

Sort a String of Clothing Sizes

UberSoftware Engineer · Technical Screen
EasySoftware EngineerTechnical ScreenCoding & Algorithms

Last updated

This problem tests the ability to perform a custom sort on a constrained set of characters using an O(n) counting approach rather than a standard comparison-based O(n log n) sort.

Problem Statement

You are given a string sizes consisting only of the characters 'S', 'M', and 'L', representing clothing sizes. Your task is to sort the string such that all 'S' characters come first, followed by 'M', and then 'L'.

Implement the function sort_sizes(sizes: str) -> str.

Constraints

  • The string length n is between 0 and 1,000,000.
  • You should aim for O(n) time complexity and O(1) auxiliary space (excluding the output string).

Examples

Example 1 Input: "LMSMS" Output: "SSMML"

Example 2 Input: "MMM" Output: "MMM"

Edge Cases

  • Empty string: "" should return "".
  • String containing only one type of character: e.g., "SSSS" should return "SSSS".
def sort_sizes(sizes: str) -> str:
    # Implementation here
    pass

Hints

Hint 1

Since there are only three possible values, you can count the occurrences of each character instead of using a sorting algorithm.

Hint 2

Traverse the string once to calculate the total counts for 'S', 'M', and 'L', then reconstruct the string based on these counts.

Hint 3

For the reconstruction step, you can use the string multiplication operator (e.g., 'S' * count_s) to build the result efficiently.

Follow-up questions

  • How would you modify your approach if the input string contained an unexpected character, such as 'X'?
  • What changes would be required to support a dynamic list of sizes with a custom priority order, such as ['XS', 'S', 'M', 'L', 'XL']?
  • How does your implementation perform under memory pressure if the input size grows to 100 million characters?