FastPrepResource Transition Graph
Problems/Resource Transition Graph

Resource Transition Graph

Indeed logoIndeed● MediumFULLTIMEPHONE SCREEN
QuestionFunctionExamplesConstraints

Problem statement

Source note: In the third coding question of a Karat interview, whose text the author later shared, user access logs become move probabilities between resources, with a START step before each user's first visit and an END step after their last. Example 1 is the report's own sample.

The report does not say how to round, what shape the answer has, or what to do when one user has two logs at the same time. Its sample shows three decimals, such as 0.333 and 0.667. Here, you return sorted rows of [from, to, probability], and each probability is rounded half up and written with exactly three digits, so 1.0 becomes 1.000. No user has two logs at the same time, and the size limits are practice choices.

The judged task matches the report at about 90%.

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, then END.
  • Every two neighbors on a path make one step. A resource can be followed by itself.
  • For a state s (START or a resource), the probability of going to t is the number of steps from s to t, over all users, divided by the number of steps that leave s.

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.0625 becomes "0.063".
  • Sort the rows by the first column, then by the second, comparing strings by character code. So START and END, 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 <= 1000
  • logs[i].length == 3
  • Each timestamp is a whole number from 0 to 10^9, written without leading zeros.
  • Each userId and resourceId has 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.

More Indeed problems

  • Insert into an Unrolled Linked ListPHONE SCREEN · ONSITE INTERVIEW · Seen Sep 2026
  • Course Completion OrderPHONE SCREEN · Seen May 2025
  • Recipes You Can PreparePHONE SCREEN · Seen May 2025
All Indeed interview questionsSee Indeed hiring insights
Saved
class Solution {
    public String[][] transitionGraph(String[][] logs) {
        // Write your code here.
    }
}
Checking account…