Implement Several Core Algorithmic Components

Part 1: LRU Cache

Design and implement a Least Recently Used (LRU) cache. It should support get(key) and put(key, value) operations with O(1) average time complexity. The cache has a fixed capacity.

Part 2: Randomized Transformation

Given a function rand7() that generates a uniform integer between 1 and 7, implement a function rand10() that generates a uniform integer between 1 and 10 using rand7().

Part 3: Axis-Aligned Square Counting

Given a list of points on a 2D plane points = [[x1, y1], [x2, y2], ...], write a function to return the total number of axis-aligned squares that can be formed using four points from the set. An axis-aligned square has sides parallel to the x and y axes.

Examples

LRU Cache

cache = LRUCache(2)
cache.put(1, 1)
cache.put(2, 2)
cache.get(1) # Returns 1
cache.put(3, 3) # Evicts key 2
cache.get(2) # Returns -1 (not found)

Square Counting

# Input: points = [[0,0], [0,1], [1,0], [1,1], [0,2], [1,2]]
# Output: 2
# Explanation: The squares are ([0,0], [0,1], [1,0], [1,1]) and ([0,1], [0,2], [1,1], [1,2]).

Constraints

• For LRUCache, capacity is a positive integer.
• For rand7(), assume it is uniformly distributed.
• For square counting, the number of points N is up to 1000.