28

You can achieve constant amortized time per operation by keeping a dynamically-sized array $A$ (using the doubling/halving technique). To insert an element append it at the end. To implement remove_random() generate a random index $k$ between $1$ and $n$, swap $A[k]$ with $A[n]$ and delete (and return) $A[n]$. If you want a non-amortized worst-case bound on ...


26

In many algorithms we don't need to check whether two vertices are adjacent, like in search algorithms, DFS, BFS, Dijkstra's, and many other algorithms. In the cases where we only need to enumerate the neighborhoods, a list/vector/array far outperforms typical set structures. Python's set uses a hashtable underneath, which is both much slower to iterate ...


15

Since you clearly don't care about the order of elements changing, I think the simplest approach is to use a resizable array (like C++'s std::vector or Java's java.util.ArrayList). When you remove an element, if it's not the last element, you just move the last element to take its place. That gives amortized-constant-time add and constant-time remove_random. ...


9

Another solution that provides amortized constant time operations is to use a dynamic array with insertion and removal at the end, just as in Steven's answer, but swap the last element with a random one after insert, instead of before removal as in Steven's method. That is, instead of doing what Steven suggests (in pseudocode): public method insert(element): ...


6

Based on standard usage of the terms, a heap is a specific data structure, with a specific representation in memory. A priority queue is an abstract data type: it identifies some operations that must be supported by the data structure, but does not itself describe any particular data structure. You can use a heap to implement the priority queue operations. ...


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 ...


5

I think it would work with a complete tree with elements stored in leaves, the whole thing being stored in an array (the same way as for heaps). You also need to store in each node the sum of the weights of all its children. To be able to modify weight, you would also need a corresponding array (or hashtable if ids are not consecutive integers), to know ...


4

Suppose that $f(n) = O(n^{\log_b a - \epsilon})$. According to the definition, there exist constants $N,C>0$ such that $f(n) \leq Cn^{\log_b a - \epsilon}$ for all $n \geq N$. Let $M$ be the maximum value of $f(n)/n^{\log_b a - \epsilon}$ over all positive integers $n < N$. The maximum exists since there are only finitely many such $n$. Then $f(n) \leq ...


4

Consider a data structure with operations $o_1,\ldots,o_k$. We say that these operations have amortized time $t_1,\ldots,t_k$ if any sequence of operations which contains $m_i$ operations of type $o_i$ runs in time at most $\sum_i m_i t_i$. This is essentially the same definition as yours, in a more general setting. We often allow $t_1,\ldots,t_m$ to depend ...


3

State machines and databases are quite different entities, and their usage (or functionality) is very different. In this answer, I'll just try to separate them with respect to the similarity you mention. This is by no means a comprehensive description of neither state machines nor databases. The states of a state machine can indeed be thought of as ...


3

Let $s_i$, $e_i$, $x_i$, be the shift start time, shift end time, and experience of the $i$-th worker. For each worker define the following two events: A shift-start event is a triple $(s_i, 0, i)$. A shift-end event is a triple $(e_i, 1, i)$. Collect all events in an array $E$ and sort it in increasing order (lexicographically). This requires $O(w \log w)$...


3

The first use of linked lists in their modern form seems to have been by Peter Luhn in 1953, when he implemented a chaining-based hash table on the IBM 701 machine. Linked lists are often misattributed as being due to Newell et al. during their development of the IPL language (an early version of lisp), but that wasn't until 1956. The IPL language did ...


3

Your random number generator might not be able to produce all numbers. Without looking at Math.Random, if it returned an integer then it would never match 0.123456. If it returned a double precision floating point number 0 <= rnd < 1, it might produce a 53 bit integer from 0 to 2^53-1, and multiply by 2^-53. In this case it is quite possible that 0....


3

You can use a disjoint sets data structure to quickly solve your problem (exercise). This can be further improved by exploiting the particular nature of your problem. We maintain a list of intervals $[a_1,b_1],[a_2,b_2],\ldots$ which succinctly represent the integers seen so far. In addition, we store $a_i,b_i$ in a hash table. Given a new integer $c$, we ...


3

For any pair of adjacent strings, you can find a constraint of the form $\sigma < \tau$ on the order of the symbols which is necessary in order for this pair of strings to be lexicographically ordered. This doesn't require any fancy data structure. Putting all of these constraints together in a directed graph, you can determine whether such an order ...


3

Let us prove by induction on depth that for every node $v$, there exist $a_v,b_v$ (possibly $\pm \infty$) such that the input $x$ reaches $v$ iff $a_v < x < b_v$. This is true for the root since we can take $a_r = -\infty$ and $b_r = +\infty$. Now suppose that it is true for some node $v$, and let $v_<,v_>$ be its two children. Suppose that node $...


