How would you modify this solution for a very large binary tree, like a distributed system where each part of the tree is on different servers?

Interviewee: For a distributed system, we’d need to divide the tree into parts and process each part concurrently. Each server could handle traversal for its subtree and communicate the results back to a central system that aggregates the level order lists.

We’d also need to ensure proper synchronization between servers, as they may finish processing at different times. A message-passing system or a distributed queue could help manage the traversal between different parts of the tree.

Interviewer: Interesting. How would you handle balancing the workload across servers?

Interviewee: I would start by distributing the workload based on tree size. We could estimate the number of nodes in each subtree and allocate more resources to larger subtrees. Alternatively, we could divide the tree breadth-wise, so each level of the tree is handled independently by different servers, which might better distribute the workload.

Interviewer: That’s a good approach. One final question—how would you handle errors in a distributed system like this, such as a server going down?

Interviewee: If a server goes down, we could implement retries for the part of the tree that server was processing. We’d keep track of which nodes have been processed and which haven’t, so that another server could take over the failed part. We could also store the state of each server periodically so that in case of failure, recovery would be easier.

Alex Xu의 시스템 디자인 인터뷰 책이나 Grokking the system design interview 보시길 바랍니다. 앞 뒤 다 자르고, 저 위처럼 대답하면 떨어질 확률 높습니다. 이유는 저 두 곳에 잘 설명 되어 있습니다. 물론, 인터뷰어가 잘 봐 주면 다른 얘기지만.

음… 이건 단순히 맞고 틀리고로 나뉘는게 아니죠. 정답이 있는게 아니라 대답하는 사람의 수준과 생각하는 능력을 보는겁니다. 그래서 매번 대답에 덧붙여서 계속 이런 저런 질문을 이어가는겁니다.

답변의 수준을 평가하자면, 그리 깊은 수준은 아닙니다. 매우 high-level에 머물러 있습니다. 고민하거나 고려해야할 것들에 대한 얘기들도 별로 없지요. 경험없는 일반 학부 new grad라면 이 정도일 수도 있겠습니다만, 뭔가 다루어 봤다면 조금은 다른 대답이 있을 수도 있겠죠.

간단한 예를 들겠습니다. 트리를 분산 처리한다고 할 때, 균일하게 topology 따라 고정된 형태로 나누는 얘기만 했는데, 어떤 종류의 작업인지에 따라 어떤 리소스가 중요하고 어떤 부분이 시간이 걸리는지 달라지죠. 그런 개념이 있다면 질문을 하거나 대답을 하며 assumption을 얘기하며 대답을 이어갈겁니다. 생각해보세요. 트리 데이타가 모두 in-memory냐, I/O가 필요하냐에 따라서도 많이 달라지죠. 그리고 그냥 search/scan이냐, 아니면 어떤 computation이 병행되느냐도 영향을 미칩니다. 경험과 아는 정도에 따라 고려할 수 있는 것은 무궁무진합니다.

학부 new grad라면 대단한 답변은 아니더라도, 뭔가 생각하고 고민하고 만들어가는 모습을 보여주는게 좋습니다.