LRU Cache Implementation

Your challenge is to design and implement a Least Recently Used (LRU) cache data structure that supports the following operations with optimal time complexity (preferably O(1) for each operation):

1. get(key): Retrieve the value associated with the key if it exists in the cache; otherwise, return -1.

2. put(key, value): Insert or update the value associated with the key. If the cache exceeds its predetermined capacity after the insertion, it should invalidate and remove the least recently used item.

Requirements:

• The cache should be initialized with a fixed capacity.
• Both operations (get and put) must perform in constant time on average.
• Consider edge cases such as accessing non-existent keys and updating an existing key.

Implement your solution in the programming language of your choice and include tests or examples that demonstrate the correctness of your implementation.