Chasing state of the art

Exploring best practices in problem solving

Parallel partition phase for quick sort

A while ago I was wrapping my head around parallel merge sort. Since it requires additional O(n)...

Author: Dzmitry Huba Date: 03/04/2012

Load-balancing partitioner with work stealing, part two

In part one work stealing range was introduced that allows stealing of work items in contiguous...

Author: Dzmitry Huba Date: 08/10/2011

Load-balancing partitioner with work stealing, part one

Data parallelism is a computing parallelization technique where data can be separated into...

Author: Dzmitry Huba Date: 08/08/2011

Infernal dinner synchronization problem

Imagine group of hungry people with spoons sitting around pot of stew. Spoon’s handle long...

Author: Dzmitry Huba Date: 07/19/2011

Shared rooms synchronization problem

Recently I came across another interesting synchronization problem. Assume there are n rooms....

Author: Dzmitry Huba Date: 06/29/2011

Single Responsibility Principle – discovering violations

Single Responsibility Principle states: A class should have only one reason to change....

Author: Dzmitry Huba Date: 06/15/2011

Inject or locate dependencies?

Inversion of Control pattern allows to decouple components (consumers) from their dependencies and...

Author: Dzmitry Huba Date: 06/13/2011

Sleeping barber synchronization problem

Sleeping barber problem is a classic synchronization problem proposed by Dijkstra that goes as...

Author: Dzmitry Huba Date: 06/12/2011

Concurrent Object Pool

Object pool is a set of initialized objects that are kept ready to use, rather than allocated and...

Author: Dzmitry Huba Date: 05/01/2011

Concurrent set based on sorted singly linked list

Set is an abstract data structure that can store certain values, without any particular order, and...

Author: Dzmitry Huba Date: 04/06/2011

Merge binary search trees in place

Binary search tree is a fundamental data structure that is used for searching and sorting. It also...

Author: Dzmitry Huba Date: 03/27/2011

Shared restroom synchronization problem

Assume you own a bar that have single restroom with n stalls. In order to avoid lawsuits you want to...

Author: Dzmitry Huba Date: 03/02/2011

Merge sequences in parallel

In practice you may find yourself in a situation when you have several sequences of data that you...

Author: Dzmitry Huba Date: 02/25/2011

Longest consecutive elements sequence

A tiny detail that can be uncovered by looking at a problem on a different angle usually is the key...

Author: Dzmitry Huba Date: 02/12/2011

Parallel string matching

String matching is about searching for occurrence (first or all occurrences – it makes...

Author: Dzmitry Huba Date: 01/05/2011

Graph is a concept used to describe relationships between things where vertices (or nodes) represent...

Author: Dzmitry Huba Date: 12/26/2010

Joining Microsoft

Find a job you like and you add five days to every week. - H. Jackson Brown, Jr. I decided to join...

Author: Dzmitry Huba Date: 11/11/2010

Parallel merge sort

Divide and conquer algorithm solves the problem by: dividing problem into two or more smaller...

Author: Dzmitry Huba Date: 10/17/2010

Traverse binary tree in level order by spiral

Another puzzle is at stake, folks. This time it is binary tree related (not necessarily binary...

Author: Dzmitry Huba Date: 09/19/2010

External merge sort

If data to be sorted doesn’t fit into main memory external sorting is applicable. External...

Author: Dzmitry Huba Date: 08/24/2010

Minimum window that contains all characters

Like most of life's problems, this one can be solved with bending - Bender B.Rodrigues Let’s...

Author: Dzmitry Huba Date: 08/21/2010

Recently I came across simple yet interesting coding problem. So here is the deal. You are given...

Author: Dzmitry Huba Date: 08/17/2010

Suffix array

Find all occurrences of a pattern (of length m) in a text (of length n) is quite commonly...

Author: Dzmitry Huba Date: 04/04/2010

Selecting k smallest or largest elements

There are cases when you need to select a number of best (according to some definition) elements out...

Author: Dzmitry Huba Date: 03/17/2010

K-way merge

The classic merge (the one used in Merge Sort) takes as input some sorted lists and at each step...

Author: Dzmitry Huba Date: 03/04/2010

Right-hand side Enumerable.Zip

With Reactive Extensions for .NET (Rx) and .NET Framework 4 a new LINQ operator was introduced...

Author: Dzmitry Huba Date: 02/22/2010

Binary heap based priority queue

Design of container that supports items ordering raises lots of interesting design questions to...

Author: Dzmitry Huba Date: 02/08/2010

Queue based on a single stack

Looking at things from different perspectives allows to understand them better. On the other hand...

Author: Dzmitry Huba Date: 01/17/2010

Disposing sequence of resources with Reactive Extensions

Recall my previous post on Disposing sequence of resources where we were solving imperatively the...

Author: Dzmitry Huba Date: 12/29/2009

Chaining responsibilities

The idea behind Chain of Responsibility pattern is quite simple and powerful: Avoid coupling the...

Author: Dzmitry Huba Date: 12/22/2009

Making callbacks more explicit

Recall my previous post Events and Callbacks vs. Explicit Calls that outlined pros and cons of both...

Author: Dzmitry Huba Date: 12/21/2009

Disposing sequence of resources

C# “using” statement has several advantages over its expanded equivalent: Shortcut is...

Author: Dzmitry Huba Date: 11/04/2009