1
function shuffle<T>(arr: T[]): T[] {
2
  for (let i = arr.length - 1; i > 0; i--) {
3
    const j = Math.floor(Math.random() * (i + 1));
4
    [arr[i], arr[j]] = [arr[j], arr[i]];
5
  }
6

7
  return arr;
8
}

1
function reservoirSampling<T>(stream: T[], k: number): T[] {
2
  const reservoir: T[] = [];
3

4
  for (let i = 0; i < stream.length; i++) {
5
    if (i < k) {
6
      reservoir.push(stream[i]);
7
    } else {
8
      const j = Math.floor(Math.random() * (i + 1));
9
      if (j < k) reservoir[j] = stream[i];
10
    }
11
  }
12

13
  return reservoir;
14
}

1
interface WeightedItem<T> {
2
  value: T;
3
  weight: number;
4
}
5

6
function weightedRandom<T>(items: WeightedItem<T>[]): T {
7
  const total = items.reduce((sum, item) => sum + item.weight, 0);
8
  let random = Math.random() * total;
9

10
  for (const item of items) {
11
    random -= item.weight;
12
    if (random <= 0) return item.value;
13
  }
14

15
  return items[items.length - 1].value;
16
}

1
class WeightedPicker<T> {
2
  private values: T[];
3
  private prefix: number[] = [];
4
  private total = 0;
5

6
  constructor(items: WeightedItem<T>[]) {
7
    this.values = items.map(item => item.value);
8

9
    for (const item of items) {
10
      this.total += item.weight;
11
      this.prefix.push(this.total);
12
    }
13
  }
14

15
  pick(): T {
16
    const target = Math.random() * this.total;
17
    let left = 0;
18
    let right = this.prefix.length - 1;
19

20
    while (left < right) {
21
      const mid = left + Math.floor((right - left) / 2);
22
      if (this.prefix[mid] < target) left = mid + 1;
23
      else right = mid;
24
    }
25

26
    return this.values[left];
27
  }
28
}

1
function estimatePi(samples = 1_000_000): number {
2
  let inside = 0;
3

4
  for (let i = 0; i < samples; i++) {
5
    const x = Math.random();
6
    const y = Math.random();
7
    if (x * x + y * y <= 1) inside++;
8
  }
9

10
  return (inside / samples) * 4;
11
}

1
class ABTesting {
2
  private variants: string[];
3
  private weights: number[];
4

5
  constructor(config: Record<string, number>) {
6
    this.variants = Object.keys(config);
7
    this.weights = Object.values(config);
8
  }
9

10
  assign(userId: string): string {
11
    const total = this.weights.reduce((sum, weight) => sum + weight, 0);
12
    const bucket = this.hashCode(userId) % total;
13
    let current = 0;
14

15
    for (let i = 0; i < this.variants.length; i++) {
16
      current += this.weights[i];
17
      if (bucket < current) return this.variants[i];
18
    }
19

20
    return this.variants[this.variants.length - 1];
21
  }
22

23
  private hashCode(str: string): number {
24
    let hash = 0;
25
    for (let i = 0; i < str.length; i++) {
26
      hash = ((hash << 5) - hash + str.charCodeAt(i)) | 0;
27
    }
28
    return Math.abs(hash);
29
  }
30
}