# Design Query Cache

## Task

Design a key-value cache to save the results of the most recent web server queries

## Use Cases

- User sends a search request resulting in a `cache` hit
- User sends a search request resulting in a `cache` miss

## Design

**Query API**

```python
class QueryApi(object):
    # Attributes: memory_cache, reverse_index_service

def parse_query(self, query):
        # Clean up query, tokenize string, convert to boolean operations

def process_query(self, query):
        # Check cache. If no results, retrieve from index service and update cache
```

**Node** (atomic unit of `query`, `results` pair)

```python
class Node(object):
    # Attributes: query, results
```

**LinkedList** (doubly linked list of `node` to track least recently used query result)

```python
class LinkedList(object):
    # Attributes: head, tail

def move_to_front(self, node):
        # Move existing node to front of linked list

def append_to_front(self, node):
        # Append node to front of linked list

def remove_from_tail(self):
        # Remove node at the tail of linked list
```

**Cache**

```python
class Cache(object):
    # Attributes: MAX_SIZE, size, lookup, linked_list

def get(self, query):
        # Get query results. Update node position to front of list.

def set(self, results, query):
        # Add query-results pair into key-values.
        # Remove oldest entry in list and add node to front of list.
```

_Based on Donne Martin's_ [System Design Primer](https://github.com/donnemartin/system-design-primer)