3 Short DSA analysis questions from the same thread
Here is the question I got for the coding part.
"""
Suppose we have an unsorted log file of accesses to web resources. Each log entry consists of an access time, the ID of the user making the access, and the resource ID.
The access time is represented as seconds since 00:00:00, and all times are assumed to be in the same day.
Write a function that takes the logs as input, builds the transition graph and returns it as an adjacency list with probabilities. Add
START
and
END
states.
Specifically, for each resource, we want to compute a list of every possible next step taken by any user, together with the corresponding probabilities. The list of resources should include
START
but not
END
, since by definition
END
is a terminal state.
Examples:
logs1 = [
["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"],
]
logs2 = [
["357", "user", "resource_2"],
["1262", "user", "resource_1"],
["1462", "user", "resource_2"],
["1060", "user", "resource_1"],
["756", "user", "resource_3"],
["1090", "user", "resource_3"],
]
logs3 = [
["300", "user_10", "resource_5"],
]
logs4 = [
["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"],
]
logs5 = [
["300", "user_1", "resource_3"],
["599", "user_1", "resource_3"],
["900", "user_1", "resource_3"],
["1199", "user_1", "resource_3"],
["1200", "user_1", "resource_3"],
["1201", "user_1", "resource_3"],
["1202", "user_1", "resource_3"]
]
Expected output for logs1:
transition_graph(logs1) # =>
{
'
START
': {'resource_1': 0.6, 'resource_2': 0.2, 'resource_6': 0.2},
'resource_1': {'
END
': 0.71, 'resource_3': 0.14, 'resource_5': 0.14},
'resource_2': {'resource_1': 0.5, 'resource_2': 0.5},
'resource_3': {'resource_1': 1.0},
'resource_5': {'resource_1': 1.0},
'resource_6': {'resource_1': 1.0}
}
user_1 -> resource_1
user_9 -> resource_1
user_22 -> resource_1
user_3 -> resource_6
user_6 -> resource_2
resource_1 -> 3/5 = 0.6
resource_6 -> 1/5 = 0.2
resource_2 -> 1/5 = 0.2
For example, of 5 total users, 3 users have resource_1 as a first visit (user_1, user_9, user_22), 1 user has resource_6 as a first visit (user_3), and 1 user has resource_2 as a first visit (user_6), so the possible next steps for
START
are resource_1 with probability 3/5, resource_2 with probability 1/5, and resource_6 with probability 1/5.
These are the resource paths per user for the first logs example, ordered by access time:
{
'user_1': ['resource_1', 'resource_5', 'resource_1'],
'user_3': ['resource_6', 'resource_1', 'resource_3', 'resource_1'],
'user_6': ['resource_2', 'resource_2', 'resource_1'],
'user_9': ['resource_1'],
'user_22': ['resource_1'],
}
Expected output for logs2:
transition_graph(logs2) # =>
{
'
START
': {'resource_2': 1.0},
'resource_1': {'resource_2': 0.5, 'resource_3': 0.5},
'resource_2': {'
END
': 0.5, 'resource_3': 0.5},
'resource_3': {'resource_1': 1.0}
}
Expected output for logs3:
transition_graph(logs3) # =>
{
'
START
': {'resource_5': 1.0},
'resource_5': {'
END
': 1.0}
}
Expected output for logs4:
transition_graph(logs4) # =>
{
'
START
': {'resource_5': 1.0},
'resource_5': {'
END
': 0.6, 'resource_5': 0.2, 'resource_7': 0.2},
'resource_7': {'
END
': 1.0}
}
Expected output for logs5:
transition_graph(logs5) # =>
{
'
START
': {'resource_3': 1.0},
'resource_3': {'
END
': 0.14, 'resource_3': 0.86}
}
All Test Cases:
transition_graph(logs1)
transition_graph(logs2)
transition_graph(logs3)
transition_graph(logs4)
transition_graph(logs5)
Complexity analysis variables:
n: number of logs in the input
"""
logs1 = [
["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"],
]
logs2 = [
["357", "user", "resource_2"],
["1262", "user", "resource_1"],
["1462", "user", "resource_2"],
["1060", "user", "resource_1"],
["756", "user", "resource_3"],
["1090", "user", "resource_3"],
]
logs3 = [
["300", "user_10", "resource_5"],
]
logs4 = [
["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"],
]
logs5 = [
["300", "user_1", "resource_3"],
["599", "user_1", "resource_3"],
["900", "user_1", "resource_3"],
["1199", "user_1", "resource_3"],
["1200", "user_1", "resource_3"],
["1201", "user_1", "resource_3"],
["1202", "user_1", "resource_3"]
]
'''
group accesses ussers
ssort each usserss''access by TimeoutError#
hashmap key --> usesr]
value --> [time, resource
users ={}
users[]
graph = {}
key: ressource (dict)
value -> prob
cnt how often each transition occurs
cnvrt these cnts into probas
'''
def solution(logs):
# define users -> [(time, resource)]
users = {}
for time, user, resource in logs:
if user not in users:
users[user] = []
users[user].append((int(time), resource))
# from_resouce -> {to: cnt}
cnts ={}
for user in users:
users[user].sort()
rscs =[]
for time, resource in users[user]: # extracting resource again
rscs.append(resource)
# initialize START --> resource 1
first = rscs[0]
# initialize START in the dictionary
if "
START
" not in cnts:
cnts["
START
"] = {}
if first not in cnts["
START
"]:
cnts["
START
"][first] = 0 # initialize the first resouce as value
cnts["
START
"][first] += 1
# resource --> next ressources basically
for i in range(len(rscs) - 1):
curr, nxt = rscs[i], rscs[i + 1]
if curr not in cnts:
cnts[curr] = {} # initialize dict
if nxt not in cnts[curr]:
cnts[curr][nxt] = 0
print(cnts[curr][nxt]
cnts[curr][nxt] += 1 # same thing as START
last = rscs[-1]
if last not in cnts:
cnts[last] ={}
if "
END
" not in cnts[last]:
cnts[last]["
END
"] = 0
cnts[last]["
END
"] += 1
# cvrt to probas
# define a transition_graph
graph = {}
print(cnts)
for resource in cnts:
# prob = cnts/tta
graph[resource] = {} #nested dict
total = sum(cnts[resource].values())
#print(total)
for nxt in cnts[resource]:
graph[resource][nxt] = cnts[resource][nxt]/ total
#print(cnts[resource][nxt])
#print(cnts[resource][nxt]/ total)
return graph
'''
logs1 = [
["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"],
]
Expected output for logs1:
transition_graph(logs1) # =>
{
'
START
': {'resource_1': 0.6, 'resource_2': 0.2, 'resource_6': 0.2},
'resource_1': {'
END
': 0.71, 'resource_3': 0.14, 'resource_5': 0.14},
'resource_2': {'resource_1': 0.5, 'resource_2': 0.5},
'resource_3': {'resource_1': 1.0},
'resource_5': {'resource_1': 1.0},
'resource_6': {'resource_1': 1.0}
} '''
print(solution(logs1))
Discussion
Loading comments…