Uber Phone Interview
Anonymous User
472
Hash TableArrayInterview

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:

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

#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();
    }
};
Comments (1)