Katkat
Back

Implement Last-Click Attribution APIs

UberSoftware Engineer · Technical Screen
MediumSoftware EngineerTechnical ScreenCoding & Algorithms

Last updated

This problem tests your ability to process streams of events to perform stateful attribution, requiring efficient data structures to track user sessions and match conversions to the most recent preceding click.

Problem Statement

You are building a real-time attribution service for a marketing platform. You need to process a stream of two types of events: CLICK and CONVERSION.

An attribution is valid if a CONVERSION event is linked to the most recent CLICK event for that specific user_id that occurred within a lookback window of T milliseconds.

Implement the class AttributionEngine:

class AttributionEngine:
    def __init__(self, lookback_window_ms: int):
        # Initialize with the maximum allowed time difference

    def process_event(self, event_type: str, user_id: int, timestamp: int) -> int:
        # event_type: 'CLICK' or 'CONVERSION'
        # Returns the user_id of the matched click if successful, else -1

Rules:

  1. If a CONVERSION occurs, it consumes the most recent CLICK for that user_id that is within the window [timestamp - T, timestamp].
  2. Once a CLICK is used for a CONVERSION, it cannot be used again.
  3. If multiple CLICK events exist in the window, only the latest one is used.

Examples:

  • window = 1000
  • process_event('CLICK', 1, 1000) -> returns -1
  • process_event('CONVERSION', 1, 1500) -> returns 1 (Matches the click at 1000)
  • process_event('CONVERSION', 1, 2500) -> returns -1 (No click within [1500, 2500])

Constraints:

  • Events are provided in non-decreasing order of timestamps.
  • user_id is an integer.
  • Efficiency matters: handle millions of events where many users may be inactive.

Hints

Hint 1

Use a hash map to store a collection of clicks for each user, keyed by user_id.

Hint 2

Since events arrive in chronological order, for a specific user, you only need to store clicks that could potentially be valid for future conversions.

Hint 3

Use a double-ended queue or a sorted list to store timestamps of clicks per user to easily remove expired clicks that fall outside the lookback window.

Follow-up questions

  • How would you handle the case where events arrive slightly out of chronological order due to network latency?
  • If the system crashes, how would you ensure that the state of matched clicks is persisted or recovered correctly?
  • How would your implementation change if you needed to support a 'First-Click' attribution model instead of 'Last-Click'?