Match Billing Charges to User Sessions (Part 2)
Scale AI● MediumNEW GRADINTERNOAProblem statement
This is Part 2 of Event Log Reconciliation. See Part 1: Build Sessions from Unordered Events for the session summary task. The two parts can be solved independently.
Background
Part 1 summarizes sessions per user. Part 2 works with the individual sessions and reconciles them against a billing ledger. Both parts receive the original activity events independently; Part 2 does not use the summary returned by Part 1.
Apply the same session-building rules to events, keeping each session as an interval with fields user, start, and end. Match every charge in ledger to the interval containing its timestamp. The same interval-building logic can be shared with Part 1, which folds the intervals into per-user totals.
Activity events
events is a list of objects with a user ID, an integer timestamp, and an event type:
{ "user": "u1", "ts": 100, "type": "login" }The type is login, action, or logout. Events may arrive out of order. Each user's timestamps are distinct, although different users may share a timestamp.
How to build sessions
Process the events for each user in timestamp order:
- A
loginopens a session. - The next
logoutfor that user closes it at the logout timestamp. - Missing logout: If another
loginarrives while a session is open, or the user's events end before a logout, close the session at its lastactiontimestamp. If it contains no actions, close it at its login timestamp. A new login then opens another session. - Ignore an
actionorlogoutwhen that user has no open session.
Keep sessions even when their start and end timestamps are equal.
Billing ledger
ledger is a list of charge objects. Each charge has fields user, ts, and amount:
{ "user": "u1", "ts": 200, "amount": 5 }Matching rules
- A charge matches a session when it belongs to the same user and its timestamp is inside that session, including both endpoints:
start <= charge_ts <= end. - A user's session intervals are disjoint: the end of one is strictly before the start of the next. Each charge therefore matches at most one session.
- A charge with no matching session is an orphan charge. This includes a charge for a user who has no sessions.
- A session with no matching charge is an unbilled session.
More than one charge can match the same session. It still counts as one billed session. Matching uses only the user and timestamp; a charge with an amount of 0 also bills a matching session.
Reconciliation result
Return these two groups:
- Orphan charges: The unmatched charge objects, preserving their order in
ledger. - Unbilled sessions: The reconstructed session intervals that have no matching charge.
Practice input and output
In the coding workspace, event objects are represented by the parallel arrays users, timestamps, and types. At index i, their values are the event's user, ts, and type.
The parallel arrays chargeUsers, chargeTimestamps, and chargeAmounts represent the ledger objects in their original order. At index i, their values are the charge's user, ts, and amount.
Represent the two result groups as rows:
- Return orphan charges first, each as
["orphan", user, timestamp, amount], in the original ledger order. - Then return unbilled sessions, each as
["unbilled", user, start, end], sorted by user ID in increasing lexicographic order and then by start time.
Write each numeric cell as a decimal string. If both result groups are empty, return an empty array.
Function
reconcileLedger(users: String[], timestamps: int[], types: String[], chargeUsers: String[], chargeTimestamps: int[], chargeAmounts: long[]) → String[][]Examples
Example 1
users = ["u1","u1","u1","u2"]timestamps = [100,250,180,120]types = ["login","logout","action","action"]chargeUsers = ["u1","u1","u2","u1"]chargeTimestamps = [200,250,120,251]chargeAmounts = [5,0,7,9]return = [["orphan","u2","120","7"],["orphan","u1","251","9"]]Sorting the events gives u1 the session [100,250]. The u2 action creates no session. The charges at 200 and 250 both bill u1's session, including the zero-amount charge. The u2 charge at 120 and the u1 charge at 251 are orphaned, in that ledger order. No session is unbilled.
Example 2
users = ["u1","u1","u1","u1","u2","u2"]timestamps = [10,20,30,40,15,16]types = ["login","action","login","logout","login","action"]chargeUsers = ["u3","u1","u1","u2"]chargeTimestamps = [15,20,25,16]chargeAmounts = [2,1,3,0]return = [["orphan","u3","15","2"],["orphan","u1","25","3"],["unbilled","u1","30","40"]]The second u1 login closes its first session at the last action, producing [10,20]. Its next session is [30,40]. The open u2 session closes at its last action, producing [15,16]. The u3 charge has no session, and u1's charge at 25 is in the gap. The charges at 20 and 16 bill the first u1 session and the u2 session. Only u1's [30,40] session is unbilled.
Example 3
users = ["b","a","a","a"]timestamps = [5,5,7,8]types = ["login","login","login","logout"]chargeUsers = []chargeTimestamps = []chargeAmounts = []return = [["unbilled","a","5","5"],["unbilled","a","7","8"],["unbilled","b","5","5"]]The second a login closes the first a session at its login time, giving [5,5]. The other a session is [7,8], and b has [5,5]. With no charges, all three sessions are unbilled. They are returned in user order, then start-time order.
Constraints
- For this exercise, assume
0 <= users.length <= 10000and0 <= chargeUsers.length <= 10000. users.length = timestamps.length = types.length.chargeUsers.length = chargeTimestamps.length = chargeAmounts.length.- For this exercise, assume each user ID has
1to32characters and contains only lowercase ASCII letters and digits. - For this exercise, assume
-2147483648 <= timestamps[i], chargeTimestamps[i] <= 2147483647. - For this exercise, assume
0 <= chargeAmounts[i] <= 10^12and each amount is an integer. - Every event type is one of
login,action, orlogout. - Events for the same user have distinct timestamps. Different users may share timestamps. Charges may repeat users, timestamps, and amounts.