Implement a class called AirMap that has two methods:
1. add_route(start, destination) - adds ONE WAY connecting flight from one airport to another
2. print_all_routes(start, destination) - prints all possible routes from start to destination

Given the following routes, print all possible routes between the airport C and D:
A ----- B
B ----- A
A ----- C
C ----- A
A ----- D
D ----- A
B ----- C
C ----- B
B ----- D
D ----- B
Expected Output:
C,A,B,D
C,A,D
C,B,A,D
C,B,D

Question

Implement a class called AirMap that has two methods:
1. add_route(start, destination) - adds ONE WAY connecting flight from one airport to another
2. print_all_routes(start, destination) - prints all possible routes from start to destination

Given the following routes, print all possible routes between the airport C and D:
A -----> B
B -----> A
A -----> C
C -----> A
A -----> D
D -----> A
B -----> C
C -----> B
B -----> D
D -----> B
Expected Output:
C,A,B,D
C,A,D
C,B,A,D
C,B,D

Something along these lines · Accepted Answer

class AirMap{
  Map> routeMap;
  AirMap(){
    routeMap = new HashMap();
  }
  public void add_route(String start, String dest){
    List routes = routeMap.getOrDefault(start , new ArrayList());
    routes.add(dest);
    routeMap.put(start , routes);
  }
  public List> get_routes(String start , String dest){
    List> results = new ArrayList();
    List result = new ArrayList();
    dfs_helper(start , dest , result , results);
    return results;
  }
  public void printMap(){
    System.out.println(routeMap.toString());
  }
  public void dfs_helper(String start , String dest, List result , List> results){
    if(routeMap.containsKey(start)){
      List iter = routeMap.get(start);
      for(String s : iter){
        result.add(start + " -> " + s);
        if(s.equals(dest)){
          results.add(new ArrayList(result));
        }
        dfs_helper(s , dest, result, results);
        result.remove(result.size() - 1);
      }
    } 
  }
}

Sigiloso · Answer

You had to represent the data in and adjacency list for instance and perform the traversal algorithm over the list.

Sigiloso · Answer

class AirMap:
    def __init__(self):
        self.route_map = {}

    def add_route(self, start, destination):
        if start in self.route_map:
            self.route_map[start].append(destination)
        else:
            self.route_map[start] = [destination]

    def print_all_routes(self, start, destination):
        q = [start]
        res = []

        def dfs(queue, visited):
            while queue:
                airport = queue.pop()
                if airport == destination:
                    res.append(list(visited))

                if airport not in visited:
                    visited.append(airport)

                for ap in self.route_map.get(airport, []):
                    if ap in visited:
                        continue
                    queue.append(ap)
                    visited.append(ap)
                    dfs(queue, visited)

                    visited.remove(ap)

        dfs(q, [])
        return res

Bloomberg

Pergunta de entrevista da empresa Bloomberg

Respostas da entrevista

Empresas seguidas

Buscas de vagas