6 votes
Accepted

Improving a ranking system with "best rank"

Each query can be implemented to run in $O(\log n)$ time by lazily propagating appropriate operators on the binary search tree. The lazy propagation technique *1, is that it is possible to perform ...
pcpthm's user avatar
  • 2,339
2 votes

Recursive formula for height of BST

The formula is wrong. Indeed, we can find by hand that $H(1) = 0$, $H(2) = 1$ and $H(3) = \frac95$ ($5$ different trees, $4$ of them being of height $2$, the last of height $1$). But: $$\frac13\sum\...
Nathaniel's user avatar
  • 13.9k
1 vote
Accepted

Data structure to keep track of cache hit ratio?

What you're looking for is not so much a data structure as a problem statement. What is it that you're trying to learn from a metric such as a hit-count? The structures need to match what you're ...
Cort Ammon's user avatar
  • 3,286
1 vote

How to optimize algorithm to solve the following time series problem?

First, apply the standard reduction: to solve a ratio maximization problem (sometimes called "fractional programming"), binary search on the solution $t$: $$ \max_x \frac{f(x)}{g(x)} \geq t \...
pcpthm's user avatar
  • 2,339

Only top scored, non community-wiki answers of a minimum length are eligible