Last Updated: 21 Apr, 2021
Exploring Restaurants
Moderate
Asked in company
Rohan got his new girlfriend. So he has to take her to a restaurant for a date. Rohan is confused about taking her to a safe and sound restaurant. So, he asked her girlfriend for suggestions.
Rohan’s girlfriend got a map in which she has marked ‘N’ safe points having unique id ‘I’ (ranging from 0 to N - 1).
The safe points are placed on the map at different levels. Each level can have one or more safe points and at the same time, each safe point can have one or more restaurants.
Safe points have roads connecting them. Rohan’s girlfriend points to the safe point with id = ‘I’ and a level ‘L’
Rohan has to take the names of the restaurants which were present in the Lth level safe point from the marked safe point having id = ‘I’ (but having roads connecting them with the pointed safe point).
Your task is to help Rahul in making the list of restaurants.
Note :
The list should be in the order of increasing frequency of restaurant name. If the frequency of restaurants is the same then order them in alphabetical order.
Input Format
The first line contains an integer ‘T’, which denotes the number of test cases or queries to be run. Then the test cases are as follows.
The first line of each test case contains an integer ‘N’ denoting the number of safe points.
The next alternate ‘N’ lines contain integer ‘X’ denoting the number of strings in a single array followed by space-separated strings denoting the restaurant names.
The next alternate ‘N’ lines contain integer ‘Y’ denoting the number of integers in a single array followed by space-separated integers denoting the link between the safe points.
Last line contains two space-separated integers “Id” and “level” (separated by space).
Output Format
For each test case, print a single containing space-separated strings denoting the restaurant names.
The output of each test case will be printed in a separate line.
Note:
You don’t need to print anything, It has already been taken care of. Just implement the given function.
Constraints
1 <= T <= 10
2 <= N <= 20
1 <= restaurants[i].length OR (‘X’) <= 10
1 <= restaurants[i][j].length <= 8
0 <= safePoints[i].length OR (‘Y’) < N
0 <= safePoints[i][j] < N
0 <= id < N
1 <= level < N
Where ‘T’ denotes the number of test cases, ‘N’ denotes the number of safe points, ‘i’ and ‘j’ denote the ith and jth index respectively.
Time limit: 1 sec.
Approaches
The approach is to use Breadth-First Search of the safePoints array (which denotes all the connections between safe points). First, we will insert the given “Id” in the queue “bfsQueue”(which will be used for bfs) and will continue to add its neighbors in the queue through iteration. At every new step, we will increment our counter “currentLevel” and break the iteration when this counter “currentLevel” will be equal to the given Level.
After this, we will be at the required level. Now we will generate a map “bfsMap” in which we will store the restaurant’s name (of the required safePoints) along with the frequency.
Now we will simply sort the names of the restaurants with their frequencies.
Algorithm -
- First, we will make a queue ”bfsQueue” for bfs and a visited array(visited) of size ‘N’ (size of “safePoints”) and create an array of strings “ans” in which we will store the result.
- We will then push the given “id” of the “safePoints” in the queue and mark it visited in the visited array
- While “bfsQueue” is not empty,
- We then iterate over the queue’s top index of the “safePoints” array and push the elements into “bfsQueue” if not visited.
- We will increment “currentLevel” at every full iteration of the index.
- The iteration will be until our counter “currentLevel” will not become equal to “Level”.
- Break the iteration.
- Now “bfsQueue” will contain the required safe points for which we need the restaurants.
- Now create a map “bfsMap”, and iterate over the indices (from the “bfsQueue”) of the restaurants array and insert the strings along with their frequencies.
- Now to sort the frequencies stored in the “ans”:
- Check if the frequency of strings are equal, then sort in lexicographically order
- Else sort according to frequency.
- Return “ans”.