algoadvance

This problem asks you to implement a data structure that can record and report the last k integers that have been visited. The operations that need to be supported are:

1. insert(val): Insert an integer val into the data structure.
2. get_last(k): Get the last k visited integers.

Clarifying Questions:

1. Are there any constraints on the integers (e.g., negative/positive, range)?
2. How should the get_last(k) function behave if k is larger than the number of elements inserted so far?
3. Can I always assume that insert() will be called before get_last(k)?

Example:

If you first call insert(1), insert(2), insert(3), then get_last(2) should return [3, 2].

Strategy:

1. Use a circular buffer or a deque to manage the last k elements efficiently.
2. The deque from the collections module is suitable because it allows fast appends and pops from both ends, making it ideal for this problem.

Code:

from collections import deque

class LastVisitedIntegers:
    def __init__(self, k):
        self.k = k
        self.data = deque(maxlen=k)
    
    def insert(self, val: int) -> None:
        self.data.append(val)
    
    def get_last(self, k: int):
        if k > len(self.data):
            return list(self.data)[::-1]
        else:
            return list(self.data)[-k:][::-1]

# Example Usage
# lvi = LastVisitedIntegers(k=3)
# lvi.insert(1)
# lvi.insert(2)
# lvi.insert(3)
# print(lvi.get_last(2))  # Output: [3, 2]
# lvi.insert(4)
# print(lvi.get_last(3))  # Output: [4, 3, 2]

Time Complexity:

• insert(val) takes O(1) time because appending to a deque with a fixed max length is O(1).
• get_last(k) takes O(k) time for slicing the list and reversing it (in the worst case, k is the maximum length of the deque).

This approach ensures that both insertion and retrieval of the last k elements are efficient and straightforward, leveraging the capabilities of the deque in Python’s collections module.

Try our interview co-pilot at AlgoAdvance.com

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?