PracHub
QuestionsPremiumLearningGuidesInterview PrepNEWCoaches

Quick Overview

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.

  • medium
  • Google
  • Coding & Algorithms
  • Software Engineer

Implement text wrapping, waitlist, and intervals

Company: Google

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Onsite

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): 1. Write a function to determine whether two intervals overlap. 2. Given a list of meeting intervals, compute the minimum number of conference rooms required so that no assigned meetings overlap in the same room.

Quick Answer: 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.

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

Given a string text and an integer maxWidth, return how many lines are needed to render the text in a monospace document. Newline characters force a new rendered line. Words are wrapped greedily, multiple spaces act as one separator, and leading/trailing spaces on each line are ignored. If a word is longer than maxWidth, split it into consecutive chunks of length maxWidth, with the last chunk possibly shorter. An entirely empty string renders as 0 lines; otherwise, each segment between newline characters occupies at least one line, even if it becomes blank after trimming spaces.

Constraints

  • 1 <= maxWidth <= 10^4
  • 0 <= len(text) <= 10^5
  • text contains printable characters, spaces, and newline characters

Examples

Input: ('Hello world', 6)

Expected Output: 2

Explanation: 'Hello' fits on the first line and 'world' goes on the second.

Input: ('a bb ccc', 6)

Expected Output: 2

Explanation: Multiple spaces collapse to one separator, so the lines are 'a bb' and 'ccc'.

Input: ('abcdefghij', 4)

Expected Output: 3

Explanation: The long word is split into 'abcd', 'efgh', and 'ij'.

Input: (' hi there\n\nok ', 5)

Expected Output: 4

Explanation: First segment wraps to 2 lines, the empty middle segment contributes 1 blank line, and 'ok' uses 1 line.

Input: ('', 10)

Expected Output: 0

Explanation: An empty string renders no lines.

Hints

  1. Split the input on newline first; each segment is wrapped independently.
  2. For one segment, use segment.split() to get words, then simulate greedy packing onto lines.

Part 2: Waitlist APIs - join, delete, and find earliest matching party

Implement a batch simulator for a restaurant waitlist. Each operation is one of: ('join', userId, partySize), ('delete', userId), or ('find_first_match', tableSize). join adds a new party to the end of the waitlist and returns True; if the userId is already active or partySize is not positive, return False. delete removes that user if present and returns True; otherwise return False. find_first_match returns the earliest-joined active userId whose partySize <= tableSize without removing them, or None if no match exists. Rejoining after deletion is allowed and counts as a new join time. Return a list of results for all operations in order.

Constraints

  • 1 <= len(operations) <= 2 * 10^5
  • 1 <= partySize, tableSize <= 10^9 for valid operations
  • userId values are hashable and are strings in the tests

Examples

Input: [('join', 'alice', 4), ('join', 'bob', 2), ('find_first_match', 2), ('find_first_match', 4)]

Expected Output: [True, True, 'bob', 'alice']

Explanation: For table size 2, only 'bob' fits. For table size 4, the earliest fitting party is 'alice'.

Input: [('join', 'x', 2), ('delete', 'x'), ('join', 'x', 4), ('find_first_match', 3), ('find_first_match', 4)]

Expected Output: [True, True, True, None, 'x']

Explanation: After deletion, 'x' can rejoin as a new entry.

Input: [('join', 'u1', 3), ('join', 'u1', 2), ('delete', 'u2'), ('find_first_match', 1)]

Expected Output: [True, False, False, None]

Explanation: Duplicate active joins fail, deleting a missing user fails, and no party fits table size 1.

Input: [('find_first_match', 4), ('join', 'a', 5), ('join', 'b', 2), ('delete', 'a'), ('find_first_match', 4)]

Expected Output: [None, True, True, True, 'b']

Explanation: The first query is on an empty waitlist; after deleting 'a', 'b' becomes the first match.

Input: [('join', 'bad', 0), ('join', 'ok', 1), ('find_first_match', 0)]

Expected Output: [False, True, None]

Explanation: A non-positive party size is invalid, and table size 0 matches nobody.

Hints

  1. Because joins only append, you can assign each join a permanent increasing index.
  2. A segment tree storing the minimum active party size in each range can help you find the leftmost active party with size <= tableSize.

Part 3: Intervals - determine whether two half-open intervals overlap

Given two time intervals [start, end), determine whether they overlap. The interval end is excluded, so intervals that only touch at an endpoint do not overlap. Empty intervals such as [x, x) also do not overlap anything.

Constraints

  • -10^9 <= start <= end <= 10^9
  • Each interval is half-open: [start, end)

Examples

Input: ((1, 5), (4, 8))

Expected Output: True

Explanation: They share times in [4, 5).

Input: ((1, 2), (2, 3))

Expected Output: False

Explanation: They only touch at time 2, which is excluded from the first interval.

Input: ((0, 0), (0, 10))

Expected Output: False

Explanation: [0, 0) is empty.

Input: ((-3, 1), (-1, 0))

Expected Output: True

Explanation: The second interval lies inside the first.

Hints

  1. Two half-open intervals overlap exactly when the later start is strictly less than the earlier end.
  2. Be careful with touching endpoints like [1, 2) and [2, 3).

Part 4: Intervals - minimum number of conference rooms required

Given a list of meeting intervals [start, end), return the minimum number of conference rooms needed so that no two overlapping meetings are assigned to the same room. Because the intervals are half-open, a meeting ending at time t does not conflict with one starting at time t.

Constraints

  • 0 <= len(intervals) <= 2 * 10^5
  • -10^9 <= start < end <= 10^9
  • Intervals are half-open: [start, end)

Examples

Input: []

Expected Output: 0

Explanation: No meetings require no rooms.

Input: [(0, 30), (5, 10), (15, 20)]

Expected Output: 2

Explanation: One room can host (0, 30) and another handles the shorter overlapping meetings.

Input: [(7, 10), (2, 4)]

Expected Output: 1

Explanation: The meetings do not overlap.

Input: [(1, 2), (2, 3), (3, 4)]

Expected Output: 1

Explanation: Touching endpoints do not overlap for half-open intervals.

Input: [(1, 5), (2, 6), (3, 7), (4, 8)]

Expected Output: 4

Explanation: All four meetings overlap around time 4.

Hints

  1. Sort meetings by start time.
  2. Use a min-heap of current room end times; if the smallest end time is <= the next start time, that room can be reused.
Last updated: May 4, 2026

Loading coding console...

PracHub

Master your tech interviews with 7,500+ real questions from top companies.

Product

  • Questions
  • Learning Tracks
  • Interview Guides
  • Resources
  • Premium
  • For Universities
  • Student Access

Browse

  • By Company
  • By Role
  • By Category
  • Topic Hubs
  • SQL Questions
  • Compare Platforms
  • Discord Community

Support

  • support@prachub.com
  • (916) 541-4762

Legal

  • Privacy Policy
  • Terms of Service
  • About Us

© 2026 PracHub. All rights reserved.

Related Coding Questions

  • Solve Flower Placement and Directory Deletion - Google (medium)
  • Compute Turnstile Crossing Times - Google (hard)
  • Simulate In-Place Cellular State Updates - Google (hard)
  • Determine Whether a Word Exists in a Graph - Google (medium)
  • Implement Checksums and Feature Rollout Evaluation - Google (medium)