# Tag Info

### Data Structure for Set Intersection?

The keyword to search for is inverted indexes, this kind of data structure is very common in that context. Depending on what your set elements look like, tries allow for sub-linear time merging if the ...
• 131

### Best online algorithm for a monotone priority queue that has equal amount of deletion and insertions

For say 100 items a priority queue will be just fast enough. You could take an unsorted queue for anything far in the future. Set a “future time threshold” = now plus one hour; you don’t change this ...
• 30.6k
1 vote

### Trie minimization when order doesn't matter

Sticking to frequency count is your best bet here probably
• 61
1 vote

### Top K Most Frequent Elements and Bucket Sorting Intuition

Call the mapping value→count a histogram. (If there are $m \le n/\log n$ entries, you have time for an $m\log m$ processing step).) Counting sort (bucket sort with bucket size 1) is just one procedure ...
• 1,074

### Selecting a subtree in an array representation of a binary tree

@Bulat descendant >> (hsbit(descendant) - hsbit(ancestor)) == ancestor This does not appear to work for descendant = 2 (0b10), ...
1 vote

### Detect if an interval is fully covered by union of previous intervals in sequence

I think I have worked out a solution that takes $O(n \log n)$ time. It relies on a regular interval tree which has $O(\log n + m)$ query (for $m$ overlapping intervals) and $O(\log n)$ insertion and ...
• 163

• 111
### Optimal lookup complexity when requiring insertion complexity to be at most $\mathcal O(\log\log n)$?
After mulling this over for a long time, I've convinced myself that there is no optimal lookup complexity when insertion complexity is limited to $\mathcal O(\log\log n)$. I've written up my reasoning ...