Headline twins
MediumOnline Assessment
Collapse near-duplicate news headlines from a wire feed, keeping the first story of each cluster.
Turn each headline into a set of words: lowercase it, split it into maximal runs of letters and digits (every other character is a separator, so "U.S." gives u and s), discard these stop words: the a an of to in on for and at is, and put what is left into a set (a repeated word counts once). A headline can end up with an empty set.
Two headlines are twins if their word sets are identical (this includes two empty sets), or if shared × 100 >= percent × total, where shared is the number of words in both sets and total is the number of words in at least one of them.
Process the headlines in order. A headline that is a twin of at least one headline *kept so far* is dropped, and it is attributed to the earliest kept headline it is a twin of. Otherwise it is kept and attributed to itself. Only kept headlines are ever compared against, and dropped headlines do not take part, so twin-ness is not carried along a chain.
Input: headlines, a list of strings, and percent, an integer.
Output: a list with one integer per headline: the index of the kept headline it is attributed to.
Example 1
- Input:
- [["Rain floods the old town","Rain floods old town streets","Streets flooded in old town after rain","RAIN, FLOODS: the old town!"],50]
- Output:
- [0,0,2,0]
- Explanation
- With a 50% threshold, headline 1 is a twin of headline 0 (4 shared words out of 5 distinct, 80%), so it is dropped. Headline 2 shares only 3 of 7 words with headline 0 (43%), so it is kept. It would match headline 1 (4 of 7, 57%), but headline 1 was dropped, so it does not count. Headline 3 has exactly headline 0's words once case, punctuation and the stop word "the" are ignored, so it points to 0.
Example 2
- Input:
- [["U.S. jobs up 3%","US jobs up 3","3 up jobs, S. U.","The an a","To of the"],100]
- Output:
- [0,1,0,3,3]
- Explanation
- At 100% only identical word sets are twins. Headline 2 has the same words as headline 0 in another order. Headlines 3 and 4 contain only stop words, so both have an empty set; two empty sets are identical, so 4 points to 3.
Example 3
- Input:
- [["Tech giant buys startup","Chip maker buys startup","Tech giant buys chip maker startup"],40]
- Output:
- [0,1,0]
- Explanation
- At 40%, headline 1 shares 2 of 6 words with headline 0 (33%), so it is kept. Headline 2 is a twin of both kept headlines (4 of 6, 67%, against each); it points to the earliest, headline 0.
Constraints
0 <= headlines.length <= 300- Each headline is 0 to 80 printable ASCII characters
1 <= percent <= 100