Resource Transition Graph
Problem statement
You are given logs. Each entry [timestamp, userId, resourceId] says that a user opened a resource at that time. The timestamp is a whole number of seconds, given as a string.
Build the transition graph that shows how users move from one resource to the next:
- Sort each user's logs by timestamp, comparing timestamps as numbers. The user's path is
START, then the user's resources in that order, thenEND. - Every two neighbors on a path make one step. A resource can be followed by itself.
- For a state
s(STARTor a resource), the probability of going totis the number of steps fromstot, over all users, divided by the number of steps that leaves.
Return one row [s, t, probability] for every pair s, t with at least one step. END is where paths stop, so it never appears in the first column.
- Round each probability to three decimal places and write it with exactly three digits after the point, such as
"1.000"or"0.333". A value exactly halfway rounds up:0.0625becomes"0.063". - Sort the rows by the first column, then by the second, comparing strings by character code. So
STARTandEND, which start with capital letters, come before resource IDs.
Function
transitionGraph(logs: String[][]) → String[][]Examples
Example 1
logs = [["58523","user_1","resource_1"],["62314","user_2","resource_2"],["54001","user_1","resource_3"],["200","user_6","resource_5"],["215","user_6","resource_4"],["54060","user_2","resource_3"],["53760","user_3","resource_3"],["58522","user_22","resource_1"],["53651","user_5","resource_3"],["2","user_6","resource_1"],["100","user_6","resource_6"],["400","user_7","resource_2"],["100","user_8","resource_6"],["54359","user_1","resource_3"]]return = [["START","resource_1","0.250"],["START","resource_2","0.125"],["START","resource_3","0.500"],["START","resource_6","0.125"],["resource_1","END","0.667"],["resource_1","resource_6","0.333"],["resource_2","END","1.000"],["resource_3","END","0.400"],["resource_3","resource_1","0.200"],["resource_3","resource_2","0.200"],["resource_3","resource_3","0.200"],["resource_4","END","1.000"],["resource_5","resource_4","1.000"],["resource_6","END","0.500"],["resource_6","resource_5","0.500"]]Sorted by time, user_6 visits resource_1 (time 2), resource_6 (100), resource_5 (200) and resource_4 (215). The times are compared as numbers, so "2" comes before "100".
Eight users each start somewhere: 4 of them at resource_3, 2 at resource_1, 1 at resource_2 and 1 at resource_6. So START goes to resource_3 with probability 4/8 = 0.500.
resource_3 is left 5 times: twice to END, and once each to resource_1, resource_2 and resource_3 itself (user_1 opens it twice in a row). That gives 0.400 and three times 0.200. resource_1 is left 3 times: once to resource_6 (1/3 rounds to 0.333) and twice to END (2/3 rounds to 0.667).
Example 2
logs = [["30","amy","home"],["5","bob","home"],["12","amy","search"],["40","bob","cart"],["9","amy","home"]]return = [["START","home","1.000"],["cart","END","1.000"],["home","END","0.333"],["home","cart","0.333"],["home","search","0.333"],["search","home","1.000"]]amy visits home, search, home, and bob visits home, cart. home is left three times, once each to END, cart and search, so each gets 1/3, which is 0.333. The rounded values do not have to add up to exactly 1.
Rows are sorted by the first column, then the second. START and END start with capital letters, so they sort before the small-letter resource IDs.
Example 3
logs = [["10","u0","a"],["11","u1","a"],["12","u2","a"],["13","u3","a"],["14","u4","a"],["15","u5","a"],["16","u6","a"],["17","u7","a"],["18","u8","a"],["19","u9","a"],["20","u10","a"],["21","u11","a"],["22","u12","a"],["23","u13","a"],["24","u14","a"],["25","u15","b"]]return = [["START","a","0.938"],["START","b","0.063"],["a","END","1.000"],["b","END","1.000"]]Sixteen users each make one visit: 15 go to a and 1 goes to b. So START goes to a with probability 15/16 = 0.9375 and to b with 1/16 = 0.0625. Both end in a 5, so they round up to 0.938 and 0.063.
Constraints
1 <= logs.length <= 1000logs[i].length == 3- Each
timestampis a whole number from 0 to 10^9, written without leading zeros. - Each
userIdandresourceIdhas 1 to 20 characters, all small letters, digits or underscores, and starts with a small letter. - At most 20 different resource IDs appear in
logs. - No user has two logs with the same timestamp.