Find Global and Rolling Top-K URLs Under a Memory Limit

Question

The question asks the candidate to design a system that can efficiently find the global Top K URLs and the Top K URLs accessed in the last 24 hours, all while operating under a memory constraint.

Codemia · Accepted Answer

The goal is to find the global Top K URLs and the Top K URLs accessed in the last 24 hours under memory constraints. We need to consider the volume of URL access logs and the limitations on memory usage, which will affect our choice of algorithms and data structures.

The system can be designed with two main components: a batch processing module for global Top K URLs and a streaming module for the last 24 hours' Top K URLs. We can use a distributed processing framework like Apache Spark for batch processing, while a streaming solution like Apache Flink can handle real-time data. Both components will interact with a scalable storage solution, such as a distributed database or key-value store.

Using batch processing allows for more complex algorithms but may introduce latency. Streaming processing provides real-time results but can be more challenging to implement and may require more memory. We need to balance accuracy and performance, especially under memory limits. A possible trade-off is to use approximate algorithms like HyperLogLog for counting unique URLs.

Here is a simplified pseudocode for the global Top K URLs:
```python
class TopKURLs:
    def __init__(self, k):
        self.k = k
        self.url_count = {}

def process_logs(self, logs):
        for url in logs:
            if url in self.url_count:
                self.url_count[url] += 1
            else:
                self.url_count[url] = 1
        return self.get_top_k()

def get_top_k(self):
        return sorted(self.url_count.items(), key=lambda x: x[1], reverse=True)[:self.k]
```
This pseudocode outlines a simple approach to count URLs and retrieve the top K.

To ensure scalability, we should partition the data across multiple nodes and use a distributed computing framework. Caching frequently accessed data can also help reduce memory usage. Monitoring system performance and adjusting resource allocation dynamically can further enhance scalability.

Find Global and Rolling Top-K URLs Under a Memory Limit

Oracle

What the Interviewer Expects

Key Topics to Cover

How to Approach This

Possible Follow-up Questions

Sharpen Your Skills on Codemia

Sample Answer

Requirements

High-Level Design

Submit Your Answer

Oracle Software Engineer Interview Guide

Related Questions

Design a high-throughput Inventory Management System

Design a low-latency Rate Limiting System

Design a fault-tolerant Payment System

Design a fault-tolerant Messaging System

Design Walmart Product Search