> For the complete documentation index, see [llms.txt](https://mabuxi.gitbook.io/mabuxi/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://mabuxi.gitbook.io/mabuxi/leetcode-summary/advanced-algorithm/reservoir-sampling.md).

# Reservoir Sampling

**Reservoir Sampling** is a family of randomized algorithms for randomly choosing a sample of `k` items from a list `S` containing `n` items, where `n` is either **a very large or unknown** number. Typically, `n` is large enough that the list **doesn't fit into memory**.

## Essentials

### Problem: 

* Choose `k` entries from `n` numbers. Make sure each number is selected with the probability of `k/n` 

### Basic idea: 

* Choose `1, 2, 3, ..., k` first and put them into the reservoir.
* For `k+1` , pick it with a probability of `k/(k+1)` , and randomly replace a number in the reservoir.
* For `k+i` , pick it with a probability of `k/(k+i)` , and randomly replace a number in the reservoir.
* Repeat until `k+i` reaches `n` 

### Proof: 

* For `k+i` , the probability that it is selected and will replace a number in the reservoir is `k/(k+i)` 
* For a number in the reservoir before (let's say `X`), the probability that it keeps staying in the reservoir is 
  * `P(X was in the reservoir last time)` x `P(X is not replaced by k+i)` 
  * \= `P(X was in the reservoir last time)` x `(1 - P(k+i is selected and replaces X))` 
  * \= `k/(k+i-1)` x `(1 - k/(k+i) x 1/k)` 
  * \= `k/(k+i)` 
* When `k+i` reaches `n` , the probability of each number staying in the reservoir is `k/n` 

### Example 

* Choose `3` numbers from `[111, 222, 333, 444]`. Make sure each number is selected with a probability of `3/4` 
* First, choose `[111, 222, 333]` as the initial reservior. 
* Then choose `444` with a probability of `3/4` 
* For 111 , it stays with a probability of 
  * `P(444 is not selected)` + `P(444 is selected but it replaces 222 or 333)` 
  * \= `1/4` + `3/4` \* `2/3` 
  * \= `3/4` 
* The same case with `222` and `333` 
* Now all the numbers have the probability of `3/4` to be picked

## 经典题目

[*382 Linked List Random Node*](https://leetcode.com/problems/linked-list-random-node/description/)\
[*398 Random Pick Index*](https://leetcode.com/problems/random-pick-index/description/)

{% tabs %}
{% tab title="382 Solution" %}

```java
class Solution {
    private ListNode head;
    /** @param head The linked list's head.
        Note that the head is guaranteed to be not null, so it contains at least one node. */
    public Solution(ListNode head) {
        this.head = head;
    }
    /** Returns a random node's value. */
    public int getRandom() {
        ListNode cur = head;
        int ans = cur.val;
        int i = 0;
        Random random = new Random();
        for (; cur != null; i++) {
            if (random.nextInt(i + 1) == i) {
                ans = cur.val;
            }
            cur = cur.next;
        }
        return ans;
    }
}
```

{% endtab %}

{% tab title="398 Solution" %}

```java
class Solution {
    private int[] nums;
    public Solution(int[] nums) {
        this.nums = nums;
    }
    public int pick(int target) {
        Random rd = new Random();
        int count = 0;
        int ans = 0;
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] == target) {
                if (rd.nextInt(count + 1) == count) {
                    ans = i;
                }
                count += 1;
            }
        }
        return ans;
    }
}
```

{% endtab %}
{% endtabs %}


---

# Agent Instructions
This documentation is published with GitBook. GitBook is the documentation platform designed so that both humans and AI agents can read, navigate, and reason over technical content effectively. Learn more at gitbook.com.

## Querying This Documentation
If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter, and the optional `goal` query parameter:

```
GET https://mabuxi.gitbook.io/mabuxi/leetcode-summary/advanced-algorithm/reservoir-sampling.md?ask=<question>&goal=<endgoal>
```

`ask` is the immediate question: it should be specific, self-contained, and written in natural language.
`goal` is optional and describes the broader end goal you are ultimately trying to accomplish on behalf of the user. GitBook uses it to tailor the answer towards what is most useful for that goal.

The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.