Week 5 Live Coding Solutions
Week 5 Live Coding Solutions
Week-5 Live coding problem 1
Solution
Public Test case
Private Test case
Week-5 Live coding problem 2
Solution
Public Test Case
Private Test Case
Week-5 Live coding problem 3
Solution
Public Test case
Private Test case
Week-5 Live coding problem 1
An Airline company wants to make airport to connect n cities labeled 0 to n-1 all across the
country . Write a function Airport(distance_map) that accepts a weighted adjacency list
distance_map in the following format:-
1 distance_map = {
2 source_index : [(destination_index,distance(km)),
(destination_index,distance),..],
3 ..
4 ..
5 source_index : [(destination_index,distance),
(destination_index,distance),..]
6 }
The function returns the minimum distance of airport network to connect all n cities.
Sample input
1 7 #(number of vertices)
2 [(0,1,10),(0,2,50),(0,3,300),(5,6,45),(2,1,30),(6,4,37),(1,6,65),(2,5,76),
(1,3,40),(3,4,60),(2,4,20)] #(Edges)
Output
1 182
Solution
Solution Code
1 def kruskal(WList):
2 (edges,component,TE)=([],{},[])
3 for u in [Link]():
4 [Link]([(d,u,v) for (v,d) in WList[u]])
5 component[u] = u
6 [Link]()
7 for (d,u,v) in edges:
8 if component[u] != component[v]:
9 [Link]((u,v))
10 c = component[u]
11 for w in [Link]():
12 if component[w] == c:
13 component[w] = component[v]
14 return(TE)
15
16 def Airport(distance_map):
17 R = kruskal(distance_map)
18 S = 0
19 for e in R:
20 for ed in distance_map[e[0]]:
21 if ed[0]==e[1]:
22 S += ed[1]
23 return S
Suffix code(visible)
1 size = int(input())
2 edges = eval(input())
3 WL = {}
4 for i in range(size):
5 WL[i] = []
6 for ed in edges:
7 WL[ed[0]].append((ed[1],ed[2]))
8 WL[ed[1]].append((ed[0],ed[2]))
9 print(Airport(WL))
Public Test case
Input 1
1 7
2 [(0,1,10),(0,2,50),(0,3,300),(5,6,45),(2,1,30),(6,4,37),(1,6,65),(2,5,76),
(1,3,40),(3,4,60),(2,4,20)]
Output
1 182
Input 2
1 6
2 [(0,1,16),(0,3,2),(1,2,4),(3,4,10),(0,4,9),(3,5,15),(1,5,7),(2,5,6)]
Output
1 36
Input 3
1 4
2 [(0,1,2),(1,2,4),(0,3,3),(0,2,1),(2,3,6)]
Output
1 6
Private Test case
Input 1
1 6
2 [(0,1,1),(0,2,6),(1,2,3),(1,3,4),(2,4,4),(2,3,2),(3,4,3),(1,5,2),(2,5,7),
(3,5,1),(4,5,5)]
Output
1 9
Input 2
1 7
2 [(0,1,10),(1,2,50),(2,3,60),(3,0,75),(3,1,80),(6,4,90),(1,6,100),(2,5,110),
(3,6,150),(3,4,180),(0,4,200)]
Output
1 420
Input 3
1 6
2 [(0,1,1),(1,2,3),(1,3,4),(1,4,5),(0,4,7),(0,5,10),(2,3,12),(3,4,13),(1,5,15),
(2,5,17),(3,5,21),(4,5,25)]
Output
1 23
Week-5 Live coding problem 2
You are given a network of n nodes, labelled from 0 to n-1 . You are also given travel_times , a
list of signal travel times in as directed edges travel_times[i] = (ui, vi, wi) , where ui is
the source node, vi is the target node, and wi is the time it takes for a signal to travel from
source to target.
Write a function min_transmission_time(n, travel_times, s) that accept number of nodes n , a
list travel_times and a source node s to send the signal . The function returns the minimum
time required for the signal sent by the source node s to be received by all the remaining n-1
nodes. If it is impossible to obtain a signal for all n-1 nodes, return -1 .
Sample Input 1
1 4 #n
2 [(2,1,1),(2,3,1),(3,4,1)] #travel_times
3 2 #s
Output
1 2
Sample Input 2
1 4
2 [(2,1,1),(2,3,1),(4,3,1)]
3 2
Output
1 -1
Sample Input 3
1 7
2 [(0,1,10),(0,2,80),(1,2,6),(1,4,20),(2,3,70),(4,5,50),(4,6,5),(5,6,10)]
3 0
Output
1 86
Solution
Solution
1 def dijkstralist(WList,s):
2 infinity = 1 + len([Link]())*max([d for u in [Link]() for (v,d)
in WList[u]])
3 (visited,distance) = ({},{})
4 for v in [Link]():
5 (visited[v],distance[v]) = (False,infinity)
6
7 distance[s] = 0
8
9 for u in [Link]():
10 nextd = min([distance[v] for v in [Link]() if not visited[v]])
11 nextvlist = [v for v in [Link]() if (not visited[v]) and
distance[v] == nextd]
12 nextv = min(nextvlist)
13 visited[nextv] = True
14 for (v,d) in WList[nextv]:
15 if not visited[v]:
16 distance[v] = min(distance[v],distance[nextv]+d)
17 return(distance,infinity)
18 def min_transmission_time(n, travel_times, s):
19 AList={}
20 for i in range(n):
21 AList[i]=[]
22 for u,v,d in travel_times:
23 AList[u].append((v,d))
24 dist,inf = dijkstralist(AList,s)
25 maxtime = 0
26 for node,distance in [Link]():
27 if distance >= maxtime:
28 maxtime = distance
29 if maxtime >= inf:
30 return -1
31 else:
32 return maxtime
Suffix Code
1 n = int(input())
2 edges = eval(input())
3 s = int(input())
4 print(min_transmission_time(n, edges, s))
Public Test Case
Input 1
1 4
2 [(1,0,1),(1,2,1),(2,3,1)]
3 1
Output
1 2
Input 2
1 4
2 [(1,0,1),(1,2,1),(3,2,1)]
3 3
Output
1 -1
Input 3
1 7
2 [(0,1,10),(0,2,80),(1,2,6),(1,4,20),(2,3,70),(4,5,50),(4,6,5),(5,6,10)]
3 0
Output
1 86
Private Test Case
Input 1
1 5
2 [(0,1,1000),(0,2,500),(0,3,3000),(2,0,2000),(2,1,3000),(1,3,300),(3,4,600),
(2,4,2000)]
3 0
Output
1 1900
Input 2
1 5
2 [(0,1,1000),(0,2,500),(0,3,3000),(2,0,2000),(2,1,3000),(1,3,300),(4,3,600),
(4,2,2000)]
3 0
Output
1 -1
Input 3
1 8
2 [(0,1,1000),(0,7,800),(1,5,200),(2,1,100),(2,3,100),(3,4,300),(4,5,500),
(5,2,200),(2,4,200),(6,1,400),(6,5,100),(7,6,100)]
3 0
Output
1 1400
Input 4
1 8
2 [(0,1,1000),(0,7,800),(1,5,200),(2,1,100),(2,3,100),(3,4,300),(4,5,500),
(5,2,200),(2,4,200),(6,1,400),(6,5,100),(7,6,100)]
3 6
Output
1 -1
Input 4
1 8
2 [(0,1,1000),(0,7,800),(1,5,200),(2,1,100),(2,0,100),(1,3,300),(3,4,300),
(4,5,500),(5,2,200),(2,4,200),(6,1,400),(6,5,100),(7,6,100)]
3 2
Output
1 1000
Week-5 Live coding problem 3
An airlines company has flights operational in n cities labeled 0 to n-1 . Write a function
best_fare(flight_route, source, destination, k) in which you are given a weighted adjacency list
flight_route in the following format:-
1 flight_route = {
2 source_index : [(destination_index,price),(destination_index,price),..],
3 ..
4 ..
5 source_index : [(destination_index,price),(destination_index,price),..]
6 }
You are also given three integers source , destination and k(positive integer) , function
returns minimum cost and flight route in the format (minimum_cost, [source, next_stop,
next_stop,.., destination]) from source to destination with at most k stops in between
(source and destination are not included). If there is no such route, return string Not found .
For the given graph
Sample Input-1
1 5 # number of vertices
2 [(0,1,1000),(0,2,500),(0,3,3000),(2,0,2000),(2,1,3000),(1,3,300),(3,4,600),
(2,4,2000)] #edges
3 0 # source
4 4 # destination
5 1 # k (Maximum stops allowed in route)
Output
1 (2500, [0, 2, 4])
Sample Input-2
1 5
2 [(0,1,1000),(0,2,500),(0,3,3000),(2,0,2000),(2,1,3000),(1,3,300),(3,4,600),
(2,4,2000)]
3 0
4 4
5 0
Output
1 Not found
Solution
Prefix code(visible)
1 def addallpath(WList,u, d, visited, path,allpath):
2 visited[u]= True
3 [Link](u)
4 if u == d:
5 L = [Link]()
6 [Link](L)
7 else:
8 for i in WList[u]:
9 if visited[i[0]]== False:
10 addallpath(WList, i[0], d, visited, path, allpath)
11 [Link]()
12 visited[u]= False
13 # Following function returns a list of all paths from s to d
14 # Format of returned list:- [[s,...,d],[s,...,d],...]
15 def findallpath(WList,s,d):
16 visited = {}
17 allpath = []
18 for v in [Link]():
19 visited[v] = False
20 path = []
21 addallpath(WList,s, d, visited, path,allpath)
22 return(allpath)
Solution Code
1 def best_fare(flight_route,source,destination,k):
2 L = findallpath(flight_route,source,destination)
3 if L != []:
4 cost = 1 + len(flight_route.keys())*max([d for u in
flight_route.keys() for (v,d) in flight_route[u]])
5 route = []
6 for pth in L:
7 if len(pth) < k+3:
8 s = 0
9 for i in range(0,len(pth)-1):
10 for j in flight_route[pth[i]]:
11 if pth[i+1] == j[0]:
12 s += j[1]
13 if s < cost:
14 cost = s
15 route = pth
16 if route != []:
17 return (cost,route)
18 else:
19 return 'Not found'
20 else:
21 return 'Not found'
Prefix code(visible)
1 size = int(input())
2 edges = eval(input())
3 s = int(input())
4 d = int(input())
5 k = int(input())
6 WL = {}
7 for i in range(size):
8 WL[i] = []
9 for ed in edges:
10 WL[ed[0]].append((ed[1],ed[2]))
11 print(best_fare(WL,s,d,k))
Public Test case
Input 1
1 5
2 [(0,1,1000),(0,2,500),(0,3,3000),(2,0,2000),(2,1,3000),(1,3,300),(3,4,600),
(2,4,2000)]
3 0
4 4
5 1
Output
1 (2500, [0, 2, 4])
Input 2
1 5
2 [(0,1,1000),(0,2,500),(0,3,3000),(2,0,2000),(2,1,3000),(1,3,300),(3,4,600),
(2,4,2000)]
3 0
4 4
5 0
Output
1 Not found
Private Test case
Input 1
1 5
2 [(0,1,1000),(0,2,500),(0,3,3000),(2,0,2000),(2,1,3000),(1,3,300),(3,4,600),
(2,4,2000)]
3 2
4 4
5 2
Output
1 (2000, [2, 4])
Input 2
1 5
2 [(0,1,1000),(0,2,500),(0,3,3000),(2,0,2000),(2,1,3000),(1,3,300),(3,4,600),
(2,4,2000)]
3 0
4 4
5 2
Output
1 (1900, [0, 1, 3, 4])