Quick Overview

This question evaluates string parsing and data-extraction skills alongside set/array-based aggregation and algorithmic reasoning for calendar availability and time-window constraints.

Parse strings and find meeting slots

Company: Google

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Onsite

##### Question Given a text file where each line contains raw information, extract the user identifier and the numeric quantity on that line and store the results efficiently. Given multiple people's calendars (each as a list of available days), return the days when everyone is available for a meeting. Follow-ups: (a) return the days when at least P people are available; (b) given an integer X, return time periods of consecutive days of length X when the availability condition holds.

Overview: This question evaluates string parsing and data-extraction skills alongside set/array-based aggregation and algorithmic reasoning for calendar availability and time-window constraints.

You are given two inputs: (1) lines: a list of strings, each containing exactly one user identifier and exactly one signed integer; (2) calendars: a dictionary mapping user names to a list of integers representing the days that user is available. A user identifier in a line matches the pattern '@' followed by one or more characters from [A-Za-z0-9_]. Extract the user name (without the leading '@') and the integer from each line and compute the sum of integers per user. For the calendars, compute the set of days on which at least p users are available (duplicates within a user's list count once). Then, given an integer x, return all contiguous periods [start, end] of exact length x such that every day in [start, end] is in that set of days. Return a dictionary with: user_sums (mapping user->sum), days (sorted list of days with at least p users), and periods (sorted list of [start, end] segments of length x where availability condition holds).

Constraints

  • 1 <= len(lines) <= 200000
  • Each line contains exactly one user identifier of the form '@[A-Za-z0-9_]+' and exactly one signed integer (e.g., -7, +3, 42)
  • 1 <= len(calendars) <= 100000
  • Let T be the total number of day entries across all users in calendars; 0 <= T <= 200000
  • Day values are integers in [1, 10^9]
  • Duplicates in a single user's day list are allowed but count once for that user
  • 1 <= p <= len(calendars)
  • 1 <= x <= 10^6
  • Output 'days' must be sorted ascending without duplicates
  • Output 'periods' must be sorted by start ascending; each period is [start, end] inclusive with end = start + x - 1

Hints

  1. Use a regular expression to extract '@username' and the (signed) integer from each line; strip the leading '@' from the username.
  2. Aggregate per-user sums in a dictionary for O(1) average updates.
  3. Convert each user's availability list to a set to remove duplicates before counting days.
  4. Count availability per day across users, then collect days with count >= p and sort them.
  5. Scan the sorted valid days to find consecutive runs and emit all length-x windows within each run.

Loading coding console...

Show the approach

Approach

Parse each line using two regular expressions: one to capture '@username' and one for the signed integer. Aggregate per-user sums in a dictionary. For calendars, treat each user's list as a set to avoid counting duplicate days. Build a count map from day to number of users available, then collect days with count >= p and sort them. To produce periods of length x, scan the sorted valid days to find maximal consecutive runs. For a run of length L, there are L - x + 1 windows of size x; emit each as [start, start + x - 1].

Time complexity:
O(L + T + D log D + W), where L = number of lines, T = total day entries across calendars, D = number of distinct days with at least one available user, and W = number of output windows
Space complexity:
O(U + D), where U = number of distinct users seen in lines and D = number of distinct days across calendars