Skip to content

Instantly share code, notes, and snippets.

@Kunoacc
Last active April 3, 2024 18:30
Show Gist options
  • Save Kunoacc/884f0ec52493c71a4f275d1acedcb701 to your computer and use it in GitHub Desktop.
Save Kunoacc/884f0ec52493c71a4f275d1acedcb701 to your computer and use it in GitHub Desktop.
function getCacheSize(data, queries) {
const n = data.length;
const q = queries.length;
const events = [];
// TODO: add validations against constraints for inputs
// Create events for data insertions and expirations
for (let i = 0; i < n; i++) {
const [startTime, ttl] = data[i];
events.push({ time: startTime, type: 'entry', count: 1 });
events.push({ time: startTime + ttl, type: 'exit', count: -1 });
}
// Create events for queries
for (let i = 0; i < q; i++) {
events.push({ time: queries[i], type: 'query', count: 0, index: i });
}
// Sort events by time
events.sort((a, b) => a.time - b.time || b.count - a.count);
const result = new Array(q).fill(0);
let count = 0;
// Process events and update count
for (const event of events) {
// a switch statement could be used instead too? event types can increase by a factor of n
if (type !== 'query')
count += event.count;
if (type === 'query') {
result[event.index] = count;
}
}
return result;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment