Tree algorithms in Scala: DFS, BFS and Height of binary tree

Tree:

         3
   5          2
1   4      6

Preorder Traversal

root -> left subtree -> right subtree
3 ->  5 -> 1 -> 4 -> 2 -> 6

def preOrder(node: Node): Unit = {
  if (node != null){
    print(node.value + " ")
    preOrder(node.left)
    preOrder(node.right)
  }
}

def iterativePreOrder(root: Node): Unit = {
  val stack = new mutable.Stack[Node]()
  var node = root
  while (stack.nonEmpty || node != null) {
    if (node != null) {
      print(node.value + " ")
      if (node.right != null) stack.push(node.right)
      node = node.left
    }
    else {
      node = stack.pop()
    }
  }
}

InOrder Traversal

left subtree -> root -> right subtree
1 -> 5 -> 4 -> 3 -> 6 -> 2

def inOrder(node: Node): Unit = {
  if (node != null){
    inOrder(node.left)
    print(node.value + " ")
    inOrder(node.right)
  }
}

def iterativeInOrder(root: Node): Unit = {
  val stack = new mutable.Stack[Node]()
  var node = root
  while (stack.nonEmpty || node != null) {    if (node != null) {      stack.push(node)      node = node.left    }    else {      node = stack.pop()      print(node.value + " ")      node = node.right    }  }
}

PostOrder Traversal

left subtree -> right subtree -> root
1 -> 4 -> 5 -> 6 -> 2 -> 3

def postOrder(node: Node): Unit = {
  if (node != null) {
    postOrder(node.left)
    postOrder(node.right)
    print(node.value + " ")
  }
}

def iterativePostOrder(root: Node): Unit = {
  val stack = new mutable.Stack[Node]()
  var node = root
  var prev: Node = null  while (stack.nonEmpty || node != null) {
    if (node != null) {
      stack.push(node)
      node = node.left
    }
    else {
      node = stack.pop()
      if (node.right != null && prev != node.right) {
        stack.push(node)
        node = node.right
      }
      else {
        print(node.value + " ")
        prev = node
        node = null      }
    }
  }
}

Breadth first search

3 -> 5 -> 2 -> 1 -> 4 -> 6 

def bfs(root: Node): Unit = {
  val q = new mutable.Queue[Node]()
  var node = root

  q.enqueue(node)
  while (q.nonEmpty) {
    node = q.dequeue()
    print(node.value + " ")
    if (node.left != null) q.enqueue(node.left)
    if (node.right != null) q.enqueue(node.right)
  }
}

Height of a binary tree

def height(root: Node): Int = {
  val q = new mutable.Queue[(Node, Int)]()
  var node = root

  q.enqueue((node, 1))
  var max = 1  while (q.nonEmpty) {
    val d = q.dequeue()
    node = d._1

    if (node.left != null) {
      max = d._2 +1      q.enqueue((node.left, max))
    }
    if (node.right != null) {
      max = d._2 +1      q.enqueue((node.right, max))
    }
  }
  max
}

Scala: Pass by name vs pass by value

Scala call by value vs call by name



In scala when you pass by name (using =>) the expression gets evaluated every time it is used.

Passing by name and passing by value will result in the same output if pure functions are used and both evaluations terminate.

Note that in scala the default is passing by value which is more performant. 

REST API

One really useful book about REST API design is 'The REST API Design Rulebook' by and published by O'Reilly. 

One of my favourite bits was in Chapter 2 about resource archetypes. 

Document

A Document is a THING (for want of a better description). 

www.myrestservice.com/names/female/alexandra

Collection

A collection is a server-managed collection of resources. The client can propose additions to the collection. 

From the above examples, collections would be:

www.myrestservice.com/names/ and www.myrestservice.com/names/female/

Store

A store is a client-managed collection of resources. 

For example to store my favourite female names (my user name = polyglotpiglet): 

PUT www.service.com/users/polyglotpiglet/favourites/names/agnes

Controller

A controller resource is like an executable function with inputs and outputs. It is used in REST APIs when you want to do something that doesn't fall naturally into the CRUD operations. 

For example:

www.service.com/users/polyglotpiglet/favourites/names/sendAsEmail

(weird example but hopefully it makes sense).

In this book I thought that the description of controller resources was awesome - it seems to be a common misconception that REST APIs are only appropriate for designing CRUD systems and if you want to do anything complicated it's not possible with REST. This is not my experience. 

Other notes from the book

Some really useful tips about headers (making sure you set the appropriate headers and why it might be useful eg cache control, last modified time, content types etc)

Euclid's Formula for generating Pythagorean Triples

Pythagorean triple

$$a^2 + b^2 = c^2$$

Euclid's formula:

$$ m,n \in N, m > n $$ $$ a = m^2 - n^2, b = 2mn, c = m^2 + n^2$$ $$ => a^2 + b^2 = c^2$$
Trivial proof.

Primitive pythagorean triples are ones that cannot be reduced (think $ k.a^2 + k.b^2 = k.c^2 $). The triple  is primitive if $a$, $b$ and $c$ are coprime (ie they share no common divisors except 1). An example of a primitive pythagorean triple is (3,4,5).

The pythagorean triples generated using Euclid's formula are primitive iff $m$ and $n$ are coprime and $m-n$ is odd.

Clearly this second point is true because if both $m$ and $n$ were even, then all three terms will be even when squared, so $k$ could equal two so the triple would not be primitive.

Similar if they are not coprime, you could obvs divide every term.

Why should you expect failures in your datacenter?

Not only should you expect failures but you should expect FREQUENT failures.

If you can estimate that every server in your data centre will fail once every ten years then that sounds pretty good right?

Failure rate = Once / 10 years = once / 120 months

But... if you have 120 servers then that will mean you should expect a failure every month!

According to this article, in 2010 Facebook was running at least 60,000 servers across its data centres. 

If these each of these 60,000 servers is expected to fail once every 10 years, then at that time Facebook would have expected a server failure about every hour and a half (120 months / 60000 ~= 1.46  hr)

Eeeek. 

Scala Puzzler 1: Overrides in Constructors

Question:

What is printed when the following code is executed?

Answer:

This code will print out 'null'.

This is because  the Person constructor is called before the override, meaning that val name is instantiated before the override is called. The default name value is never set because the compiler is clever enough to know we don't wan stringName to be set to "I dont have a name" so it skips that assignment.

Interestingly... 

If the stringName was declared with the 'lazy keyword' the code would work properly and print 'Alexandra'. This is because a lazy variable is declared as soon as it is needed, which in this case would be when the name class is instantiated.

Spray-can/Akka simple application

Spray?

The spray-can module of spray.io provides a framework with which you can build http servers and clients which easily integrate with your own akka system.

Note that according to the akka roadmap, in future releases of akka, spray will be built in and will be known as akka-http.

The Code

Under the covers

Spray request handling

When you start your spray app, spray generates an HttpListener actor that listens on port 8181 for incoming requests. For each client connection, spray spawns a new HttpServerConnection actor which receives a request from an open connection and passes an HttpEntity message to your listening actor (the first parameter to the Http.Bind method).

Binding

You must call bind from within an actor.

IO(Http) ! Http.Bind(self, interface = "localhost, port=8181")

This threw me for a bit because initially the first parameter I passed to Http.Bind was the actor that is handling my Http requests. However, when you call Http.Bind you send an async message off to trigger the bind, then spray sends a Tcp.Bound message back to the actor from which you called Http.Bind, not the actor that you pass in as the first parameter.

Try it out

curl localhost:8181/ping