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


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


3

Yup. A BDD is just an acyclic finite-state automaton (DFA) that accepts a language $L \subseteq \{0,1\}^n$. It represents the function $f(x)= 1$ if $x \in L$ or $f(x)=0$ if $x \notin L$. You can generalize this to allow an acyclic finite-state automaton over a language over a different alphabet, or indeed, a language $L \subseteq \Sigma_1 \times \cdots \...


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


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


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

Since you only measure distances from the centers of the squares, you can restate your problem as follows: Maintain a dynamic collection $X$ of $n$ points in Euclidean space so that you can quickly find the $k$ nearest neighbors in $X \setminus \{p\}$ of a query point $p \in X$. Using the data structure described here you can maintain such a collection in $...


1

Let's show that $\{a^n b^n : n \geq 0\}$ is not regular using Myhill's criterion (there are infinitely many equivalence classes): The pumping lemma shows that $\{a^n b^n : n \geq 0\}$ is not regular. According to Myhill's criterion, if a language is not regular then it has infinitely many equivalence classes. Therefore the language has infinitely many ...


1

Let $n$ denote the number of items in the set, and $f(i)$ denote the $i$th value. Use format-preserving encryption to construct a random permutation $\sigma:\{1,\dots,n\} \to \{1,\dots,n\}$. Define $g(i) = f(\sigma(i))$. Then $g$ is a representation of a randomly shuffled version of your set, and specific items can be accessed very efficiently. To ...


1

As discussed in the comments it turns out that, yes, I need to size my Cuckoo filter for the set of every existing name. That being said, it is not much of a problem in the end if I only send the buckets with fingerprints in it, which shouldn't be more than 600. In addition to that, my attempt at a self answer was very wrong. The probability that there is ...


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

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


1

This can be solved in $\mathcal{O}(n\log^2{}n)$ by using a 2D-range query data structure to optimize the Dynamic Programming solution which has been explained in the link given in the question: As in the link, for a box in the input with dimensions $(w_i, d_i, h_i)$, consider all rotations of the box, but maintain the property that the first dimension is ...


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


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