Learn
Practice
Interview
Resources
Newsletter
F
Toggle theme
0
F
0
Toggle menu
Animations
← Back to All Animations
Random Pick with Weight
Bookmark
Linear Scan
Binary Search
Alias Method
Input
Standard
Equal weights
Single weight
Large first
Custom
weights
=
[1, 3, 2, 4]
,
target
=
7
weights
0
1
1
3
2
2
3
4
weights
0
1
1
3
2
2
3
4
Phase 1: Build Prefix Sum
weights
0
1
1
3
2
2
3
4
prefixSum
0
1
Phase 1: Build Prefix Sum
weights
0
1
1
3
2
2
3
4
prefixSum
0
1
1
4
2
6
Phase 1: Build Prefix Sum
weights
0
1
1
3
2
2
3
4
prefixSum
0
1
1
4
2
6
3
10
Phase 1: Build Prefix Sum
weights
0
1
1
3
2
2
3
4
prefixSum
0
1
1
4
2
6
3
10
total = 10
Phase 2: pickIndex()
weights
0
1
1
3
2
2
3
4
prefixSum
0
1
1
4
2
6
3
10
target = 7
Phase 2: pickIndex()
weights
0
1
1
3
2
2
3
4
prefixSum
0
1
1
4
2
6
3
10
i
target = 7
Phase 2: pickIndex()
weights
0
1
1
3
2
2
3
4
prefixSum
0
1
1
4
2
6
3
10
i
target = 7
Phase 2: pickIndex()
weights
0
1
1
3
2
2
3
4
prefixSum
0
1
1
4
2
6
3
10
i
target = 7
Phase 2: pickIndex()
weights
0
1
1
3
2
2
3
4
prefixSum
0
1
1
4
2
6
3
10
target = 7
Result: index 3
algo
master
.
io
Step:
Start: build the prefix sum, then linearly scan for the target bucket
0 / 12
Input
Standard
Equal weights
Single weight
Large first
Custom
weights
=
[1, 3, 2, 4]
,
target
=
7
0 / 12
algo
master
.
io
Step:
Start: build the prefix sum, then linearly scan for the target bucket
