In coding interviews, writing a correct solution is only part of the evaluation. Interviewers also expect you to explain its efficiency clearly and justify why it meets the problem constraints.
Suppose you implemented a solution that scans a list of Greenhouse Recruiting candidate IDs and uses a hash map to detect whether any ID appears more than once. Explain the time complexity of your solution.
Address these points:
You do not need to derive formal proofs, but you should give a precise interview-level explanation. A strong answer should distinguish average-case vs worst-case behavior and connect the complexity to the number of input elements.
Big-O describes how runtime or memory grows as input size increases. In interviews, it is used to communicate scalability rather than exact execution time.
for candidate_id in candidate_ids:
# one pass over n items
pass
If a solution processes each element once, the runtime is typically linear in the number of elements. The key question is whether each iteration does constant-time work or something more expensive.
for candidate_id in candidate_ids:
if candidate_id in seen:
return True
seen.add(candidate_id)
Hash tables usually provide average O(1) lookup and insertion. That assumption is what allows a one-pass duplicate check to remain O(n) overall instead of O(n^2).
seen = set()
# membership and insert are average O(1)
Although hash operations are average O(1), pathological collisions can degrade performance. A strong answer should mention that worst-case behavior can be worse even if average-case is the expected interview answer.
Space complexity measures extra memory used beyond the input. If you store up to all seen elements in a hash set, the extra space grows linearly with input size.
seen = set() # may store up to n candidate IDs
