61–70 of 93 posts
HyperLogLog
Simplex. If you can transform your NP hard optimization problem into an LP, simplex can often work like magic.
That said, many combinatorial optimization problems that look quite similar to NP hard problems have very nice and efficient LP formulations, and for many NP hard problems, integer programming-based methods (which in the end mostly solve LP relaxations) are among the best algorithms. For example, planar TSP can be solved for tens or even hundreds of thousands of nodes using the LP relaxation, branch, and cut tool set.
Modern LP solvers don't just use the Simplex method though. I'm very partial to the Simplex method myself, but in practice, Interior Point Methods are often used.
Given the head of a linked list, how do you determine if it loops? eg, an l-shaped list is easy to determine - you simply process each element in the list until you find one without a subsequent element. But what if it's a 9-shaped linked list? You'll never run out of elements, so the best you could seem to do would be to store a reference to each element and check against all references to see if you've found a dupl…
I like my solution better: The list node contains a pointer and some data, most likely another pointer, or a primitive type, or a struct of primitive types. Which means, that on all modern systems, a list node is aligned to at least 16 bits, much more likely 32 bits. That means that the pointer to the node always has the last bit set to zero. So: bool containsCycle(node_t *root) { node_t *p = root; bool ret = false;…
So I beg to differ, it's not really "better" by any metric.
The Fastest and Shortest Algorithm for All Well-Defined Problems: https://arxiv.org/abs/cs/0206022 Abstract: An algorithm M is described that solves any well-defined problem p as quickly as the fastest algorithm computing a solution to p, save for a factor of 5 and low-order additive terms. M optimally distributes resources between the execution of provably correct p-solving programs and an enumeration of all proofs,…
I vote twice for this one!
I have never seen anything more elegant than Disjoint Set Datastructure https://en.wikipedia.org/wiki/Disjoint-set_data_structure
Also best (only?) practical use of the (inverse) Ackermann function!
Earlier quoted context omitted.
I like my solution better: The list node contains a pointer and some data, most likely another pointer, or a primitive type, or a struct of primitive types. Which means, that on all modern systems, a list node is aligned to at least 16 bits, much more likely 32 bits. That means that the pointer to the node always has the last bit set to zero. So: bool containsCycle(node_t *root) { node_t *p = root; bool ret = false;…
Hacky, trashes CPU cache, the code itself is on a sloppy side and, most importantly, it lacks the elegance of the original solution. So I beg to differ, it's not really "better" by any metric.
Tortoise and hare can only detect that a cycle exists. This hack will tell you exactly which node the cycle starts on. That means that if you want to e.g. repair a list, you can just cut that last link and set it to either null or root. Granted, this wasn't the original problem.
1. Lempel-Ziv compression algorithms (both LZ77 and LZ78). They are practical, even if one code their basic versions will get good compression ratio. Moreover, they opened the whole big chapter of data compression (LZW, LZSS and more). 2. The algorithm behind rsync. Nice one. 3. Jarvis algorithm for finding convex hull. 4. Speaking of data structures I like xor-linked list, it's neat. [1] https://en.wikipedia.org/wik…
Do you mean the rolling checksum part?
1. Lempel-Ziv compression algorithms (both LZ77 and LZ78). They are practical, even if one code their basic versions will get good compression ratio. Moreover, they opened the whole big chapter of data compression (LZW, LZSS and more). 2. The algorithm behind rsync. Nice one. 3. Jarvis algorithm for finding convex hull. 4. Speaking of data structures I like xor-linked list, it's neat. [1] https://en.wikipedia.org/wik…
> 2. The algorithm behind rsync. Do you mean the rolling checksum part?