Skip to main content

New answers tagged

0 votes

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 ...
saolof's user avatar
  • 131
0 votes

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 ...
gnasher729's user avatar
  • 30.6k
1 vote

Trie minimization when order doesn't matter

Sticking to frequency count is your best bet here probably
NeedHelp's user avatar
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 ...
greybeard's user avatar
  • 1,074
0 votes

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), ...
Minh Tran's user avatar
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 ...
MattDs17's user avatar
  • 163
0 votes

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

Note, that $$I_i \subseteq \bigcup_{k < i} I_k \iff I_i \cap \overline{\bigcup_{k < i} I_k} = \emptyset \iff \Big(\big((I_i \setminus I_1) \setminus I_2\big) ... \setminus I_{i - 1}\Big) = \...
Knogger's user avatar
  • 1,302
2 votes

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

The intersection of a sequence of intervals $I_1, ..., I_p$ is $$\left[ \max_{i \leq p} s(I_i), \min_{i \leq p} f(I_i) \right],$$ where $s$ and $f$ are the start and finish times is an interval. From ...
Pål GD's user avatar
  • 16.7k
0 votes

Given an AVL tree of size n, is it possible to split the tree into 'k' equal sized search-trees in less than O(n) time?

If you are given an AVL-tree, or any other search tree then I would say that it is not possible to split it into $k > 1$ equal parts without counting which vertices are maximums for each new tree. ...
Smylic's user avatar
  • 303
2 votes
Accepted

Given an AVL tree of size n, is it possible to split the tree into 'k' equal sized search-trees in less than O(n) time?

Convert your AVL tree to an order statistics tree . Now, you can search for the $n/k$ element, the $2n/k$, and so on in $O(\log n) $ time each or $O(k\log n) $ in total. After each search, you can ...
Russel's user avatar
  • 2,780
1 vote

Using XOR operation, a MOD operation compute a function f(n)

As we want to use both operations, we only have two possible combinations: $$\left(n \oplus x\right) \mod s\tag{1}\label{1}$$ $$\left(n \mod x\right) \oplus s\tag{2}$$ If we store $f\left(n\right)$ in ...
Nerrit's user avatar
  • 111
0 votes

Efficient data structure for multidimensional lookup

IF the set of GOOD tuples is fixed and you only need to know if the new point would be classified as GOOD or BAD, then you could train a binary classifier(like a decision tree) to reach the binary ...
Sachith Pai's user avatar
1 vote

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 ...
Franklin Pezzuti Dyer's user avatar

Top 50 recent answers are included