## Skyscanner Interview Question for Software Engineers

Country: United Kingdom
Interview Type: Written Test

Comment hidden because of low score. Click to expand.
1
of 1 vote

this is minimum spanning tree problem (look for it in wikipedia).

Honestly, it does not really look like an interview question.

Comment hidden because of low score. Click to expand.
0

It is hackerRank online test question, it's screening test before interview

Comment hidden because of low score. Click to expand.
0
of 0 vote

I think Floyd Warshall Algo should work

Comment hidden because of low score. Click to expand.
0
of 0 vote

Dude,,,,I have exact the same 3 questions as yours, the first two is easy while this one I have no idea...

Comment hidden because of low score. Click to expand.
0
of 0 vote

Could you explain how to solve this? I am new to this kind of algorithms, thank you very much

Comment hidden because of low score. Click to expand.
0
of 0 vote

Could you please explain how you would solve that? Thank you in advance!

Comment hidden because of low score. Click to expand.
0
of 0 vote

Could someone provide an example for the solution?

Comment hidden because of low score. Click to expand.
0
of 0 vote

The problem screams Dijkstra - the most common shortest path algorithm. There are numerous examples you can find.

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````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)
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``````

Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

### Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

### Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.

### Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

### Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.