Screening Round
Questions:
- Leadership Principle Questions: Two LP questions were asked, and the candidate blended their experience into the answers.
- Graph Question:
Given connections between different cities & some of them are data centers. Return the city with the farthest network connection to any data center possible.
- Example provided:
connections: [(a,b);(b,c);(c,d);(d,e);(f,g);(g,e)] dataCenters: [a,f]
- Explanation of the example:
a - b - c - d - e - g - f (Cities) 0 - 1 - 2 - 3 - 2 - 1 - 0 (Distance from nearest data center)
- Expected output:
d
- Example provided:
Candidate's Approach
The candidate approached the problem using a Multi-source BFS method. They explained that there could be multiple cities that are farthest from the data centers, providing a modified example to illustrate this point. They coded the solution while explaining their process, ensuring to clarify that the graph is strongly connected.
The candidate's code was as follows:
vector<char> getFarthestCities(vector<vector<char>> connections, vector<char> dataCenters) { unordered_map<char,vector<char>> edges; for (auto connection : connections) { edges[connection[0]].push_back(connection[1]); edges[connection[1]].push_back(connection[0]); } vector<int> dist(edges.size(),INT_MAX); queue<pair<int,int>> q; for (auto dc : dataCenters) { q.push({dc-'a',0}); } // Loop-1 while (!q.empty()) { auto current = q.front(); q.pop(); char city = current.first+'a'; int distance = current.second; // Loop-2 for (auto neighbour : edges[city]) { if (dist[neighbour-'a']>1+distance) { dist[neighbour-'a']=1+distance; q.push({neighbour-'a', 1+distance}); } } } int maxDist=*max_element(dist.begin(),dist.end()); vector<char> farthestCities; int s=dist.size(); // Loop-3 for (int i=0;i<s;i++) { if (dist[i]==maxDist) { farthestCities.push_back(i+'a'); } } return farthestCities; }
The candidate dry ran the example and explained every step of the code.
Interviewer's Feedback
The interviewer provided positive feedback for the Leadership Principles but noted negative feedback regarding technical skills, mentioning there are gaps in the candidate's technical skills.