Fun

Misc

Algorithms

Here are questions and short notes about some funny and useful algorithms I was asked on interview or which were used in real work.

A couple examples to get in 😉

Average

There is a set R of N different numbers. How to find an average (arithmetic mean) of all numbers in this set?
How many steps does it take?

Solution:

assign value A = 0
one by one add to A all numbers Ri from the set R : A = A + Ri, (0<i<N)
A/N is the average (of numbers from the set R)

Number of required actions is ~N

Minimum

There is a set R of N different numbers.
How do I find the minimum number in a set?
How many steps does it take?

Solution:

assign value A = R1
for all other numbers from the set R do the following: if (Ri <A)? then A = Ri, (1<i<N)
A is the minimum number from the set R

Number of required actions is ~N

Now let's start

How to determine (quickly) if a given number is an integer power of two?

HINT:

A set of randomly distributed integers from 1 to 100 contains 101 elements: one number appears twice. How do you find this - duplicated - number? How many steps does it take?

HINT:

The sum of the first 100 numbers from 1 to 100 is 5050. Thus, adding 101 numbers from the set, it is easy to find the duplicated one

There is a set R of N different numbers.
How do I find the median number of this set?

How many steps does it take?

Note:
The median (do not mix with average) is such a number that half of the elements in the set are larger than it and the other half are smaller. For example, for a set of numbers 1, 3, 2, 59, 68, the median will be 3, because of two numbers from the set (1 and 2) are less than 3, and two numbers from the set (59 and 68) are greater than 3.

Tower of Hanoi
Kids toy: rod and a number of disks of different sizes, which can slide onto the rod.

There are three rods. The disks in a stack in ascending order of size on one rod, the smallest at the top.
Develop algorithm solving the following task:
How to move all disks onto another rod, following the rules:

one disk can be moved (to another rod) at a time
disk can be placed only on top of larger one (or on empty rod)

Rectangles of different lengths and heights are placed on the horizontal line (X-axis). The bottom base of the rectangles lies on a straight line. Rectangles can intersect (overlap) each other. Compose an algorithm to get a skyline - a silhouette of set of rectangles - as a set of vertices (X, Y) / segments of a polyline

City Silhouette / Skyline

All pictures - on screen!

A set of different rectangles (oriented along the 0X, 0Y axes ) must be placed on the plane so that

rectangles did not overlap / did not intersect each other
the ratio of the length to the width of the common area covered by rectangles should be within the given limits ( Rmin < L/W < Rmax )
the part of the common area not covered by rectangles should be minimal.

Trees

Here tree means a (hierarchical) structure in which each node (parent) can have several "sub-" nodes (children).

We should also mention the structure of a binary tree where each node has at most two "sub" nodes.

Common ancestor

Suppose we have two nodes of the same tree.
Find their closest common ancestor. Estimate the difficulty (how many steps will it take?)

Example. For two blue nodes, the closest common ancestor will be the red node. For two green nodes, the orange node will be the closest common ancestor.

Genghis Khan's heirs

Print out information about all nodes of the tree, observing the hierarchy.
Example: suppose we have the genealogical tree of the heirs of Genghis Khan. It is required to print the names and order / level of the heirs.

Solution 1 (recursion):

1. prepare "helper" function
print_children (parent , level)
{
for each child of a given parent {
print: child-name , level
call print_children(child, level + 1)
}
}

2. to print full tree of Genghis Khan's heirs just do:

print: Genghis Khan, 0
call the function print_children ( Genghis Khan , 1)

Solution 1 is fine, but not always acceptable: for very "deep" trees, recursion can be "overflowed" (computer specific). Therefore, it would be good to go without recursion and find solution with a loop.

Try to find solution 2 ... 😉

again about Genghis Khan
Now the question is about structure.
Is it possible (how?) to represent the hierarchy of the heirs of Genghis Khan (an arbitrary tree) in the form of a binary tree?

Recall that in a binary tree, each node has at most two "sub" nodes.

Not just a heap

The efficiency of an algorithm / solution often is determined by suitable data structure.
A few interesting examples are usage of MinHeap / MaxHeap structures.

MinHeap / MaxHeap is a binary tree data structure where each node has a lower (or higher) priority ("weight") than its (two) sub-nodes. At the same time, ratio of priorities/weights of nodes at the same level undefined.

In some tasks, these structures are much more efficient than sorted data. Heap structures are most efficient in tasks with dynamically changing data sets, where the element with the lowest (or highest) priority is periodically deleted. In such tasks, Heap does only what is necessary (eliminating unnecessary full sorting ).

An important property of the Heap: it can be stored as an array (vector). For each node of the Heap, its ID in the array and the IDs of "children" (sub-nodes) are simply linked:
if node number (id) in the array is: n,
then sub-node numbers are:
i1=2n + 1 and i2=2n + 2

MinHeap as an array.
The node ID in the array are written in blue .

Restoring the MinHeap / MaxHeap structure after adding a new element and / or after removing the root element requires no more than log (N) operations. Here N is the number of elements in the heap.

The heap implementation and all the details are covered in many articles. (see Wikipedia, search Google)

Use cases

1. "Respect for elders" (contrived situation)
People come to a certain organization (shop, clinic, municipality), where they are served not according to the order of arrival, but according to age. How to organize the reception of visitors? - MaxHeap !

2. Dynamic median
The set of numbers is filled with new data. It is required to track the median value "on the fly".

Pair MinHeap (for numbers greater than the median) and MaxHeap (for numbers lower than the median) will help. Make sure that the number of elements in the heaps does not differ by more than 1. The median will always be either the top of one of the heaps (larger in size), or the average of both tops (if sizes of heaps are same).

3. Dissolution of the polymer
Lets consider a polymer film where macromolecules of different sizes (solubility) are unevenly distributed throughout the volume. Somewhere the solubility is high, somewhere it is low. A solvent was poured onto the polymer surface ... It is required to determine the propagation of the solvent front in the polymer (surface development).

Lets divide the volume of the polymer into small cells so that the dissolution rate is constant within each cell. We will collect / store cells at the solvent front in MinHeap. The "priority" will be the dissolution time of the cell. The cell at the top of MinHeap is considered dissolved. After that, its undissolved "neighbors" (cells) are added to MinHeap. Dissolution time is updated for every "neighbor" (of course, the time is increasing). And the new cell at the top becomes dissolved ... etc

Page updated

Google Sites

Report abuse