FastPrepNumbers Station Message Decoder

Numbers Station Message Decoder

Optiver logoOptiver● HardNEW GRADOA
Learn

Problem statement

A radio broadcast arrives as samples of the form sequence character. Samples may arrive out of sequence order. A complete message consists of at least two lowercase letters at consecutive sequence IDs, immediately surrounded by hyphens at the preceding and following IDs.

  • When inserting one sample completes several messages at once, output only the completed message with the greatest ending sequence ID.
  • After outputting a message, never output a message whose ending sequence ID is lower than or equal to the last output message's ending sequence ID.
  • A one-letter fragment between two hyphens is ignored.
  • Sequence IDs are unique in the input stream.

Process every sample and return completed messages in callback order.

Function

decodeNumberStationMessages(samples: String[]) → String[]

Examples

Example 1

samples = ["1 -","2 h","3 e","4 y","5 -","6 b","7 -"]return = ["hey"]

The range from 1 through 5 completes hey. The later one-letter fragment b is ignored.

Example 2

samples = ["1 -","2 h","3 e","5 -","6 b","7 y","8 e","9 -","4 y"]return = ["bye"]

bye completes first with ending ID 9. When sample 4 y later completes hey, its ending ID 5 is obsolete.

Constraints

  • 1 <= samples.length <= 5 * 10^5
  • 0 < sequenceId <= 2^64 - 1
  • Every character is a lowercase English letter or -.
  • Every sequence ID appears at most once.

More Optiver problems

See Optiver hiring insights
public String[] decodeNumberStationMessages(String[] samples) {
  // write your code here
}
samples["1 -","2 h","3 e","4 y","5 -","6 b","7 -"]
expected["hey"]
Checking account…