Problem Brief
First Unique IP Hitting the Server
FULLTIMEPHONE SCREEN
See Uber online assessment and hiring insightsYour server receives a stream of IP hit events. Design a data structure that supports two operations:
ADD ip: record one hit fromipFIRST_UNIQUE: return the earliest IP address that has appeared exactly once so far, or an empty string if none exists
Process all commands in order and return the outputs produced by the FIRST_UNIQUE commands.
Function Description
Complete the function processFirstUniqueIpCommands in the editor below.
processFirstUniqueIpCommands has the following parameter:
String[] commands: the commands to execute
Returns
String[]: the answers for the FIRST_UNIQUE commands in order.
1Example 1
Input
commands = ["ADD 1.1.1.1", "ADD 2.2.2.2", "ADD 1.1.1.1", "FIRST_UNIQUE"]
Output
["2.2.2.2"]
Explanation
2.2.2.2 is the earliest IP that has appeared exactly once after the first three add operations.
2Example 2
Input
commands = ["ADD 1.1.1.1", "ADD 2.2.2.2", "ADD 1.1.1.1", "ADD 3.3.3.3", "FIRST_UNIQUE", "ADD 2.2.2.2", "FIRST_UNIQUE"]
Output
["2.2.2.2", "3.3.3.3"]
Explanation
After the second query state change, 2.2.2.2 is no longer unique, so the next earliest unique IP is 3.3.3.3.
Constraints
Limits and guarantees your solution can rely on.
- The total number of events can be as large as
10^7. - The number of distinct IPs can be as large as
10^6. - IP strings should be treated as opaque strings; validation is not required.