Route Packets with Minimal Reassignment When Servers Change

Quick Overview

Implement consistent-hash packet routing with binary-search ring lookup, deterministic collisions, wraparound, and minimal reassignment on server changes.

Route Packets with Minimal Reassignment When Servers Change

Company: Amazon

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: hard

Interview Round: Technical Screen

Implement routing from a packet identifier to an active backend server. For the same active server set, the same packet identifier must map consistently regardless of input-list order. Support adding and removing servers while minimizing changes to existing assignments. Use the reported circular-hash-space approach: hash server IDs and packet identifiers into a fixed ordered ring and route each packet to the first server position clockwise, wrapping at the end. A stable hash function is available. ### Constraints & Assumptions Treat server IDs as unique. A query with no active servers returns no server. For equal server hash positions, use server-ID order as an explicit deterministic tie-breaker. The source does not provide the hash function or require its illustrative destinations as exact test vectors. ### Clarifying Questions to Ask - Is the hash stable across processes, restarts, and languages? - How should hash collisions, an empty server set, and duplicate IDs be handled? - Is load balance required in addition to limited reassignment? ```hint Find the clockwise successor A sorted ring turns packet lookup into an insertion-position search with one wraparound case. ``` ### What a Strong Answer Covers - Stable ring construction, binary-search lookup, and exact-boundary behavior. - The intervals affected by server insertion and removal. - Collision handling, membership updates, and load-balance limitations. ### Follow-up Questions - How would virtual nodes improve balance or represent server weights? - What happens if different routers temporarily disagree on membership?

Overview: Implement consistent-hash packet routing with binary-search ring lookup, deterministic collisions, wraparound, and minimal reassignment on server changes.

Read the full Amazon Software Engineer interview experience this question came from

Amazon logo
Amazon
Nov 4, 2026
hardSoftware EngineerTechnical ScreenCoding & Algorithms
0
0

Implement routing from a packet identifier to an active backend server. For the same active server set, the same packet identifier must map consistently regardless of input-list order. Support adding and removing servers while minimizing changes to existing assignments.

Use the reported circular-hash-space approach: hash server IDs and packet identifiers into a fixed ordered ring and route each packet to the first server position clockwise, wrapping at the end. A stable hash function is available.

Constraints & Assumptions

Treat server IDs as unique. A query with no active servers returns no server. For equal server hash positions, use server-ID order as an explicit deterministic tie-breaker. The source does not provide the hash function or require its illustrative destinations as exact test vectors.

Clarifying Questions to Ask Guidance

  • Is the hash stable across processes, restarts, and languages?
  • How should hash collisions, an empty server set, and duplicate IDs be handled?
  • Is load balance required in addition to limited reassignment?

What a Strong Answer Covers Guidance

  • Stable ring construction, binary-search lookup, and exact-boundary behavior.
  • The intervals affected by server insertion and removal.
  • Collision handling, membership updates, and load-balance limitations.

Follow-up Questions Guidance

  • How would virtual nodes improve balance or represent server weights?
  • What happens if different routers temporarily disagree on membership?