How long are the chains?

Scenario

Kestrel Observe stores request ids in a hash table with separate chaining. A key goes to bucket key mod buckets, and each bucket keeps a chain of the distinct keys that landed there.

Before tuning the table, the performance team wants a histogram of chain lengths. How many buckets are empty, how many hold one key, how many hold two, and so on up to the longest chain. A key that arrives twice is stored once.

Your task

Write chain_histogram(keys, buckets).

keys[i] is a request id. The same id may arrive more than once, and it is stored once.
A key is stored in bucket key % buckets.
Let longest be the length of the longest chain. Return a list of longest + 1 numbers, where entry k is the number of buckets that hold exactly k distinct keys.
Entry 0 counts the empty buckets. The last entry is at least 1.

Examples

Example 1 (traced)#

text2 lines

Input:  keys = [12, 7, 12, 22, 3, 17, 9], buckets = 5
Output: [2, 2, 0, 0, 1]

Reading the keys in order, the trace stores each new key and counts its bucket. Then it counts how many buckets have each length.

Key	Repeat	Bucket	counts after
12	no	2	0, 0, 1, 0, 0
7	no	2	0, 0, 2, 0, 0
12	yes		0, 0, 2, 0, 0
22	no	2	0, 0, 3, 0, 0
3	no	3	0, 0, 3, 1, 0
17	no	2	0, 0, 4, 1, 0
9	no	4	0, 0, 4, 1, 1

The final chain lengths are 0, 0, 4, 1 and 1. That is 2 empty buckets, 2 chains of length 1, and 1 chain of length 4. The histogram has entries for lengths 0 to 4: [2, 2, 0, 0, 1].

Example 2#

text2 lines

Input:  keys = [4, 4, 4], buckets = 3
Output: [2, 1]

One distinct key sits in bucket 1. Two buckets are empty, and one bucket holds one key.

Example 3#

text2 lines

Input:  keys = [1, 2, 3, 4], buckets = 1
Output: [0, 0, 0, 0, 1]

One bucket holds all four distinct keys.

Constraints

1 ≤ keys.length ≤ 100,000 (requests in one batch)
1 ≤ keys[i] ≤ 10^9 (request ids)
1 ≤ buckets ≤ 100,000

What does n ≤ 10^5 tell you?

Scanning every key once for every bucket costs buckets × n checks, which is 10^10 at the largest size, with a chain scan for each key. That is far over the budget of about 10^8 simple operations a second. Counting each new key into its bucket in a single pass makes about n steps, and counting the buckets makes about buckets steps.

Read the values too. A key is at most 10^9, which fits in a 32-bit int, and the histogram has at most n + 1 entries.

Scenario

Kestrel Observe stores request ids in a hash table with separate chaining. A key goes to bucket key mod buckets, and each bucket keeps a chain of the distinct keys that landed there.

Your task

Write chain_histogram(keys, buckets).

keys[i] is a request id. The same id may arrive more than once, and it is stored once.
A key is stored in bucket key % buckets.
Let longest be the length of the longest chain. Return a list of longest + 1 numbers, where entry k is the number of buckets that hold exactly k distinct keys.
Entry 0 counts the empty buckets. The last entry is at least 1.

Examples

Example 1 (traced)#

text2 lines

Input:  keys = [12, 7, 12, 22, 3, 17, 9], buckets = 5
Output: [2, 2, 0, 0, 1]

Reading the keys in order, the trace stores each new key and counts its bucket. Then it counts how many buckets have each length.

Key	Repeat	Bucket	counts after
12	no	2	0, 0, 1, 0, 0
7	no	2	0, 0, 2, 0, 0
12	yes		0, 0, 2, 0, 0
22	no	2	0, 0, 3, 0, 0
3	no	3	0, 0, 3, 1, 0
17	no	2	0, 0, 4, 1, 0
9	no	4	0, 0, 4, 1, 1

The final chain lengths are 0, 0, 4, 1 and 1. That is 2 empty buckets, 2 chains of length 1, and 1 chain of length 4. The histogram has entries for lengths 0 to 4: [2, 2, 0, 0, 1].

Example 2#

text2 lines

Input:  keys = [4, 4, 4], buckets = 3
Output: [2, 1]

One distinct key sits in bucket 1. Two buckets are empty, and one bucket holds one key.

Example 3#

text2 lines

Input:  keys = [1, 2, 3, 4], buckets = 1
Output: [0, 0, 0, 0, 1]

One bucket holds all four distinct keys.

Constraints

1 ≤ keys.length ≤ 100,000 (requests in one batch)
1 ≤ keys[i] ≤ 10^9 (request ids)
1 ≤ buckets ≤ 100,000

What does n ≤ 10^5 tell you?

Read the values too. A key is at most 10^9, which fits in a 32-bit int, and the histogram has at most n + 1 entries.