cache.js

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;
}