Build a Resource Transition Probability Graph from Unsorted Access Logs

Given an unsorted list of web-resource access logs, build a directed transition graph and return the outgoing transition probabilities for each source state. Each log is a three-element record `[time, user_id, resource_id]`. Time is a string containing the number of seconds since midnight; all logs are from the same day. Put each user's visits in chronological order and treat that user's observed visits as one path from `START` through the resources to `END`. Implement `transition_graph(logs)` to return an adjacency mapping: each source state maps to its possible next states and their numeric transition probabilities. Include `START` and each visited resource as source states; `END` is terminal and must not be a source state. ### Transition Rules - Each user contributes one transition from `START` to their first resource. - Each pair of consecutive visits by the same user contributes one resource-to-resource transition. Consecutive visits to the same resource count as a self-transition; do not collapse them. - Each user contributes one transition from their last resource to `END`, including users with only one visit. - For a source state, an outgoing edge's probability is its transition count divided by the total number of transitions leaving that state across all users. - Count transition occurrences, not just distinct users or distinct edges. A user who visits a resource several times may contribute several outgoing transitions from it. ### Input and Output - Resource and user identifiers are strings. Compare timestamps numerically, not lexicographically. Return count ratios without rounding; decimal values shown in examples are approximate. Mapping order does not matter. - For this practice version, times are valid integer seconds from 0 through 86,399; resource IDs do not equal the reserved labels `START` or `END`; and visits by the same user at an equal timestamp retain their input order. These conventions settle details the source report did not specify. - For empty input, return `{"START": {}}`. Each log record represents a visit, including a record that repeats another record. ### Example 1 — Interleaved Users and Repeated Visits ```text logs = [ ["200", "user_1", "resource_5"], ["3", "user_1", "resource_1"], ["620", "user_1", "resource_1"], ["620", "user_3", "resource_1"], ["34", "user_6", "resource_2"], ["95", "user_9", "resource_1"], ["416", "user_6", "resource_1"], ["58523", "user_3", "resource_1"], ["53760", "user_3", "resource_3"], ["58522", "user_22", "resource_1"], ["100", "user_3", "resource_6"], ["400", "user_6", "resource_2"] ] ``` The result is shown with exact fractions where a decimal representation would repeat: | Source | Outgoing probabilities | |---|---| | `START` | `resource_1`: 3/5; `resource_2`: 1/5; `resource_6`: 1/5 | | `resource_1` | `END`: 5/7; `resource_3`: 1/7; `resource_5`: 1/7 | | `resource_2` | `resource_1`: 1/2; `resource_2`: 1/2 | | `resource_3` | `resource_1`: 1 | | `resource_5` | `resource_1`: 1 | | `resource_6` | `resource_1`: 1 | ### Example 2 — Single-Visit Users and a Self-Transition ```text logs = [ ["1", "user_96", "resource_5"], ["1", "user_10", "resource_5"], ["301", "user_11", "resource_5"], ["301", "user_12", "resource_5"], ["603", "user_12", "resource_5"], ["1603", "user_12", "resource_7"] ] result = { "START": {"resource_5": 1.0}, "resource_5": {"END": 0.6, "resource_5": 0.2, "resource_7": 0.2}, "resource_7": {"END": 1.0} } ``` Let `n` be the number of log entries when describing time and auxiliary-space complexity.