Graph is a concept used to describe relationships between things where vertices (or nodes) represent things and edges represent relationships. Graph is made up of two finite sets (vertices and edges) and denoted by G = (V, E). Nodes usually are denoted by non-negative integers (for example, graph with 3 nodes with have nodes denoted…

# Year: 2010

## Joining Microsoft

Find a job you like and you add five days to every week. – H. Jackson Brown, Jr. I decided to join Microsoft in attempt to make my week longer. Lot’s of things to learn and challenging problems to solve. But this is where interesting topics come from. I will continue chasing state of the…

## Parallel merge sort

Divide and conquer algorithm solves the problem by: dividing problem into two or more smaller independent sub-problems of the same type of problem solving each sub-problem recursively and combining their results. Sub-problem independency makes divide and conquer algorithms natural for dynamic task parallelism. Quicksort is a good example (actually you can find its parallel version…

## 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)…

## External merge sort

If data to be sorted doesn’t fit into main memory external sorting is applicable. External merge sort can be separated into two phases: Create initial runs (run is a sequence of records that are in correct relative order or in other words sorted chunk of original file). Merge created runs into single sorted file. To…

## Minimum window that contains all characters

Like most of life’s problems, this one can be solved with bending – Bender B.Rodrigues Let’s bend another problem. Given set of characters P and string T find minimum window in T that contains all characters in P. Applicable solution is restricted to O(length(T)) time complexity. For example, given a string T “of characters and…

## Print numbers by spiral

Recently I came across simple yet interesting coding problem. So here is the deal. You are given positive integer N. Print first N ^ 2 positive integers in matrix form in a such a way that within matrix numbers form spiral starting from its center and goring clockwise. For example, for N = 5 matrix…

## 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,…