I recently had an Amazon SDE II phone interview. The coding question involved routing incoming network packets to backend servers.
The initial problem was to write a function that takes a list of active server IDs and a packet identifier, such as a source IP address and port, and returns the server ID that should handle that packet. With the same set of active servers, the same packet identifier should consistently map to the same server.
The interviewer gave examples like these:
servers = ["server1", "server2", "server3"]
"192.168.1.1:8080" → "server3"
"10.0.0.5:8080" → "server1"
"192.168.1.1:8080" → "server3"
After I asked clarifying questions, the interviewer explained that servers could be added or removed dynamically. Whenever that happened, the algorithm should minimize the number of packet identifiers reassigned to different servers.
For example, adding server4 should allow it to receive traffic while preserving as many existing assignments as possible. Removing server3 should redirect its traffic to the remaining servers while minimizing disruption to other assignments.
We agreed that a hash function could be assumed to be available, so I could focus on the routing logic and handling changes to the server set.
My approach placed servers and packet identifiers in a fixed circular hash space, then searched for a server. I finished writing the solution, but I was rushing and did not have enough time to properly dry-run and debug it. Looking back, the implementation had quite a few bugs. Near the end, he asked what I would improve with more time, and I mentioned binary search to optimize the server lookup.
The question felt very specific to the team because the interviewer mentioned that this was related to the work he actually does. At the end of the interview, he recommended that I look up consistent hashing.
Discussion
Loading comments…