FastPrepFirst Unique Event in a Stream
Problem · String

First Unique Event in a Stream

Learn this problem
● MediumGoogle logoGoogleFULLTIMEPHONE SCREEN
See Google hiring insights

Problem statement

You receive a stream of string events in order. After processing each event, report the earliest event value that has appeared exactly once in the entire prefix processed so far.

If the current prefix has no event value with frequency one, report the empty string for that position. Return one answer for every processed event.

Function

firstUniqueAfterEachEvent(events: String[]) → String[]

Examples

Example 1

events = ["a","b","a","c"]return = ["a","a","b","b"]

After the third event, a is repeated, so b becomes the earliest value seen exactly once. Adding c does not change that earliest unique value.

Example 2

events = ["x","x","y","y"]return = ["x","","y",""]

The second and fourth prefixes contain no value with frequency one, so their answers are empty strings.

Example 3

events = []return = []

An empty stream produces no prefix answers.

Constraints

  • 0 <= events.length <= 200000
  • 1 <= events[i].length <= 30
  • Each event contains lowercase English letters.

More Google problems

drafts saved locally
public String[] firstUniqueAfterEachEvent(String[] events) {
    // Write your code here.
}
events["a","b","a","c"]
expected["a", "a", "b", "b"]
checking account