How do I practice coding and algorithm questions?

Use PracHub's coding console to write, test, and debug your solutions in Python or JavaScript. View hints, test against sample inputs, and compare with official solutions.

What difficulty level is this coding question?

This is a medium difficulty Coding & Algorithms question, commonly asked during Technical Screen rounds at Uber.

What role is this question designed for?

This question is commonly asked for Software Engineer candidates at Uber during technical interviews.

Implement Last-Click Attribution APIs

Company: Uber

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Technical Screen

Design and implement an in-memory last-click attribution service. There are two event types: - `click(timestamp, userId, campaignId)` - `conversion(timestamp, userId)` For each conversion, attribute it to the most recent click from the same user such that: 1. The click timestamp is less than or equal to the conversion timestamp. 2. The click occurred within a fixed conversion window before the conversion. Use `conversion_window_seconds = 300`. For a conversion at time `t`, consider clicks from the same user in the range `[t - 300, t]`. If no qualifying click exists, the conversion is unattributed. Implement the following API: ```text recordClick(userId, campaignId, timestamp) recordConversion(userId, timestamp) getCampaignConversions(campaignId) getUserAttribution(userId) ``` Expected behavior: - `recordClick` stores a click event. - `recordConversion` records a conversion and immediately attributes it to the most recent eligible click, if one exists. - `getCampaignConversions(campaignId)` returns the number of conversions attributed to that campaign. - `getUserAttribution(userId)` returns the attribution history for that user, including each conversion timestamp and the campaign it was attributed to, or `null`/`unattributed` if no eligible click existed. You should also write and run tests for edge cases, including conversions with no clicks, clicks outside the window, multiple clicks within the window, and clicks at exactly the conversion timestamp.

Quick Answer: This question evaluates a candidate's ability to implement stateful, time-windowed event matching and attribution, testing skills in data structures, event ordering, temporal reasoning, and correctness under edge cases.

Design an in-memory last-click attribution service. Implement `solution(operations)` to process API calls in order and return the results of query calls. Use a fixed conversion window of 300 seconds. When a conversion for user `u` happens at time `t`, attribute it to the most recent recorded click for the same user whose timestamp is in `[t - 300, t]`. If no such click exists, that conversion is unattributed. Each operation is a string in one of these forms: - `recordClick userId campaignId timestamp` - `recordConversion userId timestamp` - `getCampaignConversions campaignId` - `getUserAttribution userId` All `recordClick` and `recordConversion` operations appear in non-decreasing timestamp order. If multiple clicks for the same user have the same timestamp, the one recorded later is considered more recent. Return a list containing the result of each query operation, in the order the queries appear: - `getCampaignConversions` returns the count as a string, for example `"2"`. - `getUserAttribution` returns a string like `"[100:c1,250:unattributed]"`. Use `"[]"` if the user has no conversions yet.

Constraints

1 <= len(operations) <= 2 * 10^5
0 <= timestamp <= 10^9
`recordClick` and `recordConversion` operations are given in non-decreasing timestamp order

Examples

Input: ['recordConversion u1 100', 'getUserAttribution u1', 'getCampaignConversions c1']

Expected Output: ['[100:unattributed]', '0']

Explanation: The user converts without any prior click, so the conversion is unattributed. Campaign c1 has zero attributed conversions.

Input: ['recordClick u1 c1 10', 'recordConversion u1 311', 'getUserAttribution u1', 'getCampaignConversions c1']

Expected Output: ['[311:unattributed]', '0']

Explanation: The click at 10 is outside the valid window for a conversion at 311, because the allowed range is [11, 311].

Input: ['recordClick u1 c1 100', 'recordClick u1 c2 250', 'recordConversion u1 300', 'recordClick u1 c3 300', 'recordConversion u1 300', 'getUserAttribution u1', 'getCampaignConversions c1', 'getCampaignConversions c2', 'getCampaignConversions c3']

Expected Output: ['[300:c2,300:c3]', '0', '1', '1']

Explanation: For the first conversion at 300, both clicks are in the window and c2 is the most recent. For the second conversion at the same timestamp, the click on c3 recorded at exactly 300 is eligible and becomes the most recent.

Input: ['recordClick alice A 100', 'recordClick bob B 120', 'recordConversion alice 350', 'recordConversion bob 421', 'recordClick bob C 430', 'recordConversion bob 730', 'getUserAttribution alice', 'getUserAttribution bob', 'getCampaignConversions A', 'getCampaignConversions B', 'getCampaignConversions C']

Expected Output: ['[350:A]', '[421:unattributed,730:C]', '1', '0', '1']

Explanation: Alice's click at 100 is within 300 seconds of conversion 350. Bob's click at 120 is just outside the window for 421, but the click at 430 is exactly 300 seconds before 730 and is valid.

Input: ['recordClick u1 c1 100', 'getUserAttribution u1', 'getCampaignConversions c1']

Expected Output: ['[]', '0']

Explanation: A user with clicks but no conversions has empty attribution history, and no campaign has an attributed conversion yet.

Hints

Because events are processed in chronological order, a click older than `current_timestamp - 300` for a user can never be used again for that user.
Store recent clicks per user in a deque: remove expired clicks from the left, and the newest eligible click will be at the right end.

Quick Overview

This question evaluates a candidate's ability to implement stateful, time-windowed event matching and attribution, testing skills in data structures, event ordering, temporal reasoning, and correctness under edge cases.