Home

Random point in a circle

1,442.0K Views

You’re given a procedure that with a uniform probability distribution outputs random numbers between 0 and 1 (to some sufficiently high degree of precision, with which we need not concern ourselves in this puzzle).  Using a bounded number of calls to this procedure, construct a procedure that with a uniform probability distribution outputs a random point within the unit circle.

Share
ronret45 Expert Asked on 1st August 2015 in Microsoft Interview Puzzles.
Add Comment
Cancel

    • 1 Answer(s)

    The problem does not state whether the random number is inclusive, exclusive or some combination, of the bounds 0 and 1.  My answer assumes the typical random number generator, which is inclusive of 0 and exclusive of 1.  It takes exactly two calls to the random number generator.

    radius = random / 2
    degrees = random * 360

    x = radius * sin(degrees)
    y = radius * cos(degrees)

    Now the problem with this solution is that it lacks uniform distribution.  Half the points will have radius < 0.25 and half 0.25 to 0.5, but the area in the circle with radius < 0.25 is only 25% of the total area of the circle.  So we need to distribute the points along the radius using the inverse square of the random value so that the probability of a point having radius r is proportional to the area of a circle with radius r (i.e. a radius that gives a circle with area a is half as likely as a radius that gives a circle with area 2a).

    radius = sqrt(random) / 2
    degrees = random * 360

    x = radius * sin(degrees)
    y = radius * cos(degrees)

    Cancel
    dougbell Genius Answered on 21st October 2015.
    Add Comment
    Cancel

    • Your Answer

    By posting your answer, you agree to the privacy policy and terms of service.

  • More puzzles to try-

  • Accenture Interview PuzzlesAdobe Interview PuzzlesAge RiddleAkbar Birbal PuzzlesAlgorithm PuzzlesAlphabet riddleAmazon Interview PuzzlesAnalytical MathematicsAptitude PuzzleBank PuzzlesBetting PuzzlesBrain TeasersCalendar PuzzlesCards PuzzlesChess Board PuzzleChess PuzzlesChristmas Puzzlecipher PuzzleCivil Services PuzzleClock time puzzleCognizant Interview PuzzlesCoins PuzzleComputational PuzzleconundrumCoronavirus PuzzleCoupondunia Interview PuzzleCritical Thinking Puzzledata analyticsData Structure Interview QuestionsDecode PuzzleDetective PuzzlesDice PuzzleDictionary Riddlesdifficult riddleEasy Math puzzlesEasy puzzlesEinstein puzzleEnglish RiddleFamily Tree Puzzlefamous puzzleFill in the blanks riddlesFinding Killer RiddlesFlipkart interview puzzlesFunny RiddlesGeneral KnowledgeGeographical PuzzleGoogle Code Jam 2014Google Interview PuzzlesGRE PuzzleHard Puzzle