Design a recent user query cache that stores query results for quick retrieval. The cache has a fixed capacity and removes the least recently used query whenever space is required.

Class

RecentQueryCache

Constructor

public RecentQueryCache(int capacity)

• Initializes an empty cache that can store results for at most capacity distinct queries.

Methods

storeQueryResult

public void storeQueryResult(String query, String result)

• Stores result for query.
• If the query already exists, replaces its previously stored result.
• The stored or updated query becomes the most recently used query.
• If a new query causes the cache to exceed its capacity, removes the least recently used query.

getQueryResult

public String getQueryResult(String query)

• Returns the stored result when query exists in the cache.
• A successfully retrieved query becomes the most recently used query.
• Returns an empty string "" when the query is not present.
• An unsuccessful retrieval does not change the usage order.

Cache Rules

• A query is considered used whenever it is successfully retrieved, inserted, or updated.
• The least recently used query is the stored query whose most recent successful retrieval, insertion, or update occurred earliest.
• Method-call order determines recency.
• Updating an existing query does not increase the number of stored queries.
• Inserting a new query into a full cache removes exactly one least recently used query.
• Query comparisons are exact and case-sensitive.
• Queries and results are stored exactly as supplied and are not trimmed.
• The empty string is reserved for an unsuccessful getQueryResult operation and is never supplied as a query or result.

Performance Requirements

• Each storeQueryResult operation must run in O(1) average time.
• Each getQueryResult operation must run in O(1) average time.
• The cache must use O(capacity) space.

Constraints

• 1 ≤ capacity ≤ 100,000
• 1 ≤ query.length() ≤ 200
• 1 ≤ result.length() ≤ 1,000
• Queries and results contain printable characters and are not blank.
• At most 100,000 method calls are made after construction.

Examples

Example 1

1. RecentQueryCache cache = new RecentQueryCache(capacity = 3)
2. cache.storeQueryResult( query = "weather in patna", result = "Sunny")
3. cache.storeQueryResult( query = "java hashmap", result = "Key-value collection")
4. cache.getQueryResult( query = "weather in patna") returns "Sunny"
5. cache.storeQueryResult( query = "train status", result = "On time")
6. cache.storeQueryResult( query = "flood update", result = "Normal")
7. cache.getQueryResult( query = "java hashmap") returns ""
8. cache.getQueryResult( query = "weather in patna") returns "Sunny"

Retrieving "weather in patna" makes it recently used. Therefore, "java hashmap" is removed when the fourth distinct query is stored.

Example 2

1. RecentQueryCache cache = new RecentQueryCache(capacity = 2)
2. cache.storeQueryResult( query = "electric cars", result = "Initial result")
3. cache.storeQueryResult( query = "battery laptops", result = "Laptop result")
4. cache.storeQueryResult( query = "electric cars", result = "Updated result")
5. cache.storeQueryResult( query = "water purifier", result = "Purifier result")
6. cache.getQueryResult( query = "electric cars") returns "Updated result"
7. cache.getQueryResult( query = "battery laptops") returns ""

Updating "electric cars" changes its result and makes it the most recently used query. Consequently, "battery laptops" is removed when "water purifier" is stored.

Example 3

1. RecentQueryCache cache = new RecentQueryCache(capacity = 2)
2. cache.storeQueryResult( query = "query-a", result = "result-a")
3. cache.storeQueryResult( query = "query-b", result = "result-b")
4. cache.getQueryResult( query = "missing-query") returns ""
5. cache.storeQueryResult( query = "query-c", result = "result-c")
6. cache.getQueryResult( query = "query-a") returns ""
7. cache.getQueryResult( query = "query-b") returns "result-b"

The unsuccessful retrieval of "missing-query" does not change recency. Therefore, "query-a" remains the least recently used query and is removed when "query-c" is stored.