New answers tagged data-structures
0
The intuition is following: the "bad" case when you have to do expensive operation is when one of the stacks is empty, and the other one is big. You need to compensate its real cost with a potential decrease. Thus, you can define potential function as $2 \lvert \operatorname{size}(head) - \operatorname{size}(tail) \rvert$.
(For simplicity I represent hard ...
1
If it is for some reason important to use hashing, there is a concept called locality sensitive hashing, however it is somewhat complicated. Typically, nearest neighbor search is done with tree indexes, such as quadtrees, R-Trees or kd-trees.
1
https://www.bigocheatsheet.com considering finding (Access) the position of the element before insert as separate operation.
Array:
Access - O(1) // we can get the element by index directly
Insertion - O(n) // in the worst case we need to resize the array to have a space for the new element
Linked list:
Access - O(n) // we need to reach the element
...
0
The function is called 3 times.
F(3)
F(2)
F(1)
0
You probably can't. The principled solution is to use a data structure that supports nearest neighbor search.
0
Space-efficient data structure for analytical querying of multiple branching evolutions of a dataset
I recommend you use a persistent map data structure. A reasonable choice would be a persistent binary balanced tree or a persistent hash array mapped trie; with these choices, every operation can be done in $O(\log n)$ time or $O(1)$ time. You can store these data structures on disk and the disk overhead should be not too large: $O(n+\log m)$ or $O(n+m)$, ...
3
The question of how foreign languages justifies expanding the encoding in actual usage is well explained by earlier answers. The question of why foreign languages would affect the American Standard Code for Information Interchange is subtly different.
As you all know the ASCII chart needed to be extended from 127 encoding to 256
No. The original American ...
5
There are a few other good reasons to expand from 7-bit ASCII, but since you ask specifically about foreign languages, I want to tell you about that angle.
English has words with diacritical marks, usually loan words like naïve or café. They are rare, and usually you'll get into no trouble for omitting the diacritics. Occasionally one might stumble into a ...
2
Delete-max is $O(\log n)$, so you have $O(n) + k O(\log n)$ which is $O(n)$ for fixed $k$. But if $k$ is not fixed, it can be up to $\frac{n}{2}$ (if it's greater, just use a min-heap instead of a max-heap), and $O(n) + \frac{n}{2} O(\log n) = O(n \log n)$.
In fact, if there was some tricky way to do what you want, you would solve sorting in $O(n)$, not ...
1
Building a heap is O(n).
Taking the first item from a heap and then re-arranging things so it is a heap again is O (log n), and since you need to do this n time is O (n log n).
Of course you can just take one element of the heap after the other in O(n), but they won't be in sorted order. And building a heap can be done in O(n) because you add n/2 items to ...
10
ASCII has 128 characters. Many countries had similar encodings for 128 characters. That is all history. Nobody uses ASCII anymore. There was a phase with lots of different encodings for more than 128 characters, some with 256 (Mac Roman and Windows 1152 were quite popular) and some like the Chinese GB with thousands of characters.
Nowadays people mostly ...
0
Yeah, me i say, with DIRECT access, only addresses are known and kept, so as you try to read or write, the data contained in those memory addresses the computer is iterating through is never looked at/opened but only the data kept in the address you are trying to read or write to is the one opened.
This differs from RANDOM, as random has a mechanism of ...
2
The best you can do is keep track of all currently known equivalences using a Union-Find data structure. Initially, each element is in own group. Whenever you find that two elements are equivalent, you merge their groups (via a Union operation).
Then, the best you can do to answer the query you list is to enumerate over all the groups (other than the one ...
1
But what are contexts in which jump search actually makes sense as the most efficient method of searching data that was not specifically constructed to be ideal for jump searching?
Any context in which data is stored on a physical medium that allows forward jumping quicker than backwards jumping is a candidate. Just think of an ordinary hard drive. Its disk ...
0
Let me try to explain this with an example. Let us say if m=10 and n=1000.
If I have m number of insertions in a table with m slots, it is going to be O(m). Right?
But if we have 1000 insertions in a table containing 10 slots, it is not the same math anymore. Since you will have to deal with collisions at a greater frequency. It no more remains linear math. ...
1
Think about it. You can sort an array by adding all the items to a priority queue, then removing the items in sorted order.
If you could run a priority queue in constant time, you could sort in linear time. But you can't.
1
The skip list is not a balanced tree "under the hood", but is almost (probabilistically) tree-like.
It satisfies your "functional requirements" in that it has $O(\log n)$ insertion, and I believe* that you can make it so that it can give you the $k$th element in $O(\log n)$ time.
If you keep the list ordered, you can do queries in $O(\log n)$ time.
3
In "Optimal Algorithms for List Indexing and Subset Rank" by Paul F. Dietz this data structure is called an "indexed list" and an algorithm is given that has complexity $O(\log n / \log\log n)$ for all operations. Unfortunately this term has little value as a search term.
While that is complex data structure note that you can transform any self-balanced ...
4
It is a bit confusing. Suppose the alphabet has size $\Sigma$.
Basically the idea is that instead of allocating each state an entire block of $\Sigma$ elements in next[] to hold the target states for each possible input character, most of which would just hold a special "this transition is invalid" sentinel value since there are typically only a few valid ...
Top 50 recent answers are included
