New answers tagged

2

Compressibility of a file depends on the nature of the file, and what methods are applied to it. It is common for some prepressing to improve the compression. For example, if a list of words is sorted, you will see that many words in a row with have the same prefix, and can be taken advantage to reduce the overall file size with some extra encoding. ...


0

When I tried to delete my answer a pop up window asked if I'm voting to delete the question. I'm not voting to delete a question addressed to the whole internet world, I'm just deleting my answer


2

In addition to what Jörg W Mittag said: The Unicode Consortium isn't in the business of defining file formats. I think the original standard didn't even define any encoding of Unicode as a sequence of bytes – that was an implementation detail. In a sane world, there wouldn't be any need for something like the BOM, because the format of the character data ...


2

There is no guarantee that a file has a Byte Order Marker. For example, JSON documents don't need one at all, no matter what the encoding is (as a little puzzle, figure out how you can determine which Unicode encoding a JSON document is using). Now if you KNOW there is a single byte BOM, that's easy. But what do you do if you don't know? If the first ...


6

The BOM started out as an encoding trick. It was not part of Unicode, it was something that people discovered and cleverly (ab)used. Basically, they found the U+FEFF Zero width non-breaking space character. Now, what does a space character that has a width of zero and does not induce a linebreak do at the very beginning of a document? Well, absolutely ...


1

In UTF-16, information is encoded in units of 2 bytes. Every symbol is encoded using either one unit or two units. BOM uses one unit.


0

Approximating a Hash function $h$ as a function that maps each word in $\{0,1\}^*$ to a word in $\{0,1\}^{256}$ chosen uniformly at random, you can find the probability that at least one of the events: $h(A)=h(B\{A\})$, $h(A)=h(H\{A\})$, $h(B\{A\})=h(H\{A\})$ is true by looking at the complementary probability. The probability that $h(A)$, $h(B\{A\})$, and ...


0

Asymptotically speaking, both tasks can be performed in time $O(n)$ (which is also a trivial lower bound) since there can be only finitely many distinct binary strings. I don't know which of the two approaches is faster since it depends on the specific implementation details of the data structures used so you might try both of them. In practice I would ...


3

In the paper https://arxiv.org/abs/1408.5963 Thue-Morse sequence was used to construct a distributed algorithm which is non-local but halts on every finite network (input).


0

For coding test like this one :D. Using breadth first search could solve this but it soon eats up memory as pos grows large. Binary search works but Thue-Morse has the best runtime. Consider a special family of Engineers and Doctors. This family has the following rules: Everybody has two children. The first child of an Engineer is an Engineer and the ...


Top 50 recent answers are included