Panda Guru LogoPanda
Guru

UBER SENIOR SOFTWARE ENGINEER

Round 1

Questions:

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.