FastPrep
Problem · Design

First Unique IP Hitting the Server

● MediumUberFULLTIMEPHONE SCREEN
See Uber hiring insights

Your server receives a stream of IP hit events. Design a data structure that supports two operations:

  • ADD ip: record one hit from ip
  • FIRST_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:

  1. String[] commands: the commands to execute

Returns

String[]: the answers for the FIRST_UNIQUE commands in order.

Examples
01 · 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.

02 · 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.
More Uber problems
drafts saved locally
public String[] processFirstUniqueIpCommands(String[] commands) {
    // write your code here
}
commands["ADD 1.1.1.1", "ADD 2.2.2.2", "ADD 1.1.1.1", "FIRST_UNIQUE"]
expected["2.2.2.2"]
sign in to submit