Validate alternating checkout/return logs
Company: Meta
Role: Data Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Technical Screen
Given a chronological list of events logs of the form (timestamp, book_id, is_checkout) where is_checkout is True for a checkout and False for a return, implement a validator. For each book_id, the sequence must start with a checkout, alternate strictly between checkout and return, and must never contain a return before a checkout. The function should return True if all book_id sequences are valid and False otherwise. Specify the time and space complexity.
Quick Answer: This question evaluates the ability to process sequential event logs, maintain per-entity state invariants (checkout vs return), and reason about algorithmic time and space complexity within a validation task.
You are given a list of library event logs. Each log is a tuple `(timestamp, book_id, is_checkout)`, where `is_checkout` is `True` for a checkout event and `False` for a return event.
The logs may arrive in any order, so you must first order them chronologically by `timestamp`. For each `book_id`, after ordering, the sequence of events must:
- Start with a checkout (a book cannot be returned before it has been checked out).
- Strictly alternate between checkout and return (checkout, return, checkout, return, ...).
Return `True` if every `book_id`'s ordered sequence is valid, and `False` otherwise. An empty log list is considered valid.
Example (valid):
```
[(1, 'b1', True), (2, 'b1', False), (3, 'b1', True), (4, 'b1', False)] -> True
```
Example (invalid — starts with a return):
```
[(1, 'b1', False)] -> False
```
Example (invalid — two checkouts in a row for the same book):
```
[(1, 'b1', True), (2, 'b1', True)] -> False
```
Constraints
- 0 <= number of logs <= 10^5
- Each log is a tuple (timestamp, book_id, is_checkout).
- timestamps are unique integers; logs may be given in any order.
- book_id is a string; is_checkout is a boolean.
- An empty log list is valid (returns True).
Examples
Input: ([(1, 'b1', True), (2, 'b1', False), (3, 'b1', True), (4, 'b1', False)],)
Expected Output: True
Explanation: Single book b1: checkout, return, checkout, return — a clean alternation starting with a checkout.
Input: ([(1, 'b1', False)],)
Expected Output: False
Explanation: The only event for b1 is a return with no preceding checkout, so the sequence does not start with a checkout.
Hints
- Sort the logs by timestamp first, since they can arrive out of order.
- Track, per book_id, whether the next expected event is a checkout or a return. The first expected event for any book is a checkout.
- If any event does not match the expected type for its book, the whole input is invalid. A return before any checkout is just the special case where the very first expected event (checkout) is violated.