Competency asserted: Logical and Maintainable
Frequency: 1
Job title: Software Development Engineer (SDE II)
Interviewer role: Software Development Engineer (SDE II)

## Problem Statement

An ordering system like Amazon’s needs to complete multiple processes to fulfil an order. Some operations cannot begin before some have completed. Due to the different types of orders that Amazon creates – retail, pantry, amazon pay, etc., the processes are dynamic, and hence an algorithm is required to do the following:

Given dependency information, create a list in which processes are sorted in the order in which they must be executed.

## Solution

Critical thinking: I would question why you need to resolve this at runtime honestly. Are the workflows changing often? If not. You can do this manually and hardcode them.

Main milestones:

• Is the candidate able to recognize this as a graph question/model the problem as a graph?
• Is the candidate able to think of topological sort/DFS?
• How is the graph modelled? Adjacency list or matrix? (a list is preferable).

Hints:

• Think about graphs. Can you think about dependencies as edges and processes as nodes of the graph?
• Which type of traversal is required – BFS vs DFS?
• Complexity?

LeetCode, Topological Sort

### Candidate 1

Vote: Mixed

The candidate managed to come up with a solution to the topological sorting problem asked with minimal help.

Although the solution he provided would work, the logic is quite hard to follow, and code itself is not very readable and maintainable. He didn’t modularize his code and created one single function.

Variables were named with one single letter (“g” for graph, “q” for “queue”), which is very confusing when reading code on a whiteboard.

When we challenged him on his choice of data structure (a vector of vector instead of a vector of pair), he said it was for ease because he “got lazy” (i.e: to save some time in writing).

While I don’t mind taking shortcuts for a whiteboard interview, I expect candidates to give us a heads-up before writing the code.