LRU Cache

Design and implement a Least Recently Used (LRU) cache data structure. The cache should support the following operations:

1. get(key): Return the value associated with the key if the key exists in the cache; otherwise, return -1.
2. put(key, value): Insert or update the value for the key. If the cache reaches its capacity, it should invalidate and remove the least recently used item before inserting the new item.

Your implementation should meet the following requirements:

• The cache capacity will be provided during initialization.
• Both operations should have an average time complexity of O(1).
• Keys and values will be integers.

Define the interface (or class) that supports the operations above. You may design your solution in any programming language of your choice, but ensure that the interface is clear and that you follow the operational requirements stated.

Test your implementation with multiple operations and edge cases to ensure correctness.

Happy coding!