Katkat
Back

Implement text wrapping, waitlist, and intervals

GoogleSoftware Engineer · Onsite
MediumSoftware EngineerOnsiteCoding & Algorithms

Last updated

This problem tests your ability to implement a greedy word-wrapping algorithm and a custom queue data structure that supports efficient deletions based on time intervals.

Part 1: Word Wrapping

Given a list of words and a maximum line width W, implement a function to arrange the words into lines such that each line has a length at most W. Use a greedy approach: pack as many words as possible into a line before moving to the next. Add a single space between words on the same line.

def wrap_text(words: List[str], W: int) -> List[str]:

Example: Input: words = ["hello", "world", "this", "is", "a", "test"], W = 10 Output: ["hello world", "this is a", "test"]

Part 2: Waitlist Management

Design a data structure Waitlist that tracks users and their reserved time intervals [start, end]. The system must support:

  1. add(user_id, start, end): Add a user to the waitlist.
  2. remove(user_id): Remove a user by ID.
  3. get_active_count(time): Return the number of users whose interval [start, end] covers the given time (inclusive).

Constraints:

  • start and end are integers.
  • get_active_count should be optimized for frequent queries.

Example: wl = Waitlist() wl.add("A", 1, 5) wl.add("B", 3, 7) wl.get_active_count(4) -> Returns 2 (Both A and B are active at time 4).

Hints

Hint 1

For the wrapping logic, iterate through the words while maintaining a running count of characters and spaces, starting a new line only when the next word exceeds the width.

Hint 2

For the waitlist, since you need to remove by user_id, use a dictionary to map IDs to their intervals for O(1) retrieval during removal.

Hint 3

To optimize `get_active_count`, consider storing intervals in a structure like a segment tree or using a sweep-line approach with a sorted list of time points if the number of users is large.

Follow-up questions

  • How would you modify the text wrapper to justify lines by adding extra spaces to make them exactly length W?
  • If the waitlist queries are very frequent but additions are rare, how would you cache the results of get_active_count?
  • What is the time complexity of your remove() operation in the Waitlist class if you use a balanced BST to store active intervals?