Skyscanner Interview Question
Software EngineersCountry: United Kingdom
Interview Type: Written Test
i = [
'4 5 0.35',
'4 7 0.37',
'5 7 0.28',
'0 7 0.16',
'1 5 0.32',
'0 4 0.38',
'2 3 0.17',
'1 7 0.19',
'0 2 0.26',
'1 2 0.36',
'1 3 0.29',
'2 7 0.34',
'6 2 0.40',
'3 6 0.52',
'6 0 0.58',
'6 4 0.93'
]
parent = dict()
rank = dict()
def make_set(vertice):
parent[vertice] = vertice
rank[vertice] = 0
def find(vertice):
if parent[vertice] != vertice:
parent[vertice] = find(parent[vertice])
return parent[vertice]
def union(vertice1, vertice2):
root1 = find(vertice1)
root2 = find(vertice2)
if root1 != root2:
if rank[root1] > rank[root2]:
parent[root2] = root1
else:
parent[root1] = root2
if rank[root1] == rank[root2]: rank[root2] += 1
def kruskal(graph):
for vertice in graph['vertices']:
make_set(vertice)
minimum_spanning_tree = set()
edges = list(graph['edges'])
edges.sort()
for edge in edges:
weight, vertice1, vertice2 = edge
if find(vertice1) != find(vertice2):
union(vertice1, vertice2)
minimum_spanning_tree.add(edge)
return minimum_spanning_tree
v = []
edges = []
for l in i:
vs = l.split(' ')
n1,n2,w = vs[0].strip(),vs[1].strip(),float(vs[2])
if n1 not in v:
v.append(n1)
if n2 not in v:
v.append(n2)
edges.append((w,n1,n2))
graph = {
'vertices': v,
'edges': set(edges)
}
mst = kruskal(graph)
w = []
for w,a,b in sorted(list(mst)):
print a,b,w
this is minimum spanning tree problem (look for it in wikipedia).
- JB February 06, 2015Honestly, it does not really look like an interview question.