441–450 of 507 posts
Earlier quoted context omitted.
and it's also a broken version.
How so? Are you talking about (high + low)/2? Whether that is correct depends on the language. With 64 bit arithmetic it's correct in practice, and with arbitrary size arithmetic it's correct in practice and in theory. It only really causes problems if you're using 32 bit arithmetic on a 64 bit machine.
Or, look up the right answer.
Constructive Solid Geometry using BSP trees. There is a javascript implementation [0] which is where I saw it the first time, it is about 500 lines of fully commented code. The algorithm is so simple, I absolutely love it. Basically, when performing a union on two meshes, we determine the 3d BSP trees from both meshes, then simply clip each mesh using the other's tree. The output is the union of the two leftover mesh…
Constructive Solid Geometry using BSP trees. There is a javascript implementation [0] which is where I saw it the first time, it is about 500 lines of fully commented code. The algorithm is so simple, I absolutely love it. Basically, when performing a union on two meshes, we determine the 3d BSP trees from both meshes, then simply clip each mesh using the other's tree. The output is the union of the two leftover mesh…
Nice! I studied the library by porting it to TypeScript. https://github.com/birkir/csg.js/blob/patch-1/csg.ts
I've ported this algorithm to Python, but mine is nowhere as succinct as yours (or the original). For my needs, I require the meshes to remain watertight (if the inputs are watertight), and this specific implementation doesn't preserve it. But I still love the algorithm due to its conceptual simplicity.
Earlier quoted context omitted.
How so? Are you talking about (high + low)/2? Whether that is correct depends on the language. With 64 bit arithmetic it's correct in practice, and with arbitrary size arithmetic it's correct in practice and in theory. It only really causes problems if you're using 32 bit arithmetic on a 64 bit machine.
Just keep telling yourself that. Or, look up the right answer.
My favorite is the FLAC algorithm. It's fairly simple to explain - take a signal input, pattern match a generative signal that closely matches the original or part of it, and the output is a combination of that generative code and the difference between it and it and the input. Second favorite is the LISP REPL. Specifically the Eval function, thanks to this classic video of Sussman https://www.youtube.com/watch?v=0m6…
Extremely simple one, but my favorite is an algorithm for determining if two words are anagrams of each other: The Fundamental Theorem of Arithmetic states: "every integer greater than 1 either is a prime number itself or can be represented as the product of prime numbers and that, moreover, this representation is unique, up to (except for) the order of the factors."[1] So to determine that two words are anagrams of…
Nice in theory, but in practice you wouldn't implement it like that, especially if the words can be longer than your machine integer allows. Sorting and comparing is more elegant than invoking a BigNum library, imho (and has smaller footprint). This shows that theoretical elegance != implementation elegance.
I've had really good results asking this. I find it's a great question, because it allows the candidate to show off their knowledge, and use some knowledge that they likely prepared for ahead of time. I also like it because sometimes I get to learn something really interesting from the candidate.
It's also an easy way to filter people when they can't name even one algorithm, or their favorite is "that sorting algorithm"
In other words: these are polynomials with n variables. every variable is either zero or one. addition is modulo 2. Each variable corresponds to a single bit in a binary number. Can we construct a polynomial that produces any given length 2^n sequence?
One way this is done by induction on the number of variables. I find this proof to be extremely compelling. I derived it myself one time and it has stuck with me.
The faster way to do this is through a Walsh transform. This proof converts the problem to a matrix equation by simply manipulating a sum. The Walsh matrix itself is an interesting fractal because it's a Hadamard matrix.
These two simple proofs give different perspectives
Earlier quoted context omitted.
Just keep telling yourself that. Or, look up the right answer.
Perhaps instead of being mean, you could be helpful and post a link to said answer.
Earlier quoted context omitted.
I was curious how soon overflowing a native integer would come up. The "worst case" would be all "z"s (which map to 103), so how many characters does floor(log_103(2^n-1)) get you? int32 zzzz (4 characters) uint32 zzzz (4 characters) int64 zzzzzzzzz (9 characters) uint64 zzzzzzzzz (9 characters) But that's the worst case, not many real words have several "z"s in them. How often are real words affected? I did some exp…
Hmm, nice result. That makes me want to map letters onto primes in order of frequency. So "e" is 2, "t" is 3, etc., see: http://pi.math.cornell.edu/~mec/2003-2004/cryptography/subs/...
Better complexity-wise as well, both in terms of speed and storage: O(n) and O(1), respectively. [1]
The proposed algorithm uses O(n) storage (to store the immense product), and given that integer multiplication complexity is somewhere between O(n) and O(n^2), we end up[2] with at least O(n^2) runtime complexity!
[1] ...assuming the input data is less than 15 million terabytes in size; O(n log n), O(log n) respectively for arbitrary length input. Storing the number of input bytes takes O(log n) space, and integer increment can take O(size).
[2]https://en.wikipedia.org/wiki/Computational_complexity_of_ma...