Interview question of SpringWorks -EDITORIAL

DESCRIPTION

Problem Statement

Noah is a traveller who wants to travel to different places. He knows in a unique pattern between various cities. But here’s a catch, he wants to travel in a unique pattern between various cities. Since he’s having a hard time choosing the path he wants to travel, he has decided that starting from the first city (s1) he’ll move to the next city which is closest to it (s2) and then he’ll move to the next city closest to it and so on.
Given the number of paths and the closest cities, print the order in
which Noah has to travel. Assume that the city which comes first (last
line of Input) is closest to him.

Input Format

The first line is an integer which denotes the number of paths P

• The next P lines take two space separated strings s1 and s2

• The last line after P lines takes a single string as input which
denotes the city the traveller visits first

Constraints

• 1 <= P <= 100

1<= length of each string <= 100

Output Format

• The output consists of a single string in each line which denotes
the path the traveller has to travel

Note: s1 to s2 denotes a path from City A to City B but NOT from city B to city A

Evaluation Parameters

Sample Input

5

Bangalore Hyderabad

Bangalore Chennai

Hyderabad Mumbai

Hyderabad Delhi

Chennai Kerala

Bangalore

Sample Output-

Bangalore

Hyderabad

Mumbai

Delhi

Chennai

Kerala

EXECUTION TIME LIMIT

2 seconds

2 Likes

@darshancool25

@nichke

The question seems a bit unclear. For the given sample TC I don’t understand how Delhi comes after Bangalore, Hyderabad, Mumbai especially because the paths are unidirectional !!

1 Like

It is a simple preorder DFS question but instead of integer input edges we take string input edges like their is a edge between Bangalore and Hyderabad.

I don’t know how to solve it with string input edges.
If you know please provide the solution.
Hope now you will understand the question.

@darshancool25

It is a simple preorder DFS question but instead of integer input edges we take string input edges like their is a edge between Bangalore and Hyderabad.

I don’t know how to solve it with string input edges.
If you know please provide the solution.
Hope now you will understand the question

@darshancool25 @yatintripathi Please give the solution here.

Hi @yatintripathi , do have a look, I hope it covers all test cases

import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.HashSet;
import java.util.List;
import java.util.Map;
import java.util.Scanner;
import java.util.Set;

public class SpringWorks {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int path = sc.nextInt();
        List <List<String>> paths = new ArrayList<>();
        while(path > 0) {
            String temp[] = new String[2];
            temp[0] = sc.next();
            temp[1] = sc.next();

            paths.add(Arrays.asList(temp));
            path--;
        }

        String src = sc.next();
        List<String> output = getPaths(paths, src);
        System.out.println(output);
        sc.close();
    }

    private static List<String> getPaths(List<List<String>> paths, String src) {
        Map<String, ArrayList<String>> adjList = new HashMap<>();
        Set<String> lnkSet = new HashSet<>();

        paths.forEach((p) ->  {
            String s = p.get(0);
            String d = p.get(1);

            if(adjList.containsKey(s)) {
                adjList.get(s).add(d);
            } else {
                ArrayList<String> t = new ArrayList<>();
                t.add(d);
                adjList.put(s, t);
            }

            if(!lnkSet.contains(s)) lnkSet.add(s);
            if(!lnkSet.contains(d)) lnkSet.add(d);
        });

        List<String> result = new ArrayList<>();
        if(!lnkSet.contains(src)) return result;

        ArrayList<String> P = new ArrayList<>(lnkSet);

        Boolean[] visited = new Boolean[P.size()];
        Arrays.fill(visited, false);
        dfs(adjList, P, visited,src, result);

        return result;
    }

    private static void dfs(Map<String, ArrayList<String>> adjList, ArrayList<String> P, Boolean[] visited,
            String src, List<String> result) {
        int index = P.indexOf(src);
        visited[index] = true;
        result.add(src);
        ArrayList<String> nodes = adjList.get(src);
        if(nodes == null) return;
        for(String k : nodes) {
            int idx = P.indexOf(k);
            if(!visited[idx]) {
                dfs(adjList, P, visited, k, result);
            }
        }
    }
    
}

output : [Bangalore, Hyderabad, Mumbai, Delhi, Chennai, Kerala]