New answers tagged data-structures
0
First of all, the question is phrased incorrectly. The following are equivalent and correct expressions of the intended question:
why must we use a prime number as the modulo of the hash value (not "in the hashing function)
or equivalently and more succinctly:
why must the size of a hash table be a prime number?
The proper answer to this question lies ...
0
It's quite normal.
If your hash table is getting too full, you will get a high number of collisions - time to resize the hash table.
If your hash table is not very full, a high number of collisions is possible, but not very likely.
0
You have to be consistent but you are free to decide whether you want a tree that for example has either left or right bias, never both.
When deleting you also have a choice in whether to borrow from left or right first, or whether to merge with left or right first. You need to do both but you can attempt either left or right first.
3
It is not possible to guarantee to find the maximal value that is less than a queried value $V$ in $o(K)$ time with preprocessing in $o(N)$ time.
This can be seen easily in the following extreme case. Let $A$ be any array of $N$ integers, which is composed of the following $K=N-1$ linear subarrays.
the subarray $A[0], A[1]$ with $C=A[1]-A[0]$.
the subarray ...
1
Could you please explain exactly where you were stuck? Anyway, I'll choose some parts of the solution which were not described by author and shed light on them.
You can assume that $T=\sqrt{n}$ in the solution. The main idea can be formulated as follows:
For any positive integers $m, n$ such that $m \le n$ either $m \le \sqrt{n}$ or $\frac{n}{m} < \sqrt{...
4
Augment the tree to store, for each subtree, the minimum of the prefix sums of the sequence of elements in that subtree. Then you can check the supergood condition in $O(\log n)$ time. It's your exercise, so I'll let you work out the details.
Hint #1: every prefix can be decomposed into a union of $O(\log n)$ subtrees.
Hint #2: the minimum of the prefix-...
2
It is on the right direction to try some kind of tree augmented with a global counter that stores the number of all unordered pairs of nodes $\{u,v\}$ such that $v.value+u.value \le d$.
The kind of tree you are looking for is a balanced (binary) search tree. Being balanced such as an AVL tree, it supports insertion, deletion and lookup of a number with $O(\...
2
The number of octrees with $n$ nodes is OEIS sequence A007556:
$$T(n) = {8n \choose n}/(7n+1)$$
I worked this out, incidentally, by writing a short program to generate the first few values of $T(n)$ and then searching for it.
If you had no other information than $n$, then the minimum number of bits required to store an octree with $n$ nodes is $\log\,T(n)$...
0
Here is my approach to understand, mix of both visualization and mathematics.
In the weighted quick union, when we need to do union for two nodes, we join the roots of those two nodes ( basically the smaller tree joins the bigger tree ).
Lets say these are the two trees :-
1 6
/...
0
My question is why use floor(length(a)/2)? How is it different than using length(a)? Is this the same thing?
Since every node at index $⌊𝑛/2⌋+1,⌊𝑛/2⌋+2,⋯,𝑛$ is a leaf node, it is also a root of a subtree max-heap. So no difference.
However, I want to point to another question, perhaps more interesting:
Why do we go backwards and don't start from 1 up ...
0
Sorting is well researched area in the history of computer science and mathematics, so there are a lot of algorithms for sorting. When comparing sort algorithms, I suggest categorizing them from the following view points.
time complexity
As already discussed in the other answers, the three algorithms are in average case $O (n \log n)$ while quick sort worst ...
1
One thing that I haven't seen mentioned is the difference between the space complexities of quicksort and heapsort. An efficient version of quicksort would have O(logn) space, but heapsort is constant O(1) space since no recursion or additional space allocation of any kind is required. That would of course make heapsort more space efficient than merge sort ...
2
I am not sure if choosing stacks/heap is related with object oriented programming. The stacks are adopted by many programming languages because they are perfect fit for scoped variables, e.g. create new stack frame at the beginning of a function, and discard it when leaving. They don't always store reference variables, but actual objects. In C++, you can ...
1
Make an augmented search tree. This is an ordinary binary search tree, where each node additionally stores the number of elements in its subtree. This data structure is known as order statistic tree.
If we balance the BST (making it an AVL tree for instance) then insertion can, of course, be done in logarithmic time (incrementing the node count along the ...
0
You can use Heaps. Min heaps can find kth smallest element in O(k* logn) i.e O(logn) times if heap is already build. If not in O(n + k*logn) times i.e. in O(n) time if heap is to be build from the scratch.
You can refer - https://www.geeksforgeeks.org/kth-smallestlargest-element-unsorted-array/ for more informaiton
Insertion can be done in O(logn) times in ...
Top 50 recent answers are included
