Problem · Design
First Unique IP Hitting the Server
Learn this problem● Medium
UberFULLTIMEPHONE SCREEN
See Uber hiring insightsUberFULLTIMEPHONE SCREENProblem statement
Your 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
processFirstUniqueIpCommands(commands: String[]) → String[]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.
Examples
Example 1
commands = ["ADD 1.1.1.1", "ADD 2.2.2.2", "ADD 1.1.1.1", "FIRST_UNIQUE"]return = ["2.2.2.2"]2.2.2.2 is the earliest IP that has appeared exactly once after the first three add operations.
Example 2
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"]return = ["2.2.2.2", "3.3.3.3"]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
- 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.