Consistent-Hash Packet Router
Updated
Problem statement
You are building the router that sends incoming network packets to backend servers. A packet is named by its source address and port, such as "192.168.1.1:8080". The same packet must always go to the same server while the set of active servers stays the same, and when servers join or leave, as few packets as possible should change servers.
Every server ID and packet identifier gets a position on a ring from a fixed hash. Start with x = 0; for each character from left to right, set x = (x * 31 + c) mod 1000000007, where c is the character's ASCII code. The final x is the position. Positions go from 0 to 1000000006 and increase clockwise, and the ring wraps from the largest position back to 0.
Examples
Example 1
servers = ["server1","server2","server3"]operations = ["ROUTE","ROUTE","ROUTE"]values = ["192.168.1.1:8080","10.0.0.5:8080","192.168.1.1:8080"]return = ["server1","server1","server1"]- The servers sit at positions
63364207,63364208and63364209. "192.168.1.1:8080"hashes to938097709and"10.0.0.5:8080"to743524288. No server is at or after either position, so both wrap to the smallest position,"server1".- The repeated packet goes to the same server again.
Unlock this recently reported problem
FastPrep Pro gives you full access to interview problems reported within the last week.
- Full problem statement and constraints
- 2 more worked examples, explained
- Guided hints and editorial
- Run your code on real test cases
$99 billed yearly — or $19 month-to-month. Cancel anytime.
More Amazon Phone Screen questions
- LRU Cache for Query ResultsPHONE SCREEN · ONSITE INTERVIEW · Seen Nov 2026
- Course SchedulePHONE SCREEN · ONSITE INTERVIEW · Seen Nov 2026
- Course Schedule IIPHONE SCREEN · ONSITE INTERVIEW · Seen Nov 2026
- Minimum Time to Spread Through a GridPHONE SCREEN · ONSITE INTERVIEW · Seen Nov 2026
- Count Connected ComponentsPHONE SCREEN · Seen Nov 2026
- Second Largest Distinct ElementPHONE SCREEN · Seen Nov 2026
- Task SchedulerOA · PHONE SCREEN · ONSITE INTERVIEW · Seen Nov 2026
- Top K Frequent ElementsOA · PHONE SCREEN · Seen Nov 2026
- Number of IslandsPHONE SCREEN · ONSITE INTERVIEW · Seen Nov 2026
- 3SumPHONE SCREEN · Seen Nov 2026
Similar questions at other companies
- Interview Slot BookingTrueFoundry · PHONE SCREEN
- Bank Accounts with Balance HistoryMeta · OAMeta interview questions
- Key-Value Store with Hit CounterDatabricks · ONSITE INTERVIEWDatabricks interview questions
- Banking System with Historical SnapshotsCoinbase · OACoinbase interview questions
- In-Memory Filesystem CommandsPerplexity AI · PHONE SCREEN · ONSITE INTERVIEWPerplexity AI interview questions
- LRU CacheServiceNow · PHONE SCREEN · ONSITE INTERVIEWServiceNow interview questions
- Mutable Points in a Hash Set and a ListMillennium · PHONE SCREENMillennium interview questions
- Snapshot Map with Sparse Version HistorySnorkel AI · PHONE SCREEN
- Rectangle Point Coverage CountsOpenAI · PHONE SCREEN · ONSITE INTERVIEWOpenAI interview questions
- File Storage ServiceCresta · PHONE SCREENCresta interview questions