Round 1
Questions:
-
Modified version of the above question:
Problem statement:
- Need to find the minimum bus changes to reach the destination from the source, with every bus running in an infinite loop.
Example 1:
- Input:
[[1,5,7],[3,6,7],[9,8,7]]
, source = 1, destination = 8 - Output: 2 (as two bus changes via interconnected nodes)
Example 2:
- Input:
[[1,5,7],[3,6,7],[9,8,7]]
, source = 1, destination = 7 - Output: 0 (as the same loop is running, so no bus change is required: 1->5->7->1)
import java.util.ArrayList; import java.util.HashMap; import java.util.LinkedList; import java.util.List; import java.util.Queue; /* * Uber interview * There is a HCV * h1 = [1,5,7][3,6,7] * source = 1 ,dest = 6; * output=1 (because 1 route is changed from row 0 to row 1) * h1 = [[1,5,7],[3,5,6],[9,7,5]] * output = 2 ((because 1 route is changed from row 0 to row 1 and from row 1 to row 2) * source = 1 ,dest = 9; */ public class BusRoute_2 { public HashMap<Integer,List<Integer>> adj ; public BusRoute_2(int mat[][]) { adj = new HashMap<>(); for(int i=0;i<mat.length;i++) { for(int x:mat[i]) { if(adj.containsKey(x)) { List<Integer> lp = adj.get(x); lp.add(i); adj.put(x,lp); } else { List<Integer> lp = new ArrayList<Integer>(); lp.add(i); adj.put(x,lp); } } } } public int minimumBusChange(int mat[][],int source,int dest) { boolean visitedRoutes[]=new boolean[mat.length]; if(source==dest) { return 0; } else if(!adj.containsKey(source)|| !adj.containsKey(dest)) { return 0; } else { Queue<Integer> q = new LinkedList<Integer>(); q.add(source); int count=0; while(!q.isEmpty()) { for(int i=0;i<q.size();i++) { int tempSource = q.poll(); for(int row:adj.get(tempSource)) { if(visitedRoutes[row]) { continue; } else { visitedRoutes[row] = true; for(int val:mat[row]) { if(val == dest) { return count; } q.add(val); } count++; } } } } } return -1; } public static void main(String[] args) { int mat[][] = {{1,2,65},{3,6,7},{4,9,7}}; BusRoute_2 ob1 = new BusRoute_2(mat); System.out.println(ob1.minimumBusChange(mat, 1,3)); } /*Time complexity:- O[m*m*k]; as k is the route of the node like 1,5,67,3,5,6 as we are traversing row every time so m*m is required for every route */ }
As I was able to solve the question, but the interviewer wanted a more optimized solution and I ended up with a brute force approach.
Candidate's Approach
The candidate implemented a solution using a breadth-first search (BFS) approach to find the minimum number of bus changes required to reach the destination from the source. The adjacency list was constructed to represent the bus routes, and the BFS was used to explore the routes while keeping track of visited routes to avoid cycles.
Interviewer's Feedback
The interviewer acknowledged the candidate's solution but expressed a desire for a more optimized approach, indicating that the current solution was too brute force.