An electric-vehicle company delivers software updates as fixed 10 MB chunks. To lower cellular-data usage, vehicles may pass chunks to nearby vehicles through peer-to-peer WiFi.
You receive events, a sequence of completed transfer records. Every record has three strings in the form [from, chunkList, to]:
from identifies the vehicle—or the distribution source, written as "server"—that sends the chunks.chunkList contains the chunk IDs being sent, separated by spaces.to identifies the vehicle receiving those chunks.Each transferred chunk represents exactly 10 MB. Define a vehicle's contribution score as the total amount of data, in MB, that it helped distribute:
Y forwards a chunk that vehicle X previously helped deliver to Y, X receives another 10 MB of credit for that forwarding transfer. This applies when the chunk has traveled through one or more hops.Therefore, a vehicle's score includes both its own direct sends and later sends of chunks whose propagation it contributed to.
Implement a method that accepts events and returns every vehicle mentioned in the events as either a sender or a receiver, except for "server". Sort the result by decreasing contribution score; for equal scores, order vehicle IDs lexicographically.
1 ≤ events.length ≤ 10<sup>5</sup>chunkId, the propagation graph is guaranteed to contain no cycles.chunkId, the same from, to pair never appears in more than one transfer.chunkId, a vehicle receives that chunk from no more than one other vehicle.events = [ ["server", "1 2", "A"], ["server", "3 4", "C"], ["A", "1 2", "B"], ["A", "1", "C"], ["C", "4", "D"], ["C", "3", "B"], ["B", "3", "D"], ["D", "3", "A"] ]
["C", "A", "B", "D"]
Determine each score by following how every chunk moves through the network: Chunk 4: C → D. C receives 10 MB for directly forwarding chunk 4. Chunk 3: C → B → D → A. When C sends chunk 3 to B, C receives 10 MB. When B sends it to D, B receives 10 MB for the direct transfer, and C receives 10 MB as an upstream contributor. When D sends it to A, D receives 10 MB directly, while both B and C receive 10 MB for their upstream contributions. Chunk 1: A sends it to B and C, giving A 20 MB in direct credit. Chunk 2: A sends it to B, giving A another 10 MB. The resulting scores are C = 40 MB, A = 30 MB, B = 20 MB, and D = 10 MB.
events = [["server", "1", "A"], ["A", "1", "B"]]
["A", "B"]
events = [["server", "1", "A"], ["server", "2", "B"], ["server", "3", "C"]]
["A", "B", "C"]