CareerCup

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

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

I think Floyd Warshall Algo should work

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

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

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

Could someone provide an example for the solution?

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

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