3

The problem is equivalent to job scheduling problem on parallel machines. The problem is $\mathsf{NP}$-hard even when the arrival time for each job/person is $0$ and the number of machines (or meeting rooms) are $2$. The $\mathsf{NP}$-hardness proof simply follows from the partition problem. More precisely, your problem is equivalent to $P;m|rj|C_{max}$, i.e....


3

Note: In what follows, I'm going to use the term "B-tree" to refer to the general idea of B-trees regardless of the variant, and "B+-trees" to refer specifically to B+-trees. You've correctly identified a real-word complication of using B-trees to index strings: B-trees are page-structured files, but strings are of arbitrary length. This ...


3

The following would be natural choices for sorting complex numbers: Lexicographic ordering, real first: Sort $a + bi$ first by $a$, then by $b$. So $a + bi < c + di$ if $a < c$ OR if $a = c$ and $b < d$. Lexicographic ordering, complex first: $a + bi < c + di$ if $b < d$ OR if $b = d$ and $a < c$. By magnitude: $a + bi < c + di$ if $|...


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).


2

An O(n)-time algorithm for the problem has been published by Gabow et al. (1984) in the context of "Cartesian trees": https://dl.acm.org/doi/10.1145/800057.808675 As pointed out above by Raphael, there is a close relationship to treaps. You may also want to visit the corresponding Wikipedia entry: https://en.wikipedia.org/wiki/Cartesian_tree


2

The flaw in your approach is that you assume that the second level contains only $2$ and $3$. The following examples is min heap with $3$ not in the second level. 1 / \ 2 5 / \ / \ 3 4 6 7 The solution is available here. Solution: The root of the tree has to be the minimum element, therefore $1$ is at the root. Now we need to find ...


2

This is the special case of the multidimensional knapsack problem where each item (tray) has the same value (consider the set of trays you don't select). It presumably remains NP-hard, but can be solved by a number of methods. Probably the easiest to try first is to formulate this as an instance of integer linear programming and then apply an ILP solver to ...


2

A tree structure can be completely described by three functions: a function that given a node $x$ returns the number of children of that node, a function that given a node $x$ and index $i$ returns the $i$th child of that node, and a function that given a node $x$ returns an associated value $v$ stored at that node.


2

Expanding on Dmitry's comment, you can maintain a balanced tree with the left endpoints of the intervals as the keys, and at each node store a balanced tree with the right endpoints as keys, and at each node of each of those trees store a count of intervals. This requires $O(n\log n)$ space. Lookups are $O(\log^2 n)$. Insertions are tricky because when ...


2

Let's consider the case in which $H$ is a triangle; the general case is very similar. A triangle in a graph $G$ is a set $\{x,y,z\}$ of three vertices of $G$ such that $G$ contains the edges $\{x,y\},\{y,z\},\{z,x\}$. Two triangles $T_1,T_2$ are (vertext) disjoint if they do not share a vertex: $T_1 \cap T_2 = \varnothing$. A graph contains $k$ disjoint ...


2

Finding $k$ disjoint triangles in a graph means that you color $3k$ vertices with $k$ colors, $\chi_i, 1 \leq i \leq k$ such that for each color $\chi_i$, the graph $G[X_i] \simeq K_3$, where $X_i$ are the three vertices that received color $\chi_i$. It simply means that you cannot use the same vertex in two different triangles. This type of problem is often ...


2

Insert complexity in a binary search tree is not minimum $\Omega(\log n)$. For instance, if the element to be inserted is larger than the largest element of the tree, then you can make the whole tree the left child of a new root node containing the element to be inserted. In a balanced binary search tree, with only a pointer to the root and not any other ...


2

The assumptions $A[i] \in \mathbb N$ and $A[i] + A[j] \leq n$ together imply that $0 \leq A[i] \leq n$, and so $-n \leq A[i]-i \leq n$. This suggests maintaining an array $B[-n],\ldots,B[n]$, initialized with zeroes. We go over the elements of $A$ one by one. We put $B[A[i]-i] = i$, and then check whether $B[i-A[i]]$ is non-zero, say equal to $j$. If so, ...


2

You can do it in $O(n)$ time and $O(1)$ auxiliary space assuming a model where the integers are stored as $w$-bit integers where $w > 2$, and we can modify the input array (non-destructively). First, we're going to steal two bits of storage space per element from our array. In one linear scan find the index $l$ such that the most significant bit of $A[l-...


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