Does my solution return with equal probability[C++]?


  • 2
    D

    I generate the a number for each node and return the node with the highest generated value.
    Each node has a 1/n probability of generating the largest value and thus has a 1/n probability of being returned.

    int getRandom() {
            
            int maxNumber = 0;
            int maxNodeValue = 0;
            
            ListNode * current = head;
            std::random_device rd;
            std::mt19937 gen(rd());
            std::uniform_int_distribution<> dis(1, 1000000000);
            
            
            while(current != NULL) {
                int rand = dis(gen);
                if(rand > maxNumber) {
                    maxNumber = rand;
                    maxNodeValue = current->val;
                }
                
                current = current->next;
            }
            return maxNodeValue;
        }
    

  • 0

    Very creative and neat. It's not quite perfect, because earlier nodes have the advantage in case of ties, but that's rare.


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.