Hot answers tagged

6

Knuth gives a good overview on the history of lists and linked data structures. From The Art of Computer Programming, Volume I, Section 2.6: Linked memory techniques were really born when A. Newell, J. C. Shaw, and H. A. Simon began their investigations of heuristic problem-solving by machine.


4

A balanced binary search tree can support access to arbitrary elements in $O(\log N)$ time per access. Augment the data structure to store, in each node, the number of values stored in the subtree under that node. Then you can find the $i$th largest value in the list in $O(\log N)$ time as well; thus, all basic operations can be done in $O(\log N)$ time.


2

The answer is circular buffer. Such structure could be implemented using array or linked list, but you cannot call explicit array-based circular buffer as linked-list. FSA cannot be "executed" infinitely (type 3 machine only uses fixed input and reads it ones), unless your FSA definition covers Turing Machines.


2

List processing is simultaneously three things in the development of computer science. (1) It is the creation of a genuine dynamic memory structure in a machine that had heretofore been perceived as having fixed structure. It added to our ensemble of operations those that built and modified structure in addition to those that replaced and changed content. (2)...


2

I will assume that initially $y=0$, as this makes no difference in your problem. Look at the very last two elements $a,b$ that you will apply your operation on: The tuple is $([a,b], y$) and, at the next iteration, it will necessarily be $([a+b], $y+a+b$)$, since $a+b = \sum_{i=1}^n x_i$ is a constant, you only want to minimize $y$. Notice that $a$ (resp. ...


1

No, that's not what the author means. The author means the specific sequence of characters the user will actually type. If the user is about to write a letter to Al that might be: 'D'::'e'::'a'::'r'::' '::'A'::'l'::rest The point is that you conceptually have "all" of the characters, and you can (with a bit of care) process this list like any other list.


1

You might not be able to generate lexicographic permutations for any sequence of arbitrary objects. In order to do so, you will need some way of comparing two objects and determining which one is smaller. Assuming you have this, you could use the following algorithm to generate all permutations of a sequence of $n$ objects in lexicographic order. Start by ...


1

You need an interval tree, which queries in O (logn + m) time, where $m$ is the number of intervals the point hits (as opposed to O (n) for n intervals in the data structure). This should produce enough savings that you'll hardly notice the cost of $m$. This output sensitive algorithm is likely the best you can do. The other answer suggests this ...


1

Here's my thought process on this problem: If you only care about "in or out", you can reduce the list of intervals so that no intervals overlap, and the intervals are in sorted order. Sorting by leftmost point takes $O(n \log n)$, then replacing any overlapping pairs with their union takes $O(n)$. But you've said you don't care how long this part takes. ...


1

The role of three values $V_1, V_2$ and $V_3$ isn't clear for me, but anyway: Step 1. Sort the original list in parallel by key $K$ - you'll get a list of records $(K, V_1, V_2, V_2)$, where all the records with the same key are stored together in "buckets". Step 2. Process each bucket concurrently, calculating all the averages. There are many parallel ...


1

Yes, you can have both as fast as possible random access and faster-than-full-rebuild insertion time. I assume you know how dynamically growing arrays work. Also, I assume you know how to make them work in $O(1)$ worst-case. These techniques allow us to focus on the problem for lists of limited size only. Let $n$ be the maximal size (capacity) of the list. ...


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