Showing posts with label algorithm. Show all posts
Showing posts with label algorithm. Show all posts

Union Find

I have a (possibly huge) bunch of edges describing a forest of graphs, and I'd like to know how many components it actually has. This problem has a simple solution if we shovel the edges in a union-find data structure, and then just ask it for that piece of information.

Besides the number of components, our structure keeps track of the id associated to each node, and the size of each component. Here is how the constructor for my python implementation looks:
class UnionFind:
    def __init__(self, n):  # 1
        self.count = n
        self.id = [i for i in range(n)]  # 2
        self.sz = [1 for i in range(n)]  # 3
1. If the union-find is created for n nodes, initially the number of components, named count, is n itself.
2. All the nodes in a component have the same id, initially the id is simply the index of each node.
3. In the beginning, each node is a component on its own, so the size is initialized to one for each of them.

This simple ADT has two operations, union and find, hence its name. The first gets in input an edge and, if the two nodes are in different components, joins them. The latter returns the id of the passed node.

Besides, the client code would check the count data member to see how many components are in. Pythonically, this is exposure of internal status is not perceived as horrifying. A more conservative implementation would mediate this access with a getter.

Moreover, a utility method is provided to check if two node are connected. This is not a strict necessity, still makes the user code more readable:
def connected(self, p, q):
    return self.find(p) == self.find(q)
The meaning of this method is crystal clear. Two nodes are connected only if they have the same id.

In this implementation, we connect two nodes making them share the same id. So, if we call union() on p and q, we'll change the id of one of them to assume the other one. Given this approach, we implement find() in this way:
def find(self, p):
    while p != self.id[p]:
        p = self.id[p]
    return p
If the passed p has id different from its default value, we check the other node until we find one that has its original value, that is the id of the component.

We could implement union() picking up randomly which id keep among the two passed, but we want keep low the operational costs, so we work it out so to keep low the height of the tree representing nodes in a component, leading to O(log n) find() complexity.
def union(self, p, q):
    i = self.find(p)
    j = self.find(q)
    if i != j:  # 1
        self.count -= 1  # 2
        if self.sz[i] < self.sz[j]:  # 3
            self.id[i] = j
            self.sz[j] += self.sz[i]
        else:
            self.id[j] = i
            self.sz[i] += self.sz[j]
1. If the two nodes are already in the same component, there is no need of doing anything more.
2. We are joining two components, their total number in the union-find decrease.
3. This is the smart trick to keep low the cost of find(). We decide which id to keep as representative for the component accordingly with the sizes of the two merging ones.

As example, consider this:
uf = UnionFind(10)
uf.union(4, 3)
uf.union(3, 8)
uf.union(6, 5)
uf.union(9, 4)
uf.union(2, 1)
uf.union(5, 0)
uf.union(7, 2)
uf.union(6, 1)
I created a union-find for nodes in [0..9], specifying eight edges among them, from (4, 3) to (6, 1).
As a result, I expect two components and, for instance, to see that node 2 and node 6 are connected, whilst 4 and 5 not.

I based my python code on the Java implementation provided by Robert Sedgewick and Kevin Wayne in their excellent Algorithms, 4th Edition, following the weighted quick-union variant. Check it out also for a better algorithm description.

I pushed to GitHub full code for the python class, and a test case for the example described above.

Go to the full post

Computing the Edit Distance Between Two Strings

Given two strings, we should compute their edit distance. It is a well know problem, commonly solved by Dynamic Programming.

As we should expect, the idea is very close to the one seen in the previous problem, with the noticeable difference that here we are working on two lists, so our cache is going to be a bidimensional matrix and the complexity of the algorithm is moving to the O(n * m) realm, being n and m the sizes of the two strings in input.

def solution_dp(lhs, rhs):
    table = [[x for x in range(len(rhs) + 1)]]  # 1
    for k in range(1, len(lhs) + 1):
        table.append([k] + [0] * len(rhs))

    for i in range(1, len(table)):
        for j in range(1, len(table[0])):  # 2
            if lhs[i - 1] == rhs[j - 1]:
                table[i][j] = table[i-1][j-1]  # 3
            else:
                table[i][j] = min(table[i - 1][j], table[i][j - 1], table[i - 1][j - 1]) + 1  # 4

    return table[-1][-1]  # 5
1. This is our cache. Instead of having a single dummy cell, here we have both zeroth row and column just filled with zeroes and not touched anymore. Again, not strictly a necessity, still the code is much more readable in this way.
2. Let's loop on all "real" elements in the matrix.
3. If the corresponding characters in the strings are the same, we have a match. Meaning the edit distance won't change, so we just copy in the current cell the value of the one on the left top corner.
4. Otherwise we have seen a change. Since we are looking to the minimal distance, we get the lowest value in the top / left cells, and increase it by one.
5. At the end of the loop, the bottom-right cell contains the result.

Incredible simple, isn't it?

Python code and testcase on GitHub.

Go to the full post

The closest pair of points

Given n points on a plane, find the smallest distance between a pair of two (different) points.

Let's see first a naive solution:
def solution_naive(points):
    size = len(points)
    if size < 2:  # 1
        return 0.0

    result = float('inf')  # 2
    for i in range(size - 1):
        for j in range(i+1, size):
            result = min(result, distance(points[i], points[j]))
    return result
1. If only one point, or no point at all, is passed, the minimum distance is defaulted to zero.
2. Otherwise initialize it to infinite, then loop on all the possible couples of points to find the one with minimum distance.

Where the distance function could be implemented as:
def distance(a, b):
    return math.sqrt((a[0]-b[0])**2 + (a[1]-b[1])**2)

The flaw of this naive implementation is that it has an obvious O(n^2) time complexity. Meaning that it rapidly becomes useless with the growing of the number points in input.

Let's apply a divide and conquer approach to this problem. The thing is that to do that we need a bit of mathematics that is beyond my knowledge. You could read this document by Subhash Suri from UC Santa Barbara for more details.

Firstly we sort the points for their x component, then we call the recursive function:
def solution_dac(points):
    points.sort()
    return closest_distance(points)
We firstly divide the problem up to get pieces that are so simple that they can be solved with the naive algorithm, and apply a merging part to "conquer" that step:
def closest_distance(points):
    size = len(points)
    if size < 4:  # 1
        return solution_naive(points)

    lhs = points[:size // 2]  # 2
    rhs = points[size // 2:]

    left = closest_distance(lhs)
    right = closest_distance(rhs)
    result = min(left, right)
    if result == 0.0:
        return result

    median = (lhs[-1][0] + rhs[0][0]) / 2  # 3
    closers = []
    for i in range(len(lhs)):
        if abs(lhs[i][0] - median) < result:
            closers.append(lhs[i])
    for i in range(len(rhs)):
        if abs(rhs[i][0] - median) < result:
            closers.append(rhs[i])
    closers.sort(key=lambda p: p[1])  # 4

    for i in range(len(closers) - 1):  # 5
        for j in range(i + 1, min(i + 6, len(closers))):
            if abs(closers[i][1] - closers[j][1]) < result:
                result = min(result, distance(closers[i], closers[j]))
    return result
1. For up to 3 points we could use the naive approach.
2. Split the list of points in two parts, left hand side and right hand side, and iterate on them the algorithm. If we see a minimal distance of zero, meaning two overlapping points, there is no use in going on.
3. Draw a line between the rightmost point in the left part of point collection and the leftmost in right part. Then add to a buffer list all the points that have a distance to this median line that is less than the currently found closest distance.
4. Sort the points on their "y" component.
5. And here happens the magic. There is a theorem stating that we could stop checking at 6 when looking for a closest distance in this condition.

The cutoff at 6 ensures that the time complexity of this algorithm if O(n log n).

Full python code on GitHub.

Go to the full post

Majority element

Given a list of integers, return 1 if there is an element that appears more than half the time in the list, otherwise 0.

Naive solution

Loop on all the items in the list, and count each of them. If we find a result that is bigger than half the size of the list, we have a positive result.

We can try to apply some improvement to this algorithm, for instance, we can stop checking as soon as we reach the first element after the half size, and we don't need to check each element from the beginning of the list, since if there is an instance of that element before the current point we have already count it, and if there is not, there is no use in check it. Still, the time complexity is O(n^2), so we can use it only for very short input lists.

Divide and conquer

We divide the problem until we reach the base case of one or two elements - that could be solved immediately. Then we "conquer" this step determining which element is majority in the current subinterval. I described in detail my python code that implements this approach in the previous post.

Sorting

This is a simple improvement of the naive solution, still it is powerful enough to give better results than the divide and conquer approach.

The idea is sorting the input data, and then compare the i-th element against the i-th + half size of the list. If it is the same, that is a positive result. The most expensive part of this approach is in the sorting phase, O(n log n).

Hash table

If we don't mind to use some relevant extra space, we can scan the input list pushing in a hash table each new element that we find, increasing its value each time we see it again. Than we scan the values in the hash table looking for a more than half list size one.

The python Counter collection allows us to solve this problem as a one-liner:
def solution_hash(data):
    return True if Counter(data).most_common(1)[0][1] > len(data) // 2 else False
The time complexity is linear.

Boyer–Moore

The Boyer–Moore algorithm leads to a fun, elegant, and superfast solution.

We perform a first scan of the list, looking for a candidate:
def bm_candidate(data):
    result = None
    count = 0
    for element in data:  # 1
        if count == 0:  # 2
            result = element
            count = 1
        elif element == result:  # 3
            count += 1
        else:
            count -= 1

    return result
1. Loop on all the elements
2. If the candidate counter is zero, we get the current element as candidate, setting the count to one.
3. If we see another instance of the current candidate, we increase the counter. Otherwise we decrease the counter.

This scan ensures to identify the majority element, if it exists. However, if there is not a majority element, it returns the last candidate seen. So we need to perform another linear scan to ensure that the candidate is actually the majority element.

Nonetheless, Boyer–Moore wins easily against the other seen algorithms.

See my full python code for this problem, and the other from the same lot, on GitHub.

Go to the full post

HackerRank Recursion: Davis' Staircase

The point of this HackerRank problem is calculating a sort of uber-Fibonacci number. Since we want to have an efficient solution, we should immediately think to a dynamic programming approach, or at least to some kind of memoization.

Let's call Davis number the number of ways we can climb a staircase, with the rule that we can take 1, 2, or 3 steps at a time.

First thing, we want to identify the base cases. That's pretty easy.
  1. Our staircase has just one step, we have only one way to climb it, taking 1 step.
  2. We can climb it in a single two-step jump, or we can take 1 step, then falling back to the previous case. Total of two ways of climbing.
  3. A single three-step jump is a way to get on top, otherwise we can take one step and falling back to case (2) or take a two-step jump and fall back to case (1). This means 1 + 2 + 1 = 4 ways of climbing this staircase.
The generic case is determined by the three precedent ones, something like this:
result = davis_number(n-1) + davis_number(n-2) + davis_number(n-3)
Given that, I skipped the step of writing a plain recursive solution to the problem, and I moved directly to write a Python script that uses a cache to get the result via DP.

I cached the basic step results as identified above in a list (and I define a constant that make explicit the requirement stating that a staircase could not have more that 36 steps):
cache = [1, 2, 4]
MAX_STEPS = 36
And then I wrote my solution:
def solution(steps):
    assert 0 < steps <= MAX_STEPS  # 1
    if steps <= len(cache):  # 2
        return cache[steps - 1]

    for _ in range(steps - len(cache)):  #3
        cache.append(cache[-1] + cache[-2] + cache[-3])

    return cache[-1]  # 4
1. Without this assertion, the code would become unstable for negative input values (maybe an IndexError exception, maybe simply a wrong result) and would take a very long time for large positive input values. Better a predictable AssertionError instead.
2. The result has been already calculated, and it is available in the cache. Just return it.
3. Let's calculate the required value. To do that, we need to calculate all the previous values, so we extend the cache calculating in order all of them.
4. Finally, we return the rightmost element in the cache, that is, the required Davis' number.

If MAX_STEPS was a bigger number, it could be a good idea to predetermine the full size for the cache, filling it with zeroes, and pushing the actual values when the solutions are created. This would require an extra variable to keep track of the current last Davis number in cache, and would make the code slightly more complicated. Here I found better to keep the code simple.

Full Python script and testcase on GitHub.

Go to the full post

HackerRank Merge Sort: Counting Inversions

I found the description of this problem in its HackerRank page a bit misleading. Better trust its name instead. We have to count the inversions that occur when we run a merge-sort algorithm on list of positive integers.

So, basically, we have to increase a variable to keep track of the inversions and return it to the caller. If you know how to implement merge-sort, large part of the job is done.

The main problem is that they set the timeout very tightly, and it could be tough respecting it, especially if you are using an implementation language that is not among the fastest ones.

I use Python here, so I had to be careful. At least if I don't want to use PyPy to speed everything up.

In the end I came out with this stuff:
def count_inversions(a):
    return merge_sort(a, 0, len(a) - 1)
The required count_inversions() simply calls my adapted merge-sort() function.

Beside sorting, it also stores in the variable result the count of all the inversions, and then will return it.
def merge_sort(a, left, right):
    result = 0
    if left < right:
        center = left + (right - left) // 2
        result += merge_sort(a, left, center)
        result += merge_sort(a, center + 1, right)
        result += merge(a, left, center, right)
    return result
As you see, no surprise, it's a standard merge-sort implementation.

I have spent some sweating on merge, to save to most time I could without getting something still readable:
def merge(data, left, center, right):
def merge(data, left, center, right):
    merged = []  # 1
    result = 0  # 2

    i = left  # 3
    j = center + 1
    while i <= center and j <= right:  # 4
        if data[i] > data[j]:  # 5
            result += (center - i + 1)
            merged.append(data[j])
            j += 1
        else:
            merged.append(data[i])
            i += 1

    for i in range(i, center+1):  # 6
        merged.append(data[i])
    for j in range(j, right+1):
        merged.append(data[j])

    data[left:right+1] = merged  # 7
    return result
1. We need some temporary area where storing the merged data. I use this list.
2. Keep track of the swaps happening here.
3. The main while below runs on two loop variables, i and j, representing the indexes to the left and right elements.
4. Loop until there is at least one element on the left and one on the right to be merged.
5. If an element on the left is bigger than the ones on the right, we have a swap. Or better, as many swaps as the number of elements still on the right.
6. Take care of the leftover.
7. Replace the part of the list on which we worked with the merged elements.

Fast enough to get accepted. Test case and python script on GitHub.

Go to the full post

Hackerrank Tries: Contacts

We are asked to provide a way to store contacts and check how many of them starts with a given prefix. As the name of this HackerRank problem suggests, we are gently pushed in the direction of implementing a trie. The issue is that one of the test cases that the solution has to pass to be accepted - #12 - is a bit too heavy for a plain python implementation.

My initial idea was to create a trie based on this node structure.
class Node:
    def __init__(self):
        self.count = 1
        self.children = {}

trie = Node()
An empty trie is just a node containing an empty dictionary of children.
If I add a new item on it, say a contact named 'x', I create a children with key 'x' and as value a Node created by the above constructor.
If I add a second item with the same starting letter, say 'xy, I increase the counter for the 'x' element and then create a 'y' element as its child.

I need two functions to implement the required interface, add() and find():
def add(node, data):
    pass


def find(node, data):
    pass
Given this skeleton, I written a python test unit based on the sample given by HackerRank:
def test_provided_1(self):
    add(trie, 'hack')
    add(trie, 'hackerrank')
    self.assertEqual(2, find(trie, 'hac'))

def test_provided_2(self):
    add(trie, 'hack')
    add(trie, 'hackerrank')
    self.assertEqual(0, find(trie, 'hak'))
I played a bit around, in the end I came out with this implementation:
def add(node, name):
    for letter in name:
        sub = node.children.get(letter)  # 1
        if sub:
            sub.count += 1
        else:
            sub = node.children[letter] = Node()  # 2
        node = sub  # 3
1. I am looping on each letter of the passed contact name, if the children dictionary in this level contains the relative letter, I access that node and increase its counter.
2. Otherwise I create a new node in the dictionary using as key the current letter.
3. Then I follow the recursive trie structure passing to the node in the level below.

Finding the counter associated to a prefix in a trie is just a matter of following its path in the tree.
def find(node, data):
    for letter in data:
        sub = node.children.get(letter)  # 1
        if not sub:
            return 0
        node = sub
    return node.count  # 2
1. If we don't find a letter in the path we are following in a matching level of the tree, there is no contact with such prefix. Otherwise we get the node among the children and pass to the level below.
2. If we have not intercepted a missing letter, the counter associated to the current node is the answer we want pass back to the caller.

This works fine, it is just a bit slow, with all the nodes that we create for each name we push in the trie.

We need a faster solution. A way would be changing programming language, and it looks very easy to convert this code in plain C. However, I had an idea that could make the algorithm faster.

Basically, I want to reduce the number of nodes created. When I insert the first name, for instance 'hack', I don't know if I really need to split it letter by letter. Maybe it will be the only contact starting by 'h'. So, I could keep it in a single chunk. Just one node instead of four. Good deal.
I pay it when I insert 'hackerrank', here I am forced to split 'hack' letter by letter (actually, I could have been more conservative, and keep the common prefix 'hack' in a single node. I kept it as a note. If the simpler split-all technique I went for was not enough, I would have tried this other approach). Still I let the tail of the new name, 'errank', in a single node.

Let's try it. No pun intended.

I have to store the actual piece of data in any Node:
class Node:
    def __init__(self, data=None):
        self.count = 1
        self.data = data
        self.children = {}

trie = Node()
Adding gets more complicated, since I have to think about splitting:
def add(node, name):
    for i in range(len(name)):  # 1
        sub = node.children.get(name[i])
        if not sub:
            node.children[name[i]] = Node(name[i:])  # 2
            return

        sub.count += 1
        if sub.data == name[i:]:  # 3
            return
        elif len(sub.data) > 1:  # 4
            split = sub.data[1:]
            sub.data = sub.data[0]
            sub.children[split[0]] = Node(split)
        node = sub  # 5
1. I can't use anymore the handy for-each loop, I must fallback to a plain for in range one since I need the current position in the word to split it when required.
2. When I detect a missing node I created it. The node is not associated anymore to a single letter in the name, but to the full chunk starting from the current position to the end of the word.
3. When I get a match, things are getting a bit more complicated. But not in this specific case, when the tail of the current word is a match with the content of the current node. Job done!
4. Here is the real extra work. The current node contains a chunk of two or more letters, and they don't match with the chunk from the new name. I need to split, I don't do any check on what I am splitting, I simply slice off one letter from the current chunk, let the first one in this node and put the rest in the child relative to the first letter of the split.
5. Back on the original track. I move to the node in the level below, and I am ready to the next step.

Finding stays simple, just a minor change:
def find(node, data):
    for i in range(len(data)):  # 1
        node = node.children.get(data[i])
        if not node:
            return 0
        if node.data.startswith(data[i:]):  # 2
            break
    return node.count
1. We need to know the position in the current word, here too.
2. We find the node when the data in it contains the current chunk of the new name, starting from its current position to its end.

Now the algorithm is fast enough so that also this python implementation gets fully accepted. I pushed on GitHub both versions, the "plain" one and the "chunk" one, and the relative unit tests.

I pushed a new python script on GitHub, that follows the code passed as anonymous comment here below (thank you again for contributing). It'a a "no trie" solution that works fine. I just changed the 'find' operation implementation to get rid of the try-except check. Being myself an old C++ programmer I always feel not at ease with throwing exceptions when I can avoid to.

Even though the rule of the games would push us to write a trie solution, I think it is a good idea to have a look at an implementation that avoid it. We could imagine what is its weak point, lots and lots of elements created, whereas the trie promises to reduce them on the long run. We should choose which implementation to use accordingly to the actual problem we are working with.

Go to the full post

HackerRank Tree traversal

Given a Binary Search Tree, give its node values following the in-order, pre-order, post-order, and level-order traversals, using both recursive and iterative algorithms. Actually, the HackerRank problem that gave me the idea for this post asks only to implement the level-order traversal algorithm, and you can write the code as you like, so probably in the iterative way, that comes more natural in this case.

Firstly, I sketched a BST on paper, to better visualize the problem. Nothing fancy, but not too basic too. Something like this.
Then I wrote the unit test for the eight functions I am about to write, using Python as implementation language. That lead me naturally to describe the data type Node that they all use, and setting up each test translating the picture I had of my BST in a data structure in my code.
class Node:
    def __init__(self, data, left=None, right=None):
        self.data = data
        self.left = left
        self.right = right

# ...
  
class TestCodeEval(unittest.TestCase):

    def setUp(self):
        node1 = Node(1)
        node2 = Node(2, node1)
        node4 = Node(4)
        node7 = Node(7)
        node5 = Node(5, node4, node7)

        self.root = Node(3, node2, node5)
As you can see, I gave to Node the bare minimal stuff to make it work.
def test_in_order_r(self):
    self.assertEqual([1, 2, 3, 4, 5, 7], in_order_r(self.root))

def test_in_order_i(self):
    self.assertEqual([1, 2, 3, 4, 5, 7], in_order_i(self.root))

def test_pre_order_r(self):
    self.assertEqual([3, 2, 1, 5, 4, 7], pre_order_r(self.root))

def test_pre_order_i(self):
    self.assertEqual([3, 2, 1, 5, 4, 7], pre_order_i(self.root))

def test_post_order_r(self):
    self.assertEqual([1, 2, 4, 7, 5, 3], post_order_r(self.root))

def test_post_order_i(self):
    expected_values = [1, 2, 4, 7, 5, 3]
    result = post_order_i(self.root)
    self.assertEqual(len(expected_values), len(result))
    for expected, actual in zip(expected_values, result):
        self.assertEqual(expected, actual)

def test_level_order_r(self):
    self.assertEqual([3, 2, 5, 1, 4, 7], level_order_r(self.root))

def test_level_order_i(self):
    self.assertEqual([3, 2, 5, 1, 4, 7], level_order_i(self.root))
The 'r' or 'i' at the end of the function names hint which version of the algorithm I plan to implement in there, recursive or iterative.
I have written the post-order iterative test in a slightly different way to hide the fact that I let this function return a deque instead of a plain list. Just to stress that is a bit different from all the other also when it comes to write it. In production code you don't usually want to leave such a thing. Better to convert the return value inside the function.

In order

The in/pre/post order traversals are so intrinsically recursive that could be easily written as a one-liner in Python. I have force myself to be more readable, still the code is very compact and nice to see.
def in_order_r(node):
    if not node:
        return []
    return in_order_r(node.left) + [node.data] + in_order_r(node.right)
I go down to fetch the most to the left node, then up, completing the left branch before looking in the right one.

If we don't want to use recursion, we need to explicitly use a stack.
def in_order_i(node):
    if not node:
        return []

    cur = node
    result = []
    stack = []
    while True:
        if cur:
            stack.append(cur)
            cur = cur.left
        elif stack:
            cur = stack.pop()
            result.append(cur.data)
            cur = cur.right
        else:
            return result
We push the nodes in the stack, until we find a leftmost node, than we pop the last node we pushed to the stack and put its value in the result. Look for what is now the leftmost node, and so on, until we consume all the nodes.

Pre order

The recursive code is almost the same.
def pre_order_r(node):
    if not node:
        return []
    return [node.data] + pre_order_r(node.left) + pre_order_r(node.right)
In this case, first we check the left subtree, than the right one, and finally we get the one on top.

The iterative version asks again for an explicit stack where to store the nodes temporary set apart. The loop is even more natural than the in-order one.
def pre_order_i(node):
    if not node:
        return []

    result = []
    stack = [node]
    while stack:
        cur = stack.pop()
        result.append(cur.data)
        if cur.right:
            stack.append(cur.right)
        if cur.left:
            stack.append(cur.left)

    return result
Push the root on the stack before starting the loop, then consume the top of the stack and add its children.

Post order

Again, a very clean recursive implementation.
def post_order_r(node):
    if not node:
        return []
    return post_order_r(node.left) + post_order_r(node.right) + [node.data]
The iterative version is not so immediate. At least, I spent some time on it thinking how was better to proceed. The trick is looking to the pre-order implementation and change, seeing the structure similarity, and acknowledging the differences. At first sight, they look completely different. However, if you reverse the result of the post-order traversal, you could see that something is there. Beside reversing, we need also to consider the branch in different order. This means, I am pushing the result in a queue (actually a deque, the python Queue is not a good choice in this context) and not in a stack, and I reverse the order of pushing nodes in the stack.
def post_order_i(node):
    if not node:
        return []

    stack = [node]
    result = deque()
    while stack:
        cur = stack.pop()
        result.appendleft(cur.data)  # 1
        if cur.left:
            stack.append(cur.left)  # 2
        if cur.right:
            stack.append(cur.right)
    return result
1. Push to the left in the result, and not to the right as in pre-order.
2. First the left node and then the right one.

Level order

This is kind of different from the other traversals. The recursive implementation is less immediate, and it usually comes more natural to implement it in an iterative way.

Here too it comes handy using a queue (again, here a deque because of Python) but instead of the stack, not for the result. This is because we want to get the value list level by level, so the first node we push to the buffer should be the first one to be consumed.
def level_order_i(node):
    result = []
    buffer = deque([node])
    while buffer:
        cur = buffer.popleft()
        result.append(cur.data)
        if cur.left:
            buffer.append(cur.left)
        if cur.right:
            buffer.append(cur.right)
    return result
If we really want to implement it in a recursive way, it is probably a good idea to have an helper function, since we have to carry on all the nodes at the same level, to have a way to check the level below.

Let the user call it passing the root, as usual, then convert it to a list an call the helper function:
def level_order_r(node):
    return level_order_rs([node])
In the result list we store, as usual, the values of the nodes we have already found, then we populate a list with the children of the nodes on this level, and we pass them to a recursive call.
def level_order_rs(nodes):
    result = []
    below = []
    for node in nodes:
        result.append(node.data)
        if node.left:
            below.append(node.left)
        if node.right:
            below.append(node.right)
    if below:
        result += level_order_rs(below)
    return result
I pushed both the unit test and the python script to GitHub.

Go to the full post

Maximum slice problem

On Codility there is a section dedicated to problems about determining the maximum slice in a vector. The generic problem, disscused in a pdf, is this:

Given a vector of integers, find the slice with the largest sum, and return that value.

An example is provided, that I converted on the spot to a C++11 GoogleTest test case:
TEST(MaxSlice, Given)
{
    std::vector<int> input { 5, -7, 3, 5, -2, 4, -1 };
    EXPECT_EQ(10, solution(input));
}
The biggest slice is the one ranging from input[2] to input[5], resulting in a sum of 10.

A quadratic solution

It shouldn't be complicated to think of a solution asymptotically quadratic in time. Loop on all the elements in the sequence. For each of them loop on all the subsequence starting there up to the input end, calculating their sums. The biggest one of them is our result.

Here is a possible implementation of this algorithm:
int solution(const std::vector<int>& input)
{
    int result = 0;
    for(unsigned i = 0; i < input.size(); ++i) // 1
    {
        int tentative = 0; // 2
        for(unsigned j = i; j < input.size(); ++j) // 3
        {
            tentative += input[j];
            result = std::max(result, tentative); // 4
        }
    }
    return result;
}
1. Check all the subsequences, defining i as their begin.
2. Store here the sum for the current subsequence.
3. Try all the possible subsequences starting from i.
4. Save the current subsequence if it is the current biggest one.

A linear solution

The previous solution works fine, but it mindlessly repeat adding on and on the same elements. We could save time just performing a single linear scan of our data, observing that when we get a negative result adding an element, it is more worthy to get rid of that subsequence, and starting from the next element:
int solution(const std::vector<int>& input)
{
    int result = 0;
    int candidate = 0;
    for(int cur : input)
    {
        candidate = std::max(0, candidate + cur); // 1
        result = std::max(result, candidate); // 2
    }

    return result;
}
1. Keep the candidate until adding the current element gives a positive value. Otherwise, reset the sequence. In the worst case, all negative input element, we won't never accept any value, and we would return the total relative to the empty subsequence, namely zero.
2. If the current candidate is a better solution, save it.

This problem is better known as maximum subarray problem, and the linear solution above was firstly found by Jay Kadane. That's way it is called Kadane's algorithm.

Go to the full post

Shortest path by breadth-first search

Given an undirected unweighted graph that has no loop, we can use a basic breadth-first search algorithm to determine the shortest path from a specified vertex to any (other) one in the graph.

In the previous post I showed a way to store a graph in a C++11 STL container (a vector of forward list of unsigned int). This is the Graph class you are going to see in the code below. Besides, Vertex is a typedef for unsigned int, meaning that we identify a vertex simply by an unsigned number, starting from zero.

This is the class I want to develop:
class BreadthFirstSearch
{
private:
    std::vector<Vertex> parents_; // 1
    Vertex start_; // 2
public:
    BreadthFirstSearch(const Graph& graph, Vertex start); // 3
    std::vector<Vertex> path(Vertex end); // 4
    std::vector<Vertex> backpath(Vertex end); // 5
    void printPath(Vertex end); // 6
};
1. As a result of the breadth-first search algorithm I want to put in this vector the closest ancestor to the start one of any vertex in the associated graph.
2. This is the vertex that I want to use as starting point for BFS algorithm.
3. The ctor gets in input a Graph and one of its vertex and fills the parents_ vector as expected.
4. This method returns the path from the start vertex, as specified by the ctor, to the passed end one.
5. Not strictly a necessity, it could be a private method. Provides the shortest path in reversed order, from end to start.
6. Utility method, dump to standard output a shortest path.

The BreadthFirstSearch constructor implements the BFS algorithm in this way:
BreadthFirstSearch::BreadthFirstSearch(const Graph& graph, Vertex start) :
        parents_(graph.vertices_.size(), std::numeric_limits<Vertex>::max()), start_(start) // 1
{
    if (start >= graph.vertices_.size()) // 2
        return;

    std::vector<bool> seen(graph.vertices_.size()); // 3
    std::queue<Vertex> queue; // 4

    queue.push(start); // 5
    seen[start] = true;
    while (!queue.empty()) // 6
    {
        Vertex vertex = queue.front();
        queue.pop();

        for (auto it = graph.vertices_[vertex].begin(); it != graph.vertices_[vertex].end(); ++it) // 7
        {
            Vertex next = *it;
            if (!seen[next]) // 8
            {
                queue.push(next);
                seen[next] = true;
                parents_[next] = vertex;
            }
        }
    }
}
1. Initially, the parents_ vector contains just "no parent" elements. I used the largest value available for a Vertex to represent such state.
2. Event though this code is not production ready, I couldn't help to put at least a minimal error handling in it. The vertex passed as starting point should be an actual Graph element.
3. This vector keep track of all the vertices that have been already checked in a previous step of the algorithm. Initially no one is, so we could rely on the default behavior for the vector ctor that sets to false all its elements.
4. On this queue I'll put all the vertices that are connected to the one is currently checked.
5. Let's put the control variables in the initial condition. The start vertex is enqueued, and it is marked as seen.
6. Loop until all the elements in the queue are processed.
7. Loop on all the vertices connected to the current one.
8. If this vertex has not already processed, push it in queue, mark it as seen, set as its next the current vertex.

The BreadthFirstSearch ctor has filled the parents_ vector, now we can use it to create the shortest path from the start vertex to a specific one:
std::vector<Vertex> BreadthFirstSearch::path(Vertex end)
{
    std::vector<Vertex> backtrace = backpath(end); // 1
    return std::vector<Vertex>(backtrace.rbegin(), backtrace.rend()); // 2
}
1. Actually, the real job is delegated to backpath().
2. Since backpath() returns a reversed path, the only real task of this method is reverting the vector to return a "stright" one.

If you want the path to be stored in a vector, you will find that it is in the nature of the problem to generate a reversed solution. Or maybe you could use a deque, filling it from the front. Anyway, this is my solution:
std::vector<Vertex> BreadthFirstSearch::backpath(Vertex end)
{
    std::vector<Vertex> backtrace; // 1
    if (end >= parents_.size()) // 2
        return backtrace;

    for (Vertex cur = end; cur != std::numeric_limits<Vertex>::max(); cur = parents_[cur])
        backtrace.push_back(cur); // 3
    return backtrace;
}
1. I am going to backtracing from the passed graph vertex up to the starting one, pushing each parent in this vector.
2. Better to ensure the caller won't pass a nonexistent vertex.
3. Each ancestor is pushed back in the vector, until the "no parent" element is found.

The utility method that dumps the path to standard shows how to use backpath():
void BreadthFirstSearch::printPath(Vertex end)
{
    std::vector<Vertex> vxs = backpath(end);
    std::copy(vxs.rbegin(), vxs.rend(), std::ostream_iterator<Vertex>(std::cout, " "));
    std::cout << std::endl;
}
Here is a piece of code that uses my BreadthFirstSearch class:
BreadthFirstSearch bfs(graph, 0); // 1
bfs.printPath(3); // 2
1. I pass to bfs the graph object as created in the previous post example, and I specify zero as the starting vertex.
2. Ask to print the shortest path from zero to three.

The expected result is:
0 4 3 

Go to the full post

Greedy algorithm for activity selection

A typical example of problem that has an optimal solution by implementing a greedy algorithm is the activity selection one, here is its description on wikipedia. In few words, we have a bunch of activities, identified by a start and end time, and we want to find a maximum selection of non-conflicting elements.

A couple of test cases (written in C++11 for GoogleTest) should clarify the problem:
typedef std::pair<int, int> Activity;
typedef std::vector<Activity> Activities;

TEST(ActSel, Simple)
{
  Activities input { {1, 2}, {5, 9}, {0, 6}, {8, 9}, {3, 4}, {5, 7} };

  Activities output = selectMax(input);
  ASSERT_EQ(4, output.size());
  for(unsigned i = 1; i < output.size(); ++i)
    ASSERT_LE(output[i-1].second, output[i].first);
}

TEST(ActSel, Simple2)
{
  Activities input { {1, 4}, {3, 5}, {0, 6}, {3, 9}, {5, 9}, {5, 7}, {6, 10}, {8, 11}, {8, 12}, {2, 14}, {12, 16} };

  Activities output = selectMax(input);
  ASSERT_EQ(4, output.size());
  for(unsigned i = 1; i < output.size(); ++i)
    ASSERT_LE(output[i-1].second, output[i].first);
}
In both cases I expect a selection of four Activity objects in output. In the first case these elements: (1, 2) (3, 4) (5, 7) (8, 9), in the second one (1, 4) (5, 7) (8, 12) (12, 16), or maybe (8, 11) instead of (8, 12). As you can see, there could be more solutions, and the problem doesn't require you to be particolary choosy. Once you maximize the number of selected items, the actual value of each of them is not an issue.

Still, I want to ensure in my test cases that I peak a valid solution, so I check, through ASSERT_LE, that all the elements in the extracted sequence are ordered as expected.

As said above, this problem has a greedy optimal solution. What we have to do is just sorting the input elements by their second component (the end time), and then greedily accepting all the elements we can. As in this implementation:
Activities selectMax(Activities& input) // 1
{
  std::sort(input.begin(), input.end(), [](Activity a, Activity b) { return a.second < b.second; }); // 2

  Activities output;
  output.push_back(input[0]); // 3

  for(unsigned i = 0, j = 1; j < input.size(); ++j) // 4
  {
    if(input[j].first >= input[i].second) // 5
    {
      output.push_back(input[j]);
      i = j;
    }
  }

  return output;
}
1. We don't mind if this function modify the input parameter, so it is passed as non-constant reference. Beware that this should be know and accepted by the callers.
2. The "normal" STL sort() function would order the passed sequence by its first component. So we need to use the overloaded version that let as pass a predicate to be used as comparator. Using a C++11 lambda function, as shown here, makes it simple and elegant.
3. The first element is always selected.
4. Now we are ready to loop on all the other elements in the sequence. The real looping variable is j, while i is used to keep track of the last accepted element.
5. The first element after the last accepted one that starts not before the end of it, is pushed in the output sequence.

Go to the full post

Rod cutting by dynamic programming

A typical problem that suits well to show how dynamic programming works. We have a rod sized up to, let's say, 10. We can freely cut it in pieces (integer sized) to sell them at the best price. Given a price table, find out the way to get the most from it.

Here is a C++11 test case for GoogleTest that should clarify the requirements:
typedef std::vector<int> Vector;

unsigned cutRod(const Vector& price, unsigned size);

TEST(CutRod, Simple)
{
  Vector price { 1, 5, 8, 9, 10, 17, 17, 20, 24, 30 };

  ASSERT_EQ(30, cutRod(price, 10));
  ASSERT_EQ(25, cutRod(price, 9));
  ASSERT_EQ(18, cutRod(price, 7));
  ASSERT_EQ(10, cutRod(price, 4));
}
Given that price list, we see immediately that if we have in input a rod sized up to 3, the best strategy is selling it in a single piece.
But if we have a rod sized four, selling it untouched we'll get 9. Better if we split it in two rodes both sized two, that give us 5 + 5 = 10.
Similarly, a rod sized 7 is priced 17. If we split it in two parts sized 6 and 1, we'll get 17 + 1 = 18.

Brute force

We may think to apply a recursive approach to this problem to check all the possible cut combinations we can think of. It is very easy to write the relative code, but can't we expect it to scale well:
unsigned cutRod(const Vector& price, unsigned size)
{
  unsigned result = 0;
  for(unsigned i = 0; i < size; ++i)
    result = std::max(result, price[i] + cutRod(price, size - (i+1)));

  return result;
}
It is just a matter of recursively calling our function reducing each time the size of the rod we are considering. We compare any time the partial result with the one we have previously stored, keeping just the best one.

Top-down dynamic programming

One obvious problem in the previous solution is that we solve again and again the same sub-problems. We could save lot of running time storing them in a buffer. This simple but effective idea is the basic of the dynamic programming technique.

In this context, the bargain of using space to avoid spending time repeating the same task to get a partial result is called memoization (as keeping a memo).

Here is a possible top-down implementation, very close to the naive version seen above:
unsigned cutRod(const Vector& price, unsigned size)
{
  Vector memo(size + 1, -1);
  memo[0] = 0;

  return memoCutRod(price, size, memo);
}
Here cutRod() just creates a memo vector that would store the values for each sub-problem, as soon as we get its result. Then it would start the recursion calling a support function.

Notice that the memo buffer has one element more than the price list. This is for storing also the value of the dummy cut sized zero. It is not a strict necessity, since we know that it won't cost anything, but it would help to make our code cleaner.
unsigned memoCutRod(const Vector& price, unsigned size, Vector& memo)
{
  if(memo[size] >= 0) // 1
    return memo[size];

  unsigned result = 0; // 2
  for(unsigned i = 0; i < size; ++i)
    result = std::max(result, price[i] + memoCutRod(price, size - (i+1), memo));

  return memo[size] = result; // 3
}
1. If the realtive memo buffer is not negative, we have already calculated it. Job already done.
2. Otherwise we calculate the best price as seen before.
3. And we set a memo before returning it.

Bottom-up approach

Again dynamic programming, still using memoization as we have just seen, but starting from the bottom of the problem and crawling up to its top. In this case the implementation is even simpler, and avoid us the pain and the cost of recursion:
unsigned cutRod(const Vector& price, unsigned size)
{
  Vector memo(size + 1); // 1
  for(unsigned i = 1; i <= size; ++i) // 2
  {
    int value = -1; // 3
    for(unsigned j = 0; j < i; ++j) // 4
      value = std::max(value, price[j] + memo[i-j-1]);
    memo[i] = value;
  }

  return memo.back(); // 5
}
1. As in the top-down approach, we get an extra element in the memo vector, just to keep simpler the code. But this time we don't need to initialize it to a "bad" values, because we are setting it up iteratively starting from the beginning.
2. First element in memo is already set to its expected value (that is, zero) as courtesy of the vector constructor. We need to calculate all the other elements, up to the rightmost one.
3. Initialize the current memo value to less than the minimum acceptable value (meaning, less than zero).
4. Basically it is the same loop we have seen in the previous implementations, but here we explicitly go for the smaller element first.
5. End of the story, the answer is stored in the rightmost memo element.

Check on github for full C++11 code.

Go to the full post

Quicksort

Quicksort is known to be a fast O(N lg N) divide and conquer sorting algorithm, in its average behavior. Still we have to pay attention to the worst case scenario, that brings it to a O(N ** 2) time cost.

The idea is repetitively partitioning the data collection, splitting it in two parts, in a way that a randomly chosen pivot would be equal or greater than the values on its left partition, and then call again the quicksorting procedure, until there is nothing more left to sort. As one could easily spot, is a possible bad choice of the pivot that could lead to poor performances.

The resulting code should be something like this:
void quicksort(std::vector<int>& data, int left, int right) // 1
{
  if(left < right) // 2
  {
    int pivot = partition(data, left, right); // 3
    quicksort(data, left, pivot - 1); // 4
    quicksort(data, pivot + 1, right);
  }
}
1. The function requires in input the collection on which it should operate and the indexes of its leftmost and rightmost elements.
2. Check if the interval is not empty.
3. Split the original interval in two parts. On the left side we have all the values less or equal to the value in the pivot element.
4. Call again quicksort on the left and right partitions. Notice that the pivot element is already in the right place, and don't need to be considered anymore.

We just need to partition a collection as expected:
int partition(std::vector<int>& data, int left, int right)
{
  int pivot = data[right]; // 1
  int index = left - 1; // 2

  for(int i = left; i < right; ++i) // 3
  {
    if(data[i] <= pivot) // 4
      std::swap(data[++index], data[i]);
  }

  std::swap(data[++index], data[right]); // 5
  return index;
}
1. OK, this doesn't look smart. As pivot we always select the rightmost element in the interval.
2. Initialize index to the first-before-beginning position in the interval.
3. Loop on all the items in the interval, but the last one (that is, the pivot).
4. If the current element value is less than the pivot, let's swap it with the first not already used element on the left.
5. Finally, we swap the pivot (rightmost value in the interval) with the element next to index.

Full C++ code on github.

Go to the full post

Heapsort

Heapsort is an in-place sorting algorithm, like insertion sort, that asympthotically scores a nice O(N lg N) time complexity, like merge sort.

It makes use of the heap data structure, that is a normal array seen as a nearly complete binary tree, in its max-heap flavor. Meaning that its biggest value is placed in the first element of the array (considered as the root of the tree).

Implementing heapsort in C++ is pretty trivial, since it just a matter of calling two STL algorithm functions:
#include <vector>
#include <algorithm>

void heapsort(std::vector<int>& data)
{
  std::make_heap(data.begin(), data.end()); // 1
  std::sort_heap(data.begin(), data.end()); // 2
}
1. This make_heap() call rearranges the passed elements as a max-heap.
2. This sort_heap() call assumes that the passed sequence is a max-heap and sort it in ascending order.

But let's have some fun reimplementing by hand these two functions:
typedef std::vector<int> Vector;

void heapsort(Vector& data)
{
  buildMaxHeap(data);
  sortHeap(data);
}
We'll need a way to navigate down the binary heap:
unsigned childLeft(unsigned i) { return (2 * i) + 1; }
unsigned childRight(unsigned i) { return (2 * i) + 2; }
The root element is at index 0. Its children are on 1 and 2.
The left child of the root (index 1) has its own children on 3 and 4; its sibling (index 2) on 5 and 6.
We can get the index of the children of a generic node in a binary heap just multiplying its index by two and adding 1 (for the left one) or 2 (for the right one).
And we'll need a function to ensure that a node in the data structure is complying to the binary max-heap requisite (it should be bigger than its children):
void maxHeapify(Vector& data, unsigned i, unsigned len) // 1
{
  unsigned left = childLeft(i);
  unsigned right = childRight(i);

  unsigned largest = (left < len && (data[left] > data[i])) ? left : i;
  if(right < len && (data[right] > data[largest]))
    largest = right;

  if(largest != i) // 2
  {
    std::swap(data[i], data[largest]); // 3
    maxHeapify(data, largest, len); // 4
  }
}
1. We pass to the function the data collection, the index of the element that we are checking, and the number of element in the heap.
2. We have compared the current node value against the ones of its left and right children. If the largest one is a children, the rule of the heap is currently violated. We need to rearrange the nodes.
3. Firstly, we need to swap the nodes so that the largest one is above the other ones.
4. Then, we need to ensure that the swapping has not corrupted the max-heap structure.

We are finally ready to implement the two main functions:
void buildMaxHeap(Vector& data) // 1
{
  for(int i = data.size() / 2; i >= 0; --i) // 2
    maxHeapify(data, i, data.size());
}

void sortHeap(Vector& heap) // 3
{
  for(int i = heap.size() - 1; i > 0; --i) // 4
  {
    std::swap(heap[0], heap[i]); // 5
    maxHeapify(heap, 0, i); // 6
  }
}
1. Given an arbitrary collection of values, convert it to a max-heap.
2. Start from the bottom, up to the root.
3. We assume that the passed data respect the max-heap constrains.
4. We scan the heap starting from the rightmost element up to the second one.
5. We know that the heap root is the biggest element in the collection, so we swap it to the rightmost position.
6. Before starting a new iteration, we ensure that the data collection (except the one we have already sorted) is still a max-heap.

Full C++ source code and a couple of test cases for Google test on github.

Go to the full post

Maximum subarray by Kadane

I have already shown a solution to the maximum subarray problem, based on an algorithm that follows the divide and conquer recipe. Here I give a couple of C++11 implementations based on the asyntotically better algorithm devised by Professor Kadane in the dynamic programming spirit.

The basic idea is keeping memory of the higher sum already reached and increasing a current sum. If the current sum gets higher than the historical one, also that one is increased.

This is a first version, that calculates just the sum:
typedef std::vector<int> Vector;

int maxSubAr(const Vector& data)
{
  int sum = 0;
  int sumTmp = 0;

  for(unsigned i = 0; i < data.size(); ++i)
  {
    if(int value = sumTmp + data[i] > 0) // 1
      sumTmp = value;
    else
      sumTmp = 0;

    if(sumTmp > sum) // 2
      sum = sumTmp;
  }

  return sum;
}
1. Add the current element value to the temporary sum. If this leads to a positive number, this will be the new temporary sum, otherwise I reset it.
2. If the temporary sum is bigger than the previously saved sum, I save this new value.

And that's it. Incredibly simple and effective.

Things get a bit more complicated when we want to get also the first-last index of the subsequence:
typedef std::array<int, 3> Info;
typedef std::vector<int> Vector;

Info maxSubArray(const Vector& data)
{
  int left = 0;
  int right = 0;
  int sum = 0;

  int leftTmp = 0;
  int sumTmp = 0;

  for(unsigned i = 0; i < data.size(); ++i)
  {
    int value = sumTmp + data[i];
    if(value > 0)
    {
      if(sumTmp == 0) // 1
        leftTmp = i;
      sumTmp = value;
    }
    else
      sumTmp = 0;

    if(sumTmp > sum) // 2
    {
      left = leftTmp;
      right = i;
      sum = sumTmp;
    }
  }

  return {{ left, right, sum }};
}
1. If I am at the beginning of the sequence, or if I have just reset the temporary sum, the current value is at the tentative first element of the subsequence.
2. When I see that the current sum is bigger than the one already discovered, I adjust also the left/right indexes.

Full C++11 code is on github, with a few GoogleTest test as a bonus.

Go to the full post

Maximum subarray by divide and conquer

Given an array containing positive and negative integers, we want to determine a subarray containing the largest sum of elements.

A couple of test cases, written in C++11 for GoogleTest, should make clearer the problem:
typedef std::array<int, 3> Info; // 1
typedef std::vector<int> Vector; // 2

TEST(MaxSub, Simple) // 3
{
  Vector input { 2, 3, 4, 5, 7 };

  unsigned last = input.size() - 1;
  Info sub = maxSubArray(input, 0, last);
  EXPECT_EQ(0, sub[0]);
  EXPECT_EQ(last, sub[1]);
  EXPECT_EQ(21, sub[2]);
}

TEST(MaxSub, Simple2) // 4
{
  Vector input {-2, -5, 6, -2, -3, 1, 5, -6};

  Info sub = maxSubArray(input, 0, input.size() - 1);
  EXPECT_EQ(2, sub[0]);
  EXPECT_EQ(6, sub[1]);
  EXPECT_EQ(7, sub[2]);
}

TEST(MaxSub, Negative) // 5
{
  Vector input {-2, -5, -2, -3, -6};

  Info sub = maxSubArray(input);
  EXPECT_EQ(0, sub[0]);
  EXPECT_EQ(0, sub[1]);
  EXPECT_EQ(0, sub[2]);
}
1. I want the function to return three values, the delimiting subarray indexes, and the found sum.
2. This is the container used to keep the input data.
3. Trivial case, all positive elements, the function would return 0, the last element index, and all element sum.
4. A typical case, nothing fancy.
5. If no positive element is in input, the result is an empty subarray.

We could use a divide and conquer approach to get a solution. Here is my C++11 implementation. Firstly, here is the divide part:
Info maxSubArray(const Vector& data, int left, int right)
{
  if(left == right) // 1
    return {{ left, right, data[left] }};

  int middle = (left + right) / 2; // 2

  Info subLeft = maxSubArray(data, left, middle); // 3
  Info subRight = maxSubArray(data, middle + 1, right);
  Info crossing = maxCrossing(data, left, middle, right); // 4

  return max(subLeft, subRight, crossing); // 5
}
1. If left and right index are actually the same, the problem is trivial.
2. Otherwise we split the interval in two parts. And
3. Recursively call the divide function on the left and right parts.
4. The hard job is done here. We need to check also the sequences that star before the middle point and end after it.
5. Once we get the three partial results, it is just a matter of checking which one has the highest sum and return it. To do that I have written a max() function that I guess you won't need to see to get how it works. In any case you will find it on github.

Let's see how to get the max subarray that crosses the central element. The idea is pretty simple, get the left and right max sum, starting from the middle point and moving outward, and then merge it:
Info maxCrossing(const Vector& data, int left, int middle, int right)
{
  int sum = 0;

  int maxLeft = middle;
  int leftSum = std::numeric_limits<int>::min();
  for(int i = middle; i >= left; --i) // 1
  {
    sum += data[i]; // 2
    if(sum > leftSum)
    {
      leftSum = sum;
      maxLeft = i;
    }
  }

  sum = 0; // 3
  int maxRight = middle + 1;
  int rightSum = std::numeric_limits<int>::min();
  for(int i = middle + 1; i <= right; ++i)
  {
    sum += data[i];
    if(sum > rightSum)
    {
      rightSum = sum;
      maxRight = i;
    }
  }

  return {{ maxLeft, maxRight, leftSum + rightSum }}; // 4
}
1. Loop on the elements, starting from the middle element to the leftmost one.
2. Tentatively add to the sum value the current value. If it is bigger to the precedently stored left sum value, adjust it and its leftmost index.
3. The right part is scanned specularly.
4. Put together left and right partial result to get the return value.

Full source C++11 code and a few test cases are on github.

Go to the full post

Merge sort

Typical example of a divide and conquer approach applied to the sorting problem. It's O(n lg n) time complexity makes it interesting for large enough data collections.

This algorithm's idea is that we could split recursively the problem until we have a tiny subproblem so simple that is trivial to solve it. Than we just have to merge the partial results to get the actual solution.

Here is the "divide" part, implemented in C++:
typedef std::vector<int> Data;

void mergeSort(Data& data, int left, int right) // 1
{
    if(left < right) // 2
    {
        int center = (left + right) / 2;
        mergeSort(data, left, center); // 3
        mergeSort(data, center + 1, right);
        merge(data, left, center, right); // 4
    }
}
1. The function expects in input the collection to sort and the first/last indexes to consider.
2. If there is just one element to sort, there is nothing to do.
3. Split the problem it two parts and recursively call the divide function on them.
4. Merge the partial solutions.

As one would expect, large part of the job is done by the merging function:
typedef std::queue<int> Queue;

void merge(Data& data, int left, int center, int right)
{
    Queue low; // 1
    Queue high;

    for(int i = left; i <= center; ++i) // 2
        low.push(data[i]);
    for(int i = center + 1; i <= right; ++i)
        high.push(data[i]);

    int i = left;
    while(!low.empty() && !high.empty()) // 3
    {
        if(low.front() <= high.front())
        {
            data[i++] = low.front();
            low.pop();
        }
        else
        {
            data[i++] = high.front();
            high.pop();
        }
    }

    while(!low.empty()) // 4
    {
        data[i++] = low.front();
        low.pop();
    }
    while(!high.empty())
    {
        data[i++] = high.front();
        high.pop();
    }
}
1. A couple of queues are used to temporary store the data while processing them.
2. Fill the queues with the data coming from the input collection.
3. Compare the data on the two queues, rearranging them in the original container.
4. Ensure all the possible elements left in the temporary queues are copied back to the input data.

Full code is on github. As bonus you will also find there a simple xUnit test for GoogleTest.

Go to the full post

Insertion sort

It's a simple sorting algorithm that, even if asymptotically expensive, O(N**2), it results to be cheap for small data set.

Its idea is comparing each element starting from the second up to the last one with its predecessor. While we found smaller items on its left, move those ones to the right, to make room to it.

Here is my C++ implementation:
void insertionSort(std::vector<int>& data)
{
    for(unsigned i = 1; i < data.size(); ++i) // 1
    {
        int value = data[i]; // 2
        int j = i - 1; // 3
        while(j >= 0 && data[j] > value)
        {
            data[j+1] = data[j]; // 4
            --j;
        }
        data[j+1] = value; // 5
    }
}
1. Loop on all the elements after the first one.
2. Cache the current element.
3. Loop backward on the elements on the left of the current one until we found something smaller, or there is nothing more to check.
4. Make room to the current element.
5. Place the element in order.

Full code is on github. As bonus you will find there also a basic GoogleTest test.

Go to the full post