【Amazon面经】SDE I Interview Leetcode Question Amazon OA 开发岗

兔精精 2020-7-8 694


Question:

Suppose I have a list of intervals that is unsorted and non-overlapping (start, end), intervals, produce a random int within the intervals where each number in the interval has a uniform distribution.

Challenge: in O(n) time? Bigger Challenge: iin O(1) space?

Example: intervals = [(7,9),(3, 5)] Possible results include: [3,4,5,7,8,9] omit 6

最新回复 (1)
  • Crusader 6月前
    0 引用 2

    O(1) space solution.

    
    import random
    import pprint
    
    def interval_random(intervals):
       # find how many numbers
       total = 0
    
       for interval in intervals:
           total += interval[1] - interval[0] + 1
       # get random sequence number
       seq = random.randint(0, total-1)
    
       # go through intervals again to cherry pick the original integer
       # corresponding to the global sequence number
       for interval in intervals:
           if seq < interval[1] - interval[0] + 1:
               return seq + interval[0]
           # here you only need to offset the current seq by length of the
           # last interval
           seq -= interval[1] - interval[0] + 1
       return seq + intervals[-1][0]
    
    if __name__ == "__main__":
       intervals = [(7,9),(3, 5), (10, 18), (20, 26), (30, 32)]
       print(interval_random(intervals))
    
       # uniform distribution test
       counts = {}
    
       for i in xrange(0, 2500000):
           result = interval_random(intervals)
           if result not in counts:
               counts[result] = 1
           else:
               counts[result] += 1
       print(len(counts))
       pp = pprint.PrettyPrinter(depth=6)
       pp.pprint(counts)
    
    """
    Output:
    21
    25
    {3: 100269,
    4: 100183,
    5: 99901,
    7: 99685,
    8: 100031,
    9: 100330,
    10: 99832,
    11: 100394,
    12: 99429,
    13: 99923,
    14: 100082,
    15: 100060,
    16: 100049,
    17: 100479,
    18: 100327,
    20: 99947,
    21: 99986,
    22: 99299,
    23: 100115,
    24: 100104,
    25: 99638,
    26: 99741,
    30: 100056,
    31: 100045,
    32: 100095}
    """
    上传的附件:
返回