Katkat
Back

Split a Message into Length-Limited Parts with Numbered Suffixes

Hudson River TradingSoftware Engineer · Technical Screen
MediumSoftware EngineerTechnical ScreenSoftware Engineering Fundamentals

Last updated

This problem tests your ability to handle string manipulation, edge-case arithmetic, and iterative construction while adhering to dynamic length constraints imposed by mandatory metadata.

Problem Statement

You are tasked with splitting a long message string into multiple smaller messages. Each output message must have a maximum length of K characters. To keep track of the sequence, each output message must end with a suffix in the format " (i/n)", where i is the current message index (1-indexed) and n is the total number of messages.

Your function should return a list of strings such that the total length of each string (the content fragment plus the suffix) does not exceed K. If it is impossible to fit the message into any number of chunks (e.g., if the suffix itself is longer than K), return an empty list. Try to minimize the total number of parts n.

Function Signature

def split_message(message: str, K: int) -> List[str]:

Examples

Example 1: Input: message = "Hello world", K = 10 Output: ["He (1/2)", "llo (2/2)", "world (2/2)"] (Note: The suffix length changes based on the number of digits in n.)

Example 2: Input: message = "ABC", K = 3 Output: [] (Cannot fit any message including suffix " (1/1)" which is 6 characters long.)

Constraints

  • 1 <= len(message) <= 10^5
  • 5 <= K <= 1000
  • The message contains only alphanumeric characters and spaces.

Edge Cases

  • What if the message length is smaller than K but still requires a suffix?
  • Ensure the logic accounts for the fact that the length of the suffix (i/n) increases as n grows (e.g., (9/9) is shorter than (10/10)).

Hints

Hint 1

First, determine the length of the suffix template for a given total number of messages `n`, noting that the length of `i` and `n` can vary.

Hint 2

Since the number of messages `n` is unknown, consider using a binary search or a heuristic to estimate `n` and verify if the message can be partitioned successfully.

Hint 3

Keep in mind that the suffix length is constant for all messages once `n` is fixed, except for potential digit-width changes; however, you can pad indices to a fixed width if needed or recalculate carefully.

Follow-up questions

  • How would your solution change if the message could contain unicode characters that occupy more than one byte?
  • If we wanted to ensure we don't break words (split only on spaces), how would the greedy approach need to be modified?
  • What is the time complexity of your approach, and how does the dependency on `n` affect the overall performance?