Implement text wrapping, waitlist, and intervals

Q: Implement text wrapping, waitlist, and intervals

This question evaluates skills in string parsing and word-wrapping logic, data-structure design for FIFO queue management and deletions, and interval reasoning for overlap detection and resource allocation in the Coding & Algorithms domain.

Q: How do I approach Coding & Algorithms interview questions?

Coding & Algorithms questions require understanding of core concepts and practice. PracHub provides solutions with explanations to help you master coding & algorithms interviews.

Q: What difficulty level is this interview question?

This is a medium difficulty Coding & Algorithms question, commonly asked during Onsite rounds at Google.

Q: What role is this question designed for?

This question is commonly asked for Software Engineer candidates at Google during technical interviews.

Question

Loading...

Answer the following coding questions.

1) Text wrapping: count lines in a fixed-width document

You are rendering text into a document where each line has a maximum width maxWidth (monospace: each character has width 1).

Given an input string text and integer maxWidth, compute how many lines are needed to render the text.

Rules

The input may contain:
- letters/digits/punctuation,
- spaces ( ' ' ),
- newline characters ( '\n' ).
A newline character forces a new line .
Words are sequences of non-space, non-newline characters.
Wrapping is by words :
- Words are placed left-to-right, separated by a single space when on the same line.
- Leading/trailing spaces on a line are not rendered.
- Multiple consecutive spaces in the input act as a single separator.
If a word’s length is greater than maxWidth , you may split it across lines (state your behavior clearly and apply consistently).

Output

Return the total number of rendered lines.

Constraints (you may assume)

1 <= maxWidth <= 10^4
0 <= len(text) <= 10^5

2) Waitlist APIs for matching a table size

Design and implement a waitlist data structure with these operations:

join(userId, partySize) : add a user party to the waitlist.
delete(userId) : remove that user party from the waitlist if present.
find_first_match(tableSize) : return the earliest-joined userId whose partySize <= tableSize . If no match exists, return a sentinel (e.g., null ).

Requirements

join adds to the end (FIFO).
delete can remove a party from anywhere in the queue.
find_first_match should not remove the user (unless you explicitly design it to).
Handle duplicates/invalid operations explicitly (e.g., joining an existing userId, deleting missing userId).

3) Intervals

Given time intervals [start, end) (end is not included):

Write a function to determine whether two intervals overlap.
Given a list of meeting intervals, compute the minimum number of conference rooms required so that no assigned meetings overlap in the same room.