How do I check if a directed graph is acyclic?
I would try to sort the graph topologically, and if you can’t, then it has cycles.
theory
How are hash functions like MD5 unique?
You’re correct that it cannot guarantee uniqueness, however there are approximately 3.402823669209387e+38 different values in a 32 digit hex value (16^32). That means that, assuming the math behind the algorithm gives a good distribution, your odds are phenomenally small that there will be a duplicate. You do have to keep in mind that it IS … Read more
What is the relationship between event loop and Promise [duplicate]
Each event loop has a microtask queue and a macrotask queue. A microtask is a task that is originally to be queued on the microtask queue rather than a task queue. Refer to https://www.w3.org/TR/html51/webappapis.html#microtask-queue. There are two kinds of microtasks: solitary callback microtasks, such as Promiseļ¼ and compound microtasks, such as Object.observe, MutationObserver and process.nextTick … Read more
“const correctness” in C#
I’ve come across this issue a lot of times too and ended up using interfaces. I think it’s important to drop the idea that C# is any form, or even an evolution of C++. They’re two different languages that share almost the same syntax. I usually express ‘const correctness’ in C# by defining a read-only … Read more
Is finding the equivalence of two functions undecidable?
Given an arbitrary function, f, we define a function f’ which returns 1 on input n if f halts on input n. Now, for some number x we define a function g which, on input n, returns 1 if n = x, and otherwise calls f'(n). If functional equivalence were decidable, then deciding whether g … Read more
Is the C99 preprocessor Turing complete?
Well macros don’t directly expand recursively, but there are ways we can work around this. The easiest way of doing recursion in the preprocessor is to use a deferred expression. A deferred expression is an expression that requires more scans to fully expand: #define EMPTY() #define DEFER(id) id EMPTY() #define OBSTRUCT(…) __VA_ARGS__ DEFER(EMPTY)() #define EXPAND(…) … Read more
What is Turing Complete?
Here’s the briefest explanation: A Turing Complete system means a system in which a program can be written that will find an answer (although with no guarantees regarding runtime or memory). So, if somebody says “my new thing is Turing Complete” that means in principle (although often not in practice) it could be used to … Read more
Difference Between Cohesion and Coupling
Cohesion refers to what the class (or module) can do. Low cohesion would mean that the class does a great variety of actions – it is broad, unfocused on what it should do. High cohesion means that the class is focused on what it should be doing, i.e. only methods relating to the intention of … Read more
How to test randomness (case in point – Shuffling)
Statistics. The de facto standard for testing RNGs is the Diehard suite (originally available at http://stat.fsu.edu/pub/diehard). Alternatively, the Ent program provides tests that are simpler to interpret but less comprehensive. As for shuffling algorithms, use a well-known algorithm such as Fisher-Yates (a.k.a “Knuth Shuffle”). The shuffle will be uniformly random so long as the underlying … Read more
Is it possible for a computer to “learn” a regular expression by user-provided examples?
Yes, it is possible, we can generate regexes from examples (text -> desired extractions). This is a working online tool which does the job: http://regex.inginf.units.it/ Regex Generator++ online tool generates a regex from provided examples using a GP search algorithm. The GP algorithm is driven by a multiobjective fitness which leads to higher performance and … Read more