FastPrepDuplicate News Within 60 Seconds

Duplicate News Within 60 Seconds

Bloomberg LP logoBloomberg LP● MediumFULLTIMEPHONE SCREEN

Updated

Problem statement

A news feed receives items one at a time, in time order. Item i has an id ids[i], a text contents[i], a title titles[i] and an arrival time times[i] in seconds.

Item i is a duplicate when some earlier item j (with j < i) has exactly the same content and times[i] - times[j] < 60. The earlier item can itself be a duplicate. A gap of exactly 60 seconds does not count, and a gap of 0 does. Ids and titles are never used to decide whether an item is a duplicate.

Return the ids of all duplicate items in arrival order. Return an empty array if there are none.

A good solution does not keep every item it has seen. Once the newest item is 60 or more seconds after an older one, that older one can never make a later item a duplicate, so it can be forgotten.

Function

findDuplicateNews(ids: String[], contents: String[], titles: String[], times: int[]) → String[]

Examples

Example 1

ids = ["id1","id2","id3","id4"]contents = ["t1","t2","t1","t1"]titles = ["t1","t2","t1","t1"]times = [2,4,50,80]return = ["id3","id4"]

Item id3 has the same content t1 as id1, and it arrives 50 - 2 = 48 seconds later. That is less than 60, so it is a duplicate.

Item id4 has content t1 too. The closest earlier item with that content is id3, 80 - 50 = 30 seconds before. That counts even though id3 is a duplicate itself. Item id2 is the only item with content t2, so it is not a duplicate.

Example 2

ids = ["p","q","r"]contents = ["a","a","a"]titles = ["x","x","x"]times = [10,69,129]return = ["q"]

Item q arrives 69 - 10 = 59 seconds after p with the same content. That is less than 60, so it is a duplicate.

Item r arrives 129 - 69 = 60 seconds after q. A gap of exactly 60 does not count, and p is even older, so r is not a duplicate.

Example 3

ids = ["n1","n2","n3","n4"]contents = ["x","x","y","x"]titles = ["alpha","beta","alpha","gamma"]times = [5,5,5,6]return = ["n2","n4"]

Item n2 has the same content x as n1 and arrives at the same second, a gap of 0. It is a duplicate, even though the titles are different.

Item n3 has the same title as n1 but different content, so it is not a duplicate. Item n4 has content x and arrives 1 second after n2, so it is a duplicate.

Example 4

ids = ["a","b","c"]contents = ["u","v","w"]titles = ["u","v","w"]times = [1,2,3]return = []

All three contents are different, so no item repeats an earlier one. The result is an empty array.

Constraints

  • 1 <= ids.length <= 10^5
  • ids.length == contents.length == titles.length == times.length
  • 1 <= ids[i].length, contents[i].length, titles[i].length <= 20
  • ids[i], contents[i] and titles[i] use only lowercase English letters and digits.
  • All values in ids are different.
  • 0 <= times[i] <= 10^9, and times[i] <= times[i + 1].

More Bloomberg LP Phone Screen questions

Similar questions at other companies

Interview reports that mention this question

Bloomberg LP interview experiences

All Bloomberg LP interview questionsSee Bloomberg LP hiring insights
Saved
class Solution {
    public String[] findDuplicateNews(String[] ids, String[] contents, String[] titles, int[] times) {
        // Write your code here.
    }
}
Checking account…