Uber Phone Interview

Problem Statement You\'re given a stream of user IDs visiting a website. Implement two functions: 1. void PostAddUser(int userId): Adds a new user ID to the stream. 2. int GetFirstOneTimeUser():...

Problem Statement
You\'re given a stream of user IDs visiting a website. Implement two functions:

1. void PostAddUser(int userId): Adds a new user ID to the stream.
2. int GetFirstOneTimeUser():

Returns the first user ID that has visited exactly once and is still the first such user in order. If no such user exists,

return -1.

Example Usage:

cpp
PostAddUser(1);
PostAddUser(2);
PostAddUser(3);
PostAddUser(1);
cout << GetFirstOneTimeUser(); //

**Output**: 2
PostAddUser(2);
cout << GetFirstOneTimeUser(); //

**Output**: 3
PostAddUser(3);
cout << GetFirstOneTimeUser(); //

**Output**: -1

Solution Approach
To efficiently track the first unique user in the stream, we use:

1.

An unordered map (count) to store the frequency of each user ID.
2.

A queue (q) to maintain the order of one-time users.

Steps:
- When a user visits, increment its count.
- If it\'s the first visit, push it into the queue.
- When retrieving the first one-time user, remove users from the queue until the front is still a valid one-time user.

Time Complexity:
- PostAddUser():

O(1) (Amortized)
- GetFirstOneTimeUser():

O(1) (Amortized)

C++ Solution

cpp
#include <iostream>
#include <unordered_map>
#include <queue>

using namespace std;

class WebsiteTracker {
 unordered_map<int, int> count;
 queue<int> q;

public:
 void PostAddUser(int userId) {
 count[userId]++;
 if (count[userId] == 1) {
 q.push(userId);
 }
 }

 int GetFirstOneTimeUser() {
 while (!q.empty() && count[q.front()] > 1) {
 q.pop();
 }

**return** q.empty() ? -1 : q.front();
 }
};

//

**Example** usage
int main() {
 WebsiteTracker tracker;
 tracker.PostAddUser(1);
 tracker.PostAddUser(2);
 tracker.PostAddUser(3);
 tracker.PostAddUser(1);
 cout << tracker.GetFirstOneTimeUser() << endl; //

**Output**: 2
 tracker.PostAddUser(2);
 cout << tracker.GetFirstOneTimeUser() << endl; //

**Output**: 3
 tracker.PostAddUser(3);
 cout << tracker.GetFirstOneTimeUser() << endl; //

**Output**: -1

**return** 0;
}

OR

class WebsiteTracker {
 unordered_map<int, list<int>::iterator> userPosition;
 unordered_map<int, int> count;
 list<int> uniqueUsers;

public:
 void PostAddUser(int userId) {
 count[userId]++;

 if (count[userId] == 1) {
 // First-time visit: Add to list
 uniqueUsers.push_back(userId);
 userPosition[userId] = --uniqueUsers.end(); // Store iterator
 }
 else if (count[userId] == 2) {
 // Second-time visit: Remove from list
 uniqueUsers.erase(userPosition[userId]);
 userPosition.erase(userId); // Remove iterator from map
 }
 }

 int GetFirstOneTimeUser() {

**return** uniqueUsers.empty() ? -1 : uniqueUsers.front();
 }
};