Amazon | SDE-2 | Weird Experience

1/25/2025

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

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.