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

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

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.