## Iterating over a Binary Tree with O(1) Auxiliary Space

Geez, I’ll have to actually type it up from Knuth. This solution is by Joseph M. Morris [Inf. Proc. Letters 9 (1979), 197-200]. As far as I can tell, it runs in O(NlogN) time. static void VisitInO1Memory (Node root, Action<Node> preorderVisitor) { Node parent = root ; Node right = null ; Node curr ; while (parent != null) { curr … Read more

## Algorithm to find the most common substrings in a string

This is as task similar to Nussinov algorithm and actually even simpler as we do not allow any gaps, insertions or mismatches in the alignment. For the string A having the length N, define a F[-1 .. N, -1 .. N] table and fill in using the following rules: for i = 0 to N … Read more

## What types of numbers are representable in binary floating-point?

The rule can be summed up as this: A number can be represented exactly in binary if the prime factorization of the denominator contains only 2. (i.e. the denominator is a power-of-two) So 1/(32 + 16) is not representable in binary because it has a factor of 3 in the denominator. But 1/32 + 1/16 … Read more

## Grammatical inference of regular expressions for given finite list of representative strings?

Yes, it turns out this does exist; what is required is what is known academically as a DFA Learning algorithm, examples of which include: Angluin’s L* L* (adding counter-examples to columns) Kearns / Vazirani Rivest / Schapire NL* Regular positive negative inference (RPNI) DeLeTe2 Biermann & Feldman’s algorithm Biermann & Feldman’s algorithm (using SAT-solving) Source … Read more

## Fluent Interfaces – Method Chaining

The core idea behind building a fluent interface is one of readability – someone reading the code should be able to understand what is being achieved without having to dig into the implementation to clarify details. In modern OO languages such as C#, VB.NET and Java, method chaining is one way that this is achieved, … Read more

## Are exceptions really for exceptional errors? [closed]

This sounds over-simplistic, but I think it makes sense to simply use exceptions where they are appropriate. In languages like Java and Python, exceptions are very common, especially in certain situations. Exceptions are appropriate for the type of error you want to bubble up through a code path and force the developer to explicitly catch. … Read more

## What is a stack overflow?

From Wikipedia: In software, a stack overflow occurs when too much memory is used on the call stack. In many programming languages, the call stack contains a limited amount of memory, usually determined at the start of the program. The stack is a data structure that keeps record of the point the subroutines of a … Read more

## Is Sleep() evil?

I actually believe the assertion you linked is correct. The problem is sleep is being used (as you noted) as an inefficient substitute for notification mechanisms. Sleep is always inferior to a properly implemented notification mechanism, If you are waiting for an event. If you actually need to wait a specific amount of time for … Read more

## What is an ideal variable naming convention for loop variables? [closed]

I always use a meaningful name unless it’s a single-level loop and the variable has no meaning other than “the number of times I’ve been through this loop”, in which case I use i. When using meaningful names: the code is more understandable to colleagues reading your code, it’s easier to find bugs in the … Read more

## What’s the term for the part of the URL after the question mark?

It’s the query, or sometimes the query string. To pinch a useful diagram from the URI RFC: foo://example.com:8042/over/there?name=ferret#nose \_/ \______________/\_________/ \_________/ \__/ | | | | | scheme authority path query fragment