Infernal dinner synchronization problem

Imagine group of hungry people with spoons sitting around pot of stew. Spoon’s handle long enough to reach the pot but it is longer than the arm and no one can feed himself. People are desperate. This is a picture described in recently found piece of lost chapter of Dante’s Inferno. In order to help…

1

Merge binary search trees in place

Binary search tree is a fundamental data structure that is used for searching and sorting. It also common problem to merge two binary search trees into one. The simplest solution to do this is to take every element of one tree and insert it into the other tree. This may be really inefficient as it…


Traverse binary tree in level order by spiral

Another puzzle is at stake, folks. This time it is binary tree related (not necessarily binary search tree as we are not interested in data relations but rather in binary tree structure). We need to traverse binary tree level by level (level is defined as set of all nodes at the same distance from root)…


Suffix array

Find all occurrences of a pattern (of length m) in a text (of length n) is quite commonly encountered string matching problem. For example, you hit Ctrl-F in your browser and type string you want to find while browser highlights every occurrence of a typed string on a page. The naive solution is to at…


Selecting k smallest or largest elements

There are cases when you need to select a number of best (according to some definition) elements out of finite sequence (list). For example, select 10 most popular baby names in a particular year or select 10 biggest files on your hard drive.   While selecting single minimum or maximum element can easily be done iteratively…


K-way merge

The classic merge (the one used in Merge Sort) takes as input some sorted lists and at each step outputs element with next smallest key thus producing sorted list that contains all the elements of the input lists. An instance of a list is a computer representation of the mathematical concept of a finite sequence,…


Binary heap based priority queue

Design of container that supports items ordering raises lots of interesting design questions to consider. To be more concrete we will design simple priority queue based on binary min heap that supports the following operations: Enqueue – add an item to the queue with an associated priority. Dequeue – remove the element from the queue…


Queue based on a single stack

Looking at things from different perspectives allows to understand them better. On the other hand mind bending practice improves your ability to find solutions. Previously we were Disposing sequence of resources with Reactive Extensions. This time we will build FIFO (first in, first out) collection based on single LIFO (last in, first out) collection with…


Disposing sequence of resources

C# “using” statement has several advantages over its expanded equivalent: Shortcut is more readable If local variable form for resource acquisition is used it is read-only inside using statement and thus prevents you from spoiling resource disposal Whenever you need to obtain several resources (number is known at compile time), use and then dispose them…