Posted on

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

Posted on

Slices of pizza


A logic test from a job selection process:

Cut slices of a pizza with exactly 8 straight cuts. How many (at most) slices can you get?

Solution

  1. With 0 cuts I get 1 slice, i.e. the whole pizza.

  2. With 1 cut I get 2 slices, wherever I cut the pizza through.

  3. With 2 cuts I get 4 slices, if the second cut crosses the first one at any point (inside the pizza).

  4. With 3 cuts I can make a straight cut that crosses all of the previous cuts at different points (inside the pizza).

    • Each cut defines two slices (one on each side)

    • but N cuts define N + 1 slices

      because N – 1 slices are shared between each cut and the next, thus 2N – (N – 1) == N + 1.

    • I’m crossing all the N = 2 cuts from the previous step, which define N + 1 == 3 slices of the X = 4 slices.

    Thus I now get X – (N + 1) + 2 * (N + 1) slices == X + N + 1 == 4 + 3 == 7 slices.

  5. With 4 cuts, I get 7 + 4 == 11 slices.

  6. With 5 cuts, I get 11 + 5 == 16 slices.

  7. With 6 cuts, I get 16 + 6 == 22 slices.

  8. With 7 cuts, I get 22 + 7 == 29 slices.

  9. With 8 cuts, I get 29 + 8 == 37 slices.

Posted on

12 Parties


A logic test from a job selection process:

A nation’s people can vote for members of parliament from 12 parties. One voter must cast only one vote for one representative. If a party doesn’t get more than 5% of votes, then it won’t get any chairs in the parliament. How many chairs can get (at most) the party which collects 25% of votes?

Solution

  1. If V1 == 25%, then Sum(Vi, i=2..12) == 75%

  2. The best for P1 would be that the other parties get 5% of votes, so that they lower the 75% but don’t get any chairs.

    • 5% * 11 = 55% < 75%
      11 other parties cannot get 5% each because there are no parties left to absorb the remaining 20% of votes.

    • 5% * 10 = 50% -> V2 = 75% – 50% == 25%
      10 other parties can get 5% each instead because the remaining party can get the remaining 25% of votes.

  3. Only P1 and P2 will share the parliament, and each of them with 50% of the chairs.