2dbi
Home/Elastic/Intersection of Sorted Posting Lists
EElastic·DSAEngineerOnsite – Coding 1

Intersection of Sorted Posting Lists

Problem

Given multiple sorted lists of document IDs (postings), return the IDs present in all of them.

Example

[1,2,4,8],[2,4,9],[2,4,5] -> [2,4]

Constraints

  • Lists can be large

Approach

Multi-pointer advance on the smallest; basis of AND queries in an inverted index.

added 6 days ago
LeadersAccount