Back to Roblox questions
CodingSoftware Engineer

Chat Log Window Queries

Role: Software Engineer

A multi-part progressive problem operating on a chat log represented as an array of user IDs. Each part adds a new layer on top of the previous one.

Part 1 — Subarrays Containing an Index

Given a chat_log array of user IDs, a window length n, and an index i, return all contiguous subarrays of length n that contain the element at index i.

python
def find_subarrays_with_index(
    chat_log: List[int], n: int, i: int
) -> List[List[int]]:

Example

text
chat_log = [1, 2, 3, 4, 5, 6, 7, 8],  n = 3,  i = 3

Windows of length 3 containing index 3 (value 4):
  [2, 3, 4]   (starts at index 1)
  [3, 4, 5]   (starts at index 2)
  [4, 5, 6]   (starts at index 3)

Output: [[2, 3, 4], [3, 4, 5], [4, 5, 6]]

Part 2 — Best Window for a User

Using the same valid windows as Part 1 (all length-n windows containing index i):

  • Let target_user = chat_log[i]
  • Among all valid windows, return the one with the highest count of target_user
  • Tie-breaking: if multiple windows share the max count, return the one with the smallest starting index
python
def best_subarray_for_user_at_index(
    chat_log: List[int], n: int, i: int
) -> List[int]:

Example

text
chat_log = [1, 4, 4, 4, 5, 6, 7, 8],  n = 3,  i = 3
target_user = 4

Valid windows:
  [4, 4, 4]  → count of 4: 3   ← winner
  [4, 4, 5]  → count of 4: 2
  [4, 5, 6]  → count of 4: 1

Output: [4, 4, 4]

Note: Use a sliding window to update the count incrementally in O(k) time instead of recomputing from scratch.

Part 3 — Users with Prefix Before Timestamp

Given a log of (user_id, message, timestamp) triples, a prefix string, and a cutoff_ts:

  1. Filter entries where message.startswith(prefix) and timestamp < cutoff_ts
  2. Sort by message lexicographically; break ties by timestamp ascending
  3. Return the list of user_id values in that sorted order
python
def users_with_prefix_before_timestamp(
    logs: List[Tuple[int, str, int]],
    prefix: str,
    cutoff_ts: int,
) -> List[int]:

Example

python
logs = [
    (1, "hello",       10),
    (2, "hey",          5),
    (3, "hello there",  8),
    (4, "hi",           3),
    (5, "hey",          2),
    (6, "hello",       12),
    (7, "hey there",    7),
]
prefix = "he",  cutoff_ts = 10

# After filtering (starts with "he" AND ts < 10):
#   (2, "hey", 5), (3, "hello there", 8), (5, "hey", 2), (7, "hey there", 7)
#
# After sorting by (message, timestamp):
#   "hello there" (8)  → user 3
#   "hey"         (2)  → user 5
#   "hey"         (5)  → user 2
#   "hey there"   (7)  → user 7

Output: [3, 5, 2, 7]

Constraints

  • n may exceed len(chat_log) — handle gracefully (return [])
  • i is a valid index within chat_log
  • Messages are case-sensitive for prefix matching
  • A user can appear multiple times in the output (Part 3)