FIFO FizzBuzz Market Matching
Google● MediumINTERNNEW GRADPHONE SCREENONSITE INTERVIEWProblem statement
In the FizzBuzz market, Fizz units are traded for Buzz units. You receive offers in priority order. The offer at index i has type types[i], participant names[i], and quantity quantities[i].
Process offers from left to right using these rules:
- A Fizz offer can match only a Buzz offer.
- Waiting offers of each type are matched first-in, first-out.
- Partial matches are allowed. Any remaining quantity stays at the front of its queue, or a remaining incoming quantity joins the back of its own queue.
- Aggregate every match between the same ordered pair of participant names, even when it occurs through several offers.
Return one announcement for each participant pair that traded, ordered by the pair's first match. Format each announcement as FizzBuzz! <amount> <FizzName>:<BuzzName>.
Function
matchFizzBuzzOffers(types: String[], names: String[], quantities: int[]) → String[]Examples
Example 1
types = ["Fizz","Buzz","Buzz","Fizz","Buzz"]names = ["Alice","Bob","Catherine","Alice","Bob"]quantities = [5,3,4,4,2]return = ["FizzBuzz! 5 Alice:Bob","FizzBuzz! 4 Alice:Catherine"]Alice first trades three units with Bob and two with Catherine. Her later Fizz offer trades two more with Catherine and two more with Bob, so both repeated pairs are aggregated.
Example 2
types = ["Buzz","Fizz","Fizz"]names = ["Bina","Faye","Finn"]quantities = [4,2,5]return = ["FizzBuzz! 2 Faye:Bina","FizzBuzz! 2 Finn:Bina"]The waiting Buzz offer is partially filled by Faye, then its remaining quantity is filled by Finn.
Example 3
types = ["Fizz","Fizz"]names = ["A","B"]quantities = [2,3]return = []No Buzz offer arrives, so no trade is announced.
Constraints
0 <= types.length == names.length == quantities.length <= 200000.- Every value in
typesisFizzorBuzz. - Every participant name is non-empty.
1 <= quantities[i] <= 10^9.- The total quantity aggregated for any participant pair fits in a signed 64-bit integer.