## 64/32-bit division on a processor with 32/16-bit division

See “Hacker’s Delight”, multiword division (pages 140-145). The basic concept (going back to Knuth) is to think of your problem in base-65536 terms. Then you have a 4 digit by 2 digit division problem, with 2/1 digit division as a primitive. The C code is here: https://github.com/hcs0/Hackers-Delight/blob/master/divmnu.c.txt

## Postfix notation to expression tree

Create a stack containing nodes that could be part of a tree Push operands on a stack (A, 2, B, etc. are operands) as leaf-nodes, not bound to any tree in any direction For operators, pop the necessary operands off the stack, create a node with the operator at the top, and the operands hanging … Read more

## Best algorithm for matching colours.

Convert all of the colors to the CIE Lab color space and compute the distance in that space deltaE = sqrt(deltaL^2 + deltaA^2 + deltaB^2) Colors with the lowest deltaE are the most perceptually similar to each other.

## Distance from a point to a polygon

Your best bet is to iterate over all the lines and find the minimum distance from a point to a line segment. To find the distance from a point to a line segment, you first find the distance from a point to a line by picking arbitrary points P1 and P2 on the line (it … Read more

## Appointment scheduling algorithm (N people with N free-busy slots, constraint-satisfaction)

As you pointed out, the problem is equivalent to the problem of finding a maximum matching in a bipartite graph (one set of vertices is the set of people and the other on the set of slots, there is an edge between a person and a slot if the person is available for this slot). … Read more

## Why is Insertion sort better than Quick sort for small list of elements?

Big-O Notation describes the limiting behavior when n is large, also known as asymptotic behavior. This is an approximation. (See http://en.wikipedia.org/wiki/Big_O_notation) Insertion sort is faster for small n because Quick Sort has extra overhead from the recursive function calls. Insertion sort is also more stable than Quick sort and requires less memory. This question describes … Read more

## How to apply binary search O(log n) on a sorted linked list?

It is certainly not possible with a plain singly-linked list. Sketch proof: to examine the last node of a singly-linked list, we must perform n-1 operations of following a “next” pointer [proof by induction on the fact that there is only one reference to the k+1th node, and it is in the kth node, and … Read more

## What is the most efficient way to encode an arbitrary GUID into readable ASCII (33-127)?

This is an old question, but I had to solve it in order for a system I was working on to be backward compatible. The exact requirement was for a client-generated identifier that would be written to the database and stored in a 20-character unique column. It never got shown to the user and was … Read more

## Tetris Piece Rotation Algorithm

When I was trying to figure out how rotations would work for my tetris game, this was the first question that I found on stack overflow. Even though this question is old, I think my input will help others trying to figure this out algorithmically. First, I disagree that hard coding each piece and rotation … Read more

## What is the difference between Linear search and Binary search?

A linear search looks down a list, one item at a time, without jumping. In complexity terms this is an O(n) search – the time taken to search the list gets bigger at the same rate as the list does. A binary search is when you start with the middle of a sorted list, and … Read more