Packet Reordering

Data Structures System Design Algorithms

You are tasked with designing and implementing a class to handle out-of-order network packets. Each packet is identified by an integer sequence number and carries a payload (assume it is a string). Packets may arrive out-of-order, and the system needs to return them in the correct sequence order (starting at 1).

Your class should support at least the following operations:

  1. add_packet(sequence_number, payload): Add a packet to the buffer.

  2. get_next_packet(): Retrieve and remove the next available packet in sequence order. If the next expected packet is missing, your function should indicate that the packet is not yet available (for example, by returning null or a special value).

Additional Considerations:

  • Design a concise and clear API.
  • Ensure your solution can efficiently handle a large number of packets and maintain performance even when packets are missing or arrive out-of-order.
  • Use appropriate data structures to reduce the overhead of lookup and insertion.

Implement your solution in your preferred programming language.