Bill
BAN USER- 2of 4 votes
AnswersWe have a long string. We label some substrings with tags.
- Bill in United States
- A tag entry is [startIndex, endIndex, tag].
- Query: 1 or more tags
- Output: all blocks/ranges with all queried tags.
Example tag entries:
[23, 72, 0] // label [23, 72) with tag 0
[34, 53, 1] // label [34, 53) with tag 1
[100, 128, 0]
Query and Output:
0 => [23, 72], [100, 128]
0,1 => [34,53] // [34, 53) matches both tag 0 and 1
Give an efficient algorithm. Please describe your algorithm before posting code.
**Edit**: To add some difficulties, partial overlap is treated the same as full overlap, ONLY the overlapped part matches both tags. E.g. if we have entries:
[23, 72, 0] // label [23, 72) with tag 0
[10, 53, 1] // label [34, 53) with tag 1
Query and Output:
0,1 => [23,53] // [23, 53) matches both tag 0 and 1
Minor detials: Note in the comments we used open range on the right, i.e. if the string named "str", [23, 72, 0] includes str[23] but NOT str[72]; and there's no overlap between the following entries:
[23, 72, 0]
[10, 23, 0]| Report Duplicate | Flag | PURGE
Google Senior Software Development Engineer Algorithm
@EPavlova, to clarify, "long string" doesn't mean you can't process intersection. And Time complexity is valued over space complexity.
- Bill January 20, 2016Happy hacking!^^