Overlap score of two ad profiles

Scenario

An ad platform describes each user by an interest profile: a list of topics the user has engaged with, and a weight for each. A topic is a number from a huge catalogue, so a profile holds only a few of them.

To match two users, the platform multiplies their weights on every topic they share and adds the results. Topics only one user has add nothing. You compute that overlap score.

Your task

Write overlap_score(a_topics, a_weights, b_topics, b_weights).

Profile A has a_topics[i] with weight a_weights[i]. Profile B has b_topics[j] with weight b_weights[j].
A topic appears at most once inside one profile, and the topics come in no particular order.
For every topic that appears in both profiles, multiply its two weights. Return the sum of these products. Return 0 when the profiles share no topic.
The sum can be larger than a 32-bit int, so use a 64-bit result.

Examples

Example 1 (traced)#

text2 lines

Input:  a_topics = [7, 3, 9], a_weights = [2, 5, 1], b_topics = [3, 8, 7], b_weights = [4, 6, 3]
Output: 26

The trace stores profile A as a map from topic to weight. Then it reads profile B and looks each topic up.

B topic	B weight	In A's map?	Product	Running total
3	4	yes, weight 5	20	20
8	6	no	0	20
7	3	yes, weight 2	6	26

Topics 3 and 7 are shared. Topics 8 (only B) and 9 (only A) add nothing. The score is 20 + 6 = 26.

Example 2#

text2 lines

Input:  a_topics = [1, 2], a_weights = [5, 5], b_topics = [3], b_weights = [9]
Output: 0

The profiles share no topic, so the score is 0.

Example 3#

text2 lines

Input:  a_topics = [1000000000, 4], a_weights = [10000, 1], b_topics = [4, 1000000000], b_weights = [2, 10000]
Output: 100000002

Topic 1,000,000,000 gives 10,000 × 10,000 = 100,000,000. Topic 4 gives 1 × 2 = 2. The positions differ between the two profiles, so only the topic numbers match them up.

Constraints

1 ≤ a_topics.length = a_weights.length ≤ 100,000 and 1 ≤ b_topics.length = b_weights.length ≤ 100,000 (topics in one profile)
1 ≤ a_topics[i], b_topics[j] ≤ 10^9 (topic numbers)
1 ≤ a_weights[i], b_weights[j] ≤ 10,000 (engagement weights)

What does n ≤ 10^5 tell you?

Comparing every topic of A with every topic of B costs about n × m steps, or 10^10 for two profiles of 100,000 topics. That is far over the budget of about 10^8 simple steps a second. A map from topic to weight finds a partner in one step on average, so building it for A and reading B costs about n + m steps. Topic numbers reach 10^9, so an array indexed by topic is far too big, and a hash map stores only the topics that exist.

Scenario

To match two users, the platform multiplies their weights on every topic they share and adds the results. Topics only one user has add nothing. You compute that overlap score.

Your task

Write overlap_score(a_topics, a_weights, b_topics, b_weights).

Profile A has a_topics[i] with weight a_weights[i]. Profile B has b_topics[j] with weight b_weights[j].
A topic appears at most once inside one profile, and the topics come in no particular order.
For every topic that appears in both profiles, multiply its two weights. Return the sum of these products. Return 0 when the profiles share no topic.
The sum can be larger than a 32-bit int, so use a 64-bit result.

Examples

Example 1 (traced)#

text2 lines

Input:  a_topics = [7, 3, 9], a_weights = [2, 5, 1], b_topics = [3, 8, 7], b_weights = [4, 6, 3]
Output: 26

The trace stores profile A as a map from topic to weight. Then it reads profile B and looks each topic up.

B topic	B weight	In A's map?	Product	Running total
3	4	yes, weight 5	20	20
8	6	no	0	20
7	3	yes, weight 2	6	26

Topics 3 and 7 are shared. Topics 8 (only B) and 9 (only A) add nothing. The score is 20 + 6 = 26.

Example 2#

text2 lines

Input:  a_topics = [1, 2], a_weights = [5, 5], b_topics = [3], b_weights = [9]
Output: 0

The profiles share no topic, so the score is 0.

Example 3#

text2 lines

Input:  a_topics = [1000000000, 4], a_weights = [10000, 1], b_topics = [4, 1000000000], b_weights = [2, 10000]
Output: 100000002

Topic 1,000,000,000 gives 10,000 × 10,000 = 100,000,000. Topic 4 gives 1 × 2 = 2. The positions differ between the two profiles, so only the topic numbers match them up.

Constraints

1 ≤ a_topics.length = a_weights.length ≤ 100,000 and 1 ≤ b_topics.length = b_weights.length ≤ 100,000 (topics in one profile)
1 ≤ a_topics[i], b_topics[j] ≤ 10^9 (topic numbers)
1 ≤ a_weights[i], b_weights[j] ≤ 10,000 (engagement weights)

What does n ≤ 10^5 tell you?