New answers tagged data-structures
0
gnasher729's solution is often a good one, from a pragmatic perspective. It achieves linear time iteration as long as you ensure that the load factor of the hash table is bounded below by a constant.
Another alternative is to maintain a doubly-linked list of all of the hash slots. In other words, each hash slot also has a "next" and "prev&...
2
In most implementations slots must be clearly recognisable as either "never used", "previously used but not used anymore" or "used, containing a hash value". So you just iterate over the stored hash values and use those that are neither "never used" nor "not used anymore".
Execution time is linear in the ...
0
The statement is not correct. You can use your counter-example from before, and add redundant nodes to it.
Since the bellman-ford algorithm runs iterations equal to the number of nodes in the graph - you will see that nodes that are reachable from a negative cycle (but not on the negative cycle) will also get updated.
The correct statement
To clear things ...
0
You are right that this statement is not correct. Since, especially, $t$ will potentially be updated after $n$ iterations.
A correct statement is that if a vertex $v$ gets updated after the $n$ first rounds, then there is a path from $s$ to a negative cycle $C$ that ends in $v$.
To find a negative cycle, you start from $v$ (the vertex that gets updated in ...
0
Well, first of all, i_right = i_left + 1. Always. It's obvious, so bellow I'm gonna show only proof of expression i_left_child = i_parent * 2 + 1.
In the explanation bellow there might be quite many definitions like: parent, child, index, position in current level, etc. So instead of greek/latin letters I decided to use the exact numbers from picture, but ...
0
Suppose that $n \geq 1$ and $d \geq 2$. On the one hand,
$$
\lceil \log_d(n(d-1)+1)-1 \rceil \leq \log_d(2dn) \leq \log_d n + 2.
$$
On the other hand,
$$
\lceil \log_d(n(d-1)+1)-1 \rceil \geq \log_d(nd/2)-1 = \log_d n - 1.
$$
In other words, your expression is equal to $\log_d n$ up to a constant additive term.
In particular, if we fix $d$ then your ...
0
kudos, The title of question if alone is to be considered- does have an ambitious idea, as there does exist a related research paper which sorts in linear time provided the constraints of no duplicates and knowing the range of input (gaps are allowed): Hash sort: A linear time complexity multiple-dimensional sort algorithm
However the steps mentioned in the ...
1
A plausible data structure might be a quadtree, where you augment each internal node with the priority of the highest-priority task contained within that region. This will let you do a best-first search, i.e., search first in regions that contain high-priority tasks, and avoid recursing into any region whose highest-priority task is of a lower priority than ...
0
Sparse Tables
For each index i of array, we store minimum of blocks of 2 powers till block index's doesn't exceed array length.
Any non-negative number can be uniquely represented as a sum of decreasing powers of two. This is just a variant of the binary representation of a number.
E.g. $13 = (1101)_2 = 8 + 4 + 1$.
E.g. $[2, 14] = [2, 9] \cup [10, 13] \cup [...
0
In this case, k can vary from 1 to n.
1
We might be interested in finding 1st from Beginning and 1st from End.
Time Complexities of these are respectively $O(1)$ and $O(n)$.
OR
n
We might be interested in finding nth Element from Beginning (Last Element of Linked List) and nth Element from End (First Element of Linked List)
Time Complexities of these ...
0
The definition given in this Textbook says that
A data structure is a way to store and organize data in order to facilitate access and modifications.
Again, highlighting key words:
A data structure is a way to store and organize data in order to facilitate access and modifications.
Now, analogous to real world, if we want to store something, there are ...
1
You have to make a distinction between abstract data structures and "data structure".
An abstract data structure (for instance the stack) is usually understood as the description of a collection of operations, and the semantic expected from those operations. It is only a specification, an interface.
A data structure (for instance a doubly-linked ...
6
I can't answer that question reliably, because it depends on the behavior of the memory allocator in Python, and I don't think we're provided any guarantees about that. The memory allocator might deallocate the space after the function returns, or it might deallocate in every iteration.
What we can say is that it is possible to implement this algorithm ...
-2
I think we have a short answer by using probability. we use % (modulo) in hashing to calculate remainder of a division(our data % chosen number). if our mod be a prime number which also is our divisor it is more likely that division has a remainder and less numbers has same factor like our divisor
So less collision happens.
3
There are lots of standard ones, such as:
Octrees
k-d trees
Binary space partitioning
R-trees and their variants
Which one you choose would depend on the properties of your data (e.g. how "clustered" the points are, whether the set of points is static or dynamic) and what queries you wish to perform (e.g. k-nearest-neighbour search).
1
Linear for data structures typically refers to an O(n) algorithm. I.e. the time is bounded by c.n for some constant c > 0. The function f(n) = c.n when represented in the Cartesian plane forms a straight line.
If you purely view linear as "iterating through the data sequentially" then this presumably refers to the fact that the data can be ...
0
This is solvable using a product construction. You construct a new graph $G'=(V',E')$ where each vertex in $V'$ has the form $\langle v,t \rangle$, to keep track of both which vertex you're at ($v$) and the current time ($t$). Then, find a shortest path in $G'$.
To learn more about this approach, for some other examples of a product construction, see, e.g.,...
2
Your solution seems to have higher time complexity than needed. If you have $n$ dogs and then $n$ cats then dequeuing all cats will cost you $O(n^2)$ as you need to go through dogs first.
I'd go with three queues: all animals, dogs, cats.
Enqueue: Create an instance of dog/cat, push into all animals queue. Next, push the same instance to the dog/cat queue ...
0
Let X and Y be the two sets to merge. Each element has a next pointer that ensures that if you follow the pointers, you visit all elements before you get back to the start.
Let tailX := root(X).next, and tailY := root(Y).next.
Set root(X).next := tailY and root(Y).next := tailX.
As you can see, starting from root(X) now takes you to the end of Y, through Y ...
Top 50 recent answers are included