# Web Duplicates

A logic test from a job selection process:

Web search engines A and B each crawl a random subset of the same size of the Web. Some of the pages crawled are duplicates – exact textual copies of each other at different URLs. Assume that duplicates are distributed uniformly amongst the pages crawled by A and B. Further, assume that a duplicate is a page that has exactly two copies – no pages have more than two copies. A indexes pages without duplicate elimination whereas B indexes only one copy of each duplicate page. The two random subsets have the same size before duplicate elimination. If, 45% of A’s indexed URLs are present in B’s index, while 50% of B’s indexed URLs are present in A’s index, what fraction of the Web consists of pages that do not have a duplicate?

## Solution

Be:

• C_X the number of elements of X
• X = { 1, 2, 3, 2 } -> C_X = 4
• D_X the number of elements of X with a duplicate in X:
• X = { 1, 2, 3, 2 } -> D_X = 1
• N_X the number of elements of X without a duplicate in X
• X = { 1, 2, 3, 2 } -> N_X = 2
• XY the union of X and Y

• X1 the set X before eliminating duplicates

• X2 the set X after eliminating duplicates

Data:

1. Web search engines A and B each crawl a random subset of the same size of the Web
• C_A1 + C_B1 = C_W
2. The two random subsets have the same size before duplicate elimination
• C_A1 = C_B1
3. Assume that duplicates are distributed uniformly amongst the pages crawled by A and B
• D_A1 = D_B1
4. Further, assume that a duplicate is a page that has exactly two copies – no pages have more than two copies
• C_A1 = 2 * D_A1 + D_AB + N_A1
• C_B1 = 2 * D_B1 + D_AB + N_B1
5. A indexes pages without duplicate elimination whereas B indexes only one copy of each duplicate page
• C_A2 = C_A1
• C_B2 = C_B1 – D_B1
6. 45% of A’s indexed URLs are present in B’s index, while 50% of B’s indexed URLs are present in A’s index
• D_AB (in B2) = 45/100 * C_A2
• D_AB (in A2) = 50/100 * C_B2
7. N_AB / C_W = ?

Example (without taking into account Data:6):

• A1 = 1 1 3 3 5 5 7 9 11 13 15

• B1 = 2 2 4 4 6 6 7 9 10 12 14

• A2 = A1

• B2 = 2 4 6 7 9 10 12 14

Solution:

1. N_AB = N_A1 + N_B1 — by definition.

2. N_A1 = C_A1 – 2 * D_A1 – D_AB — because of Data:4.

3. N_B1 = C_B1 – 2 * D_B1 – D_AB — because of Data:4.

4. N_B1 = C_A1 – 2 * D_A1 – D_AB — because of Solution:3 + Data:2 + Data:3

5. N_AB = 2 * C_A1 – 4 * D_A1 – 2 * D_AB — because of Solution:1 + Solution:2 + Solution:4

6. C_B2 = C_A1 – D_A1 — because of Data:5 + Data:2 + Data:3

7. 45/100 * C_A2 = 50/100 * C_B2 — because of Data:6

8. 45/100 * C_A1 = 50/100 * ( C_B1 – D_B1 ) — because of Solution:7 + Data:5

9. 45/100 * C_A1 = 50/100 * ( C_A1 – D_A1 ) — because of Data:2 + Data:3

10. D_A1 = 10/100 * C_A1 — because of Solution:9

11. N_AB = 200/100 * C_A1 – 4 * 10/100 * C_A1 – 2 * 45/100 * C_A1 — because of Solution:5 + Solution:10 + Data:6 + Data:5

12. N_AB = 70/100 * C_A1 — because of Solution:11

13. N_AB = 70/100 * 50/100 * C_W — because of Solution:12 + Data:1 + Data:2

14. N_AB / C_W === 35% — because of Solution:13

This site uses Akismet to reduce spam. Learn how your comment data is processed.