How do I practice coding and algorithm questions?

Use PracHub's coding console to write, test, and debug your solutions in Python or JavaScript. View hints, test against sample inputs, and compare with official solutions.

What difficulty level is this coding question?

This is a Medium difficulty Coding & Algorithms question, commonly asked during Technical Screen rounds at Meta.

What role is this question designed for?

This question is commonly asked for Data Engineer candidates at Meta during technical interviews.

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.

Input: ([(1, 'b1', True), (2, 'b1', True)],)

Expected Output: False

Explanation: Two checkouts in a row for b1 break strict alternation.

Input: ([(4, 'b1', False), (2, 'b1', True), (10, 'b1', True), (1, 'b1', False)],)

Expected Output: False

Explanation: After sorting by timestamp the order is (1,return),(2,checkout),(4,return),(10,checkout) — it starts with a return, which is invalid.

Input: ([(1, 'a', True), (2, 'b', True), (3, 'a', False), (4, 'b', False), (5, 'a', True)],)

Expected Output: True

Explanation: Two interleaved books: a = checkout,return,checkout and b = checkout,return; each book's own sequence is independently valid.

Input: ([(1, 'a', True), (2, 'b', False)],)

Expected Output: False

Explanation: Book b's first event is a return, so even though book a is fine, the overall result is False.

Input: ([],)

Expected Output: True

Explanation: Empty log list has no invalid sequences, so it is considered valid.

Input: ([(5, 'x', True), (1, 'x', True)],)

Expected Output: False

Explanation: After sorting, x has checkout at t=1 then checkout at t=5 — two consecutive checkouts, which breaks alternation.

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.

Quick Overview

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.