One hungover morning about a year ago a friend and I were having breakfast at a typically terrible cafe in London, trying to prepare for an interview that afternoon. It was the first time we were interviewing candidates for that company and needed to decide on what questions we were going to ask. Most cafes in the UK have set meals but also let you create your own meal from a selection of standard (bacon, eggs, etc.) and not so standard (coleslaw? tuna???) breakfast items. Inspired by our surroundings we came up with the question:

Given a list of food items with different prices and a maximum budget find all possible meals that could be purchased.

Which is essentially a confusing way of setting up a variation on the subset sum problem. Subsets are sets that can be made from the elements of a parent S. All possible subsets of a set is known as the powerset of that set. For example:

Or in terms of our problem:

So a naive approach for small sets is to generate the powerset and find all subsets that match the criteria.

I’ve been using go a lot lately for my own projects and have so far found the learning curve to be pretty straight forward. Most of the concepts feel very familiar if you’ve come from any imperative, c based language. However, one new concept, and one of go’s major selling points, is its support for concurrency using CSP, or in go terms: go routines and channels.

CSP, or communicating sequential processes, is a concept developed by Tony Hoare to model concurrent actions within applications — i.e. actions that may happen at the same time rather than strictly sequentially. Go implements these ideas by allowing you to execute code in a go routine, which essentially creates a new thread to execute the code. Crucially, go doesn’t use real OS threads, but rather green threads so this ends up being really cheap and allows for thousands of concurrent processes to be created. The other half of go’s CSP implementation are channels, which are queues that can be used to pass data between go routines and the main thread.

To get a better grip on how all this works I wanted to implement some basic concurrency patterns found in the real world. One obvious example is the sometimes confusing experience of ordering coffee at Starbucks. In case, like me, you haven’t been to a Starbucks in a while lets review the process:

• Customer places order with a Barista
• Customer gives Barista their name
• Customer waits for order
• Barista takes order from a list
• Barista makes the drink
• Barista shouts an approximation of a Customer’s name
• Customer collects drink

There are a few details I’m skipping over here like having a separate person serve the customers from the baristas, but this should model the main ordering process well enough.

A good example to consider for disjoint–sets is a friendship group. A circle of friends is a loosely connected set of people who share some connection to each other, but not necessarily every member in the set. For example, Bill and Ted are friends and Bill knows Rufus. Therefore, Bill, Ted and Rufus can all said to be connected. Another set of friends could be Socrates, Plato and Aristotle, but this set is completely unconnected from the first. However, if by some weird time-traveling trick Bill or Ted were to meet one of these historical figures then the two sets would be merged.

The basic principal of a disjoint-set is to use one member of each subset as the representative for that set and then link all members to that item. So in our case Bill (although any member could be chosen) is the representative of the first set of friends. It’s then possible to find out if Ted and Rufus are friends by checking that they’re represented by the same member — in this case Bill. To add new members to the set, e.g. when Bill and Ted become friends with Socrates, all we need to do is update all members to be represented by the same item.

Implementation

The disjoint–set data structure supports three operations:

• MakeSet — creates a new set with a single item, which represents itself.
• Find — returns set that the member belongs to (or the representative of that set).
• Union — merges two subsets.

One simple way of constructing disjoint-sets is to use a linked list and using the head of the list as the representative. Union simply join one list to the other and Find traverses up the list until it reaches the head, which is the set representative. However, this makes Find an O(n) operation.

An alternative approach is to use a tree structure to represent each set where the representative is the root and all members have a direct pointer to that node. Union attaches one root to the other, which is again a constant-time operation. Find traverses up the tree to the set representative, which is an O(h) operation where h is the height of the tree.

I’ll use the tree based approach for this example.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

package disjoint

type DisjointSet struct {
	data   interface{}
	parent *DisjointSet
}

func MakeSet(item interface{}) *DisjointSet {
	return &DisjointSet{data: item}
}

func (s *DisjointSet) Union(s2 *DisjointSet) {
	s.Find().parent = s2.Find()
}

func (s *DisjointSet) Find() *DisjointSet {
	if s.parent != nil {
		return s.parent.Find()
	} else {
		return s
	}
}

A Trie is a tree based data structure that stores keys based on a node’s position in the tree rather than explicitly assigning a key. From the Wikipedia article:

Unlike a binary search tree, no node in the tree stores the key associated with that node; instead, its position in the tree defines the key with which it is associated.

In other words, instead of labeling each node directly the key for a specific node is implied from traversing the tree to its location and keeping track of the nodes along that path.

This example shows a trie made up of the words “A”, “to”, “tea”, “ted”, “ten”, “i”, “in”, and “inn”. None of the nodes are labeled, but we can still search the trie for keys by traversing from the root node along each character in a query string, until we either find a valid node or not. For example, if we search for “ten” we start at the root node, follow the path “t” to “e” to “n”, which ends in a valid node. However, if we search for “tent” then when we get to the “n” node there won’t be a “t” to follow so we know “tent” doesn’t exist in the trie.

Implementation

First, we need to define a Trie type using a struct. This is a recursive type so that each node in a Trie is itself a Trie. The constructor function initialises a Trie with an empty map to contain its child nodes.

1
2
3
4
5
6
7
8
9

type Trie struct {
  terminated bool
  value interface{}
  children map[string]*Trie
}

func NewTrie() *Trie {
  return &Trie{children: map[string]*Trie{}}
}

Adding items to a Trie is simple: recurse through the string, adding new child nodes for each character. If a node already exists it’s skipped over. If all the characters are consumed the terminated flag is flipped to true to signify this node represents the end of a key.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

func (t *Trie) Add(k string) *Trie {
  if len(k) == 0 {
    t.terminated = true
    return t
  }

  head := string(k[0])
  tail := string(k[1:])

  child, ok := t.children[head]

  if !ok {
    child = NewTrie()
    t.children[head] = child
  }

  return child.Add(tail)
}

Note that we’re not storing any data about the key the node represents. That is determined purely from the node’s position within the Trie structure.

I’ve recently started playing around with Go again so I decided to try implementing a few basic data structures to get a better feel for the language. To kick things off I kept it super simple by starting with stacks and queues.

Stacks

A stack is a collection of items that maintains a last in, first out ordering (LIFO) and exposes two operations — push and pop. In other words, popping an item off the stack will return the item that was most recently pushed onto the stack.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

package stack

type Stack struct {
	data interface{}
	top  *Stack
	next *Stack
}

func (s *Stack) Push(v interface{}) {
	n := &Stack{data: v}
	n.next = s.top
	s.top = n
}

func (s *Stack) Pop() interface{} {
	t := s.top
	s.top = t.next
	return t.data
}

There are a few ways to implement a stack, but code above use a linked list to represent the nodes. Each node has a data property, which is used to store the items push onto the stack. They also have next and top properties that are pointers to other nodes in the stack. top is used by the root node to determine which item is currently at the top of the stack. next is used to link each of the nodes to each other so the rest of the items can be promoted to top once their parents have been popped.

To push items on to a stack we need to create a new node with the item’s value, assign its next property to be the node which is currently on top of the stack, and finally make this new node the top. To pop an item from a stack we first store a reference to the current top. We then make its next property the new top and then return its data.