Amazon Software Engineer interview questions

Design a data structure that tracks visitors in a queue with the following requirements: - Possibility to return the last person in the queue, who visited only once - All operations must be O(1) time complexity visit("Alice") -> Queue: [Alice] visit("Bob") -> Queue: [Alice, Bob] visit("Charlie") -> Queue: [Alice, Bob, Charlie] visit("Bob") -> Queue: [Alice, Charlie] (Bob removed because second visit) get_last_unique() -> Returns "Charlie" visit("David") -> Queue: [Alice, Charlie, David] visit("Charlie") -> Queue: [Alice, David] (Charlie removed because second visit) get_last_unique() -> Returns "David"