Frontend School

Max Engagement Journey Score

DSA
medium

Max Engagement Journey Score

Medium
Sorting
Dynamic Programming
Arrays

Overview

At Clevertap, understanding user engagement patterns is crucial for product success. We often analyze sequences of user events to identify valuable 'journeys' that users take within our applications. This problem asks you to identify the most impactful user journey based on event scores and time proximity.

What you need to do / Task

Implement the function maxEngagementJourneyScore that calculates the maximum total score achievable from a valid 'engagement journey'. A journey is considered valid if it meets the following criteria:

  1. Minimum Events: It must consist of at least minEvents events.
  2. Chronological Order: The selected events must be strictly increasing in their timestamps.
  3. Time Proximity: The time difference between any two consecutive events in the selected journey must not exceed maxTimeGap.

Your function should return the maximum possible total score for any such valid journey. If no valid journey can be formed, return 0.

Input & output

  • events: An array of Event objects. Each Event object has two properties:
    • timestamp: number: The time (e.g., in milliseconds) when the event occurred.
    • score: number: The engagement score associated with this event (can be positive, negative, or zero).
  • maxTimeGap: number: A non-negative integer representing the maximum allowed time difference between consecutive events in a journey.
  • minEvents: number: A positive integer representing the minimum number of events required for a journey to be considered valid.
  • Return: A number representing the maximum total score of a valid engagement journey. Return 0 if no valid journey exists.

Clarifications

  • The input events array is not guaranteed to be sorted by timestamp.
  • Timestamps are non-negative integers.
  • Scores can be negative, indicating disengagement or a less desirable action. A journey can accumulate negative scores, but the objective is always to maximize the total score.
  • If maxTimeGap is 0, consecutive events must have identical timestamps. If minEvents is 1, any single event's score is a potential journey score.

Examples

1

Example 1

Input:

events = [{timestamp: 1, score: 10}, {timestamp: 3, score: 5}, {timestamp: 5, score: 12}, {timestamp: 8, score: -3}, {timestamp: 10, score: 8}], maxTimeGap = 3, minEvents = 2

Output:

32

Note:

Sorted events: [{t:1,s:10}, {t:3,s:5}, {t:5,s:12}, {t:8,s:-3}, {t:10,s:8}]. One optimal journey is: {t:1,s:10} -> {t:3,s:5} -> {t:5,s:12} -> {t:8,s:-3} -> {t:10,s:8}. Total score = 10+5+12-3+8 = 32. All consecutive time gaps (2, 2, 3, 2) are <= 3, and event count (5) >= 2.

2

Example 2

Input:

events = [{timestamp: 1, score: 10}, {timestamp: 10, score: 5}, {timestamp: 20, score: 12}], maxTimeGap = 5, minEvents = 2

Output:

0

Note:

Sorted events are already in order. No two consecutive events have a time difference <= 5. For example, 10-1=9 > 5, and 20-10=10 > 5. Thus, no journey with at least 2 events can be formed. Returns 0.

3

Example 3

Input:

events = [{timestamp: 10, score: 50}, {timestamp: 1, score: 10}, {timestamp: 5, score: 20}], maxTimeGap = 10, minEvents = 1

Output:

80

Note:

Sorted events: [{t:1,s:10}, {t:5,s:20}, {t:10,s:50}]. All events are within maxTimeGap of 10 (5-1=4, 10-5=5). The journey {t:1,s:10} -> {t:5,s:20} -> {t:10,s:50} yields a total score of 10+20+50 = 80. Since minEvents is 1, even a single event's score would be considered if it were the maximum.

Constraints

Constraints & assumptions

  • 1 <= events.length <= 2000
  • 0 <= events[i].timestamp <= 10^9
  • -1000 <= events[i].score <= 1000
  • 0 <= maxTimeGap <= 10^9
  • 1 <= minEvents <= events.length
  • Time Complexity: O(N^2) where N is events.length.
  • Space Complexity: O(N)

Out of scope

  • Handling of concurrent events with identical timestamps (you can assume timestamp_i < timestamp_{i+1} for selected events).
  • Network latency or database interactions.

What interviewers evaluate

  • Correctness of the sorting and dynamic programming approach.
  • Efficiency of the solution within the specified time and space complexity limits.
  • Accurate handling of edge cases, such as an empty input, no valid journeys, or varying minEvents and maxTimeGap values.
  • Code clarity, readability, and appropriate use of data structures.

Loading editor...