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

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`

• 6月前
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 - interval + 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 - interval + 1:
return seq + interval
# here you only need to offset the current seq by length of the
# last interval
seq -= interval - interval + 1
return seq + intervals[-1]

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}
"""``````
上传的附件：