When a team builds a training set for a model, every training row needs the feature values that were known at the moment the row's event happened, not the values that exist today. The feature consistency topic of the ML System Design course calls this a point-in-time join, and a feature store performs it so that training data never contains information from the future. This problem asks you to perform that join by hand.
You are given a list of events and a list of feature rows. Each event is a dictionary with an entity_id (a string such as a user id) and a timestamp (an integer, for example a time in seconds). Each feature row is a dictionary with an entity_id, a timestamp that says when the feature value became available, and a numeric value. For every event, find the feature row for the same entity whose timestamp is at or before the event timestamp and no more than ttl units older than it, and take the newest such row. If no row qualifies, the feature value is None.
Return a list with one dictionary per event, in the same order as the events. Each dictionary has the keys entity_id, timestamp and value, where entity_id and timestamp are copied from the event and value is the chosen feature value or None.
The feature rows are not sorted and may belong to many entities. A row whose timestamp equals the event timestamp qualifies. A row that is exactly ttl units old also qualifies. A row with a later timestamp than the event never qualifies, however close it is, because it was not known yet.
Worked example with ttl equal to 10. Entity u1 has feature rows at times 3 (value 5.0), 8 (value 7.0) and 20 (value 9.0). An event for u1 at time 12 can see the rows at 3 and 8, since both are at or before 12 and within 10 units, and it takes the newer one, so the value is 7.0. An event for u1 at time 18 can see only the row at 8, because the row at 3 is 15 units old while the row at 8 is exactly 10 units old, so the value is 7.0 again. An event for u1 at time 35 sees nothing, because the row at 20 is 15 units old, so the value is None.
Input: events = [{"entity_id": "u1", "timestamp": 12}, {"entity_id": "u1", "timestamp": 18}, {"entity_id": "u1", "timestamp": 35}], feature_rows = [{"entity_id": "u1", "timestamp": 3, "value": 5.0}, {"entity_id": "u1", "timestamp": 8, "value": 7.0}, {"entity_id": "u1", "timestamp": 20, "value": 9.0}], ttl = 10
Output: [{"entity_id": "u1", "timestamp": 12, "value": 7.0}, {"entity_id": "u1", "timestamp": 18, "value": 7.0}, {"entity_id": "u1", "timestamp": 35, "value": null}]
Explanation: At time 12 the newest row within ten units is the one at time 8. At time 18 the row at time 3 has expired and the row at time 8 is exactly ten units old, so it still counts. At time 35 the row at time 20 has expired too, and the row from the future is never visible.
Input: events = [{"entity_id": "u2", "timestamp": 50}], feature_rows = [{"entity_id": "u1", "timestamp": 40, "value": 1.0}], ttl = 100
Output: [{"entity_id": "u2", "timestamp": 50, "value": null}]
Explanation: The only feature row belongs to a different entity, so the event gets None.
Group the feature rows by entity_id before looping over the events, so each event only scans the rows that could match it.
A row qualifies when its timestamp is at most the event timestamp and the difference is at most ttl; among qualifying rows keep the one with the largest timestamp.
Accepts: array
Accepts: array
Accepts: number
When a team builds a training set for a model, every training row needs the feature values that were known at the moment the row's event happened, not the values that exist today. The feature consistency topic of the ML System Design course calls this a point-in-time join, and a feature store performs it so that training data never contains information from the future. This problem asks you to perform that join by hand.
You are given a list of events and a list of feature rows. Each event is a dictionary with an entity_id (a string such as a user id) and a timestamp (an integer, for example a time in seconds). Each feature row is a dictionary with an entity_id, a timestamp that says when the feature value became available, and a numeric value. For every event, find the feature row for the same entity whose timestamp is at or before the event timestamp and no more than ttl units older than it, and take the newest such row. If no row qualifies, the feature value is None.
Return a list with one dictionary per event, in the same order as the events. Each dictionary has the keys entity_id, timestamp and value, where entity_id and timestamp are copied from the event and value is the chosen feature value or None.
The feature rows are not sorted and may belong to many entities. A row whose timestamp equals the event timestamp qualifies. A row that is exactly ttl units old also qualifies. A row with a later timestamp than the event never qualifies, however close it is, because it was not known yet.
Worked example with ttl equal to 10. Entity u1 has feature rows at times 3 (value 5.0), 8 (value 7.0) and 20 (value 9.0). An event for u1 at time 12 can see the rows at 3 and 8, since both are at or before 12 and within 10 units, and it takes the newer one, so the value is 7.0. An event for u1 at time 18 can see only the row at 8, because the row at 3 is 15 units old while the row at 8 is exactly 10 units old, so the value is 7.0 again. An event for u1 at time 35 sees nothing, because the row at 20 is 15 units old, so the value is None.
Input: events = [{"entity_id": "u1", "timestamp": 12}, {"entity_id": "u1", "timestamp": 18}, {"entity_id": "u1", "timestamp": 35}], feature_rows = [{"entity_id": "u1", "timestamp": 3, "value": 5.0}, {"entity_id": "u1", "timestamp": 8, "value": 7.0}, {"entity_id": "u1", "timestamp": 20, "value": 9.0}], ttl = 10
Output: [{"entity_id": "u1", "timestamp": 12, "value": 7.0}, {"entity_id": "u1", "timestamp": 18, "value": 7.0}, {"entity_id": "u1", "timestamp": 35, "value": null}]
Explanation: At time 12 the newest row within ten units is the one at time 8. At time 18 the row at time 3 has expired and the row at time 8 is exactly ten units old, so it still counts. At time 35 the row at time 20 has expired too, and the row from the future is never visible.
Input: events = [{"entity_id": "u2", "timestamp": 50}], feature_rows = [{"entity_id": "u1", "timestamp": 40, "value": 1.0}], ttl = 100
Output: [{"entity_id": "u2", "timestamp": 50, "value": null}]
Explanation: The only feature row belongs to a different entity, so the event gets None.
Group the feature rows by entity_id before looping over the events, so each event only scans the rows that could match it.
A row qualifies when its timestamp is at most the event timestamp and the difference is at most ttl; among qualifying rows keep the one with the largest timestamp.
Accepts: array
Accepts: array
Accepts: number