New answers tagged data-structures
1
Since the data structure is only created once, you can simply use an array ordered by the key. Each element in the array contains the key-value pair. Sorting the array is O(n*log(n)), which will be fast for 4e6 items and only needs to be done once. You can then use binary search (which is O(log2(n) or ~22) on the array to find the key. If not found, ...
1
As per a comment of Albert Hendriks, we need to find $i, j, k$ such that $-A[i] = 4A[j] = 5A[k]$.
We can actually do this in a single linear pass. We sweep $i$ from the left, such that $-A[i]$ can only get smaller. We sweep $j, k$ from the right for each possible $i$. But when the left hand side can only get smaller, we don't need to check any $j$ or $k$ ...
2
The amortized cost per increment will be $O(1)$. In order to show it let's use the aggregate method.
0 - 000
1 - 001
2 - 002
3 - 010
4 - 011
5 - 012
6 - 020
7 - 021
8 - 022
9 - 100
10 - 101
11 - 102
12 - 110
13 - 111
14 - 112
15 - 120
...
We can notice that the bits in the 0th place are changing in every ...
-1
This is the actual question should be (Coreman 6.3-3) :A heap of size n has at most ⌈n/2^(h+1)⌉ nodes with height h.
This is just a simple intution for the proof.
This is an easy to prove property of complete binary tree/heap that is
no. of leaf nodes = (total nodes in tree/heap)/2 {nearly}
Now, no. of nodes at height 0 = n/2 (because all leaf nodes are ...
1
Just to add on to the answer provided by @Yuval Filmus to further illustrate why the pair $Y_{i-1},Y_{n-i}$ should be independent on $Z_{n,i}$.
Here is what I got wrong:
From $Y_n = \sum_{i=1}^{n} Z_{n,i} (2\cdot max(Y_{i-1}, Y_{n-i}))$, I had mistakenly thought that $i$ is a random variable. When I put this back into the definitions: $Z_{n,i}$ denotes ...
0
The idea is that the following two experiments produce the same random variable:
A random permutation $\pi$ of $[n]$ subject to $\pi_i = n$.
Choose a random subset $S$ of $[n-1]$ of size $i$, a random permutation $\alpha$ of $S$, a random permutation $\beta$ of $[n-1] \setminus S$, and let $\pi = \alpha, n, \beta$.
The height of a BST based on the $\alpha$ ...
3
Construct a new min-heap $H$ using the root of the original heap $O$ as its only element. Then $k$ times you want to pop the smallest value from $H$, append it to our output array and add the children that node has in $O$ to $H$.
The maximum size $H$ gets here is $k + 1$, so all the above has a complexity of $O(k \log k)$.
If you meant to keep the original ...
0
Kth smallest number in a dynamic stream of numbers.
Idea from the above source.
Have two heaps, one a max heap with $k$ elements (all the elements less than the $k$th largest element and the $k$th largest element itself are here) and the rest of the elements are in the other min heap.
Inserting a new element: If the new element is less than the top of the ...
2
There is an $O(k\log k)$ algorithm pointed out by this SO answer.
Create a sorted list toVisit, which contains the nodes which we will traverse next. This is initially just the root node.
Create an array smallestNodes. Initially this is empty.
While length of smallestNodes < k:
Remove the smallest Node from toVisit
add that node to smallestNodes
...
0
The definitions aren't clearly given in the fragment of the book that Google showed me.
Clearly, if the table has $N$ entries and each entry contains at most one item, you can iterate through all the items in time $\Theta(N)$. Now, if $N$ is some fixed constant, $\Theta(N)$ time is constant time – and the set has constant size. On the other ...
2
I don't agree that the author was talking about iterating over a set with constant time per element. I've never seen iteration described in time per element. It's certainly not common enough to be an unspoken assumption. I would guess that instead it's simply an editing miss.
1
A short (or long?) recall:
Mo's algorithm is used for problems, when you want to answer a lot of range queries over an array, in which it is not possible to generate an efficient data structure like a Segment tree, because combining multiple nodes can be very inefficient. The famous problem is to count the number of distinct elements in ranges $(l, r)$. ...
0
Let's assume you store the nodes by level and then from left to right. Here are the first few levels:
Root: $1$
Children of root: $2,\ldots,k+1$
Grandchildren of root: Children of $2$: $k+2,\ldots,2k+1$; Children of $3$: $2k+2,\ldots,3k+1$, ...
Let us guess that just like in the binary case, the formula for the leftmost child of $v$ is of the form $\alpha ...
1
What is the minimum value of $i$ which can generate all permutations of 1 to $n$ at the output?
The options are: 1) 1 $\;$ 2) 2 $\;$ 3) $n-1$ $\;$ 4) $n$
None of the given options are correct.
All permutations of 1 to 7 can be generated by 3 stacks.
The permutation 7132465 cannot be generated by 2 stacks.
The above facts can be verified by an ...
Top 50 recent answers are included
