Here’s one that you might run into when being screened for a technical position: the brain teaser. The point here, usually, is not to see if you can solve a riddle. But more to see how your mind works when an unusual problem arises (see it as creative problem solving). I’ll go over some of the types of questions you may encounter and I’ll also give some references for who like this kind of stuff .

The Fermi-question

The answers to these kind of questions are based on estimates and a logical thought-process that accompanies these estimates to derive a valid answer. Often you won’t find the correct answer, but the idea is to get very close. Some of the popular Fermi-questions are: “How many piano tuners are there in the world?” or “How many gas stations are there in the United States of America?”. A bad way to answer these questions is to just give a number and be done with it.

On wikipedia you can find a good example of this: “How many piano tuners are there in Chicago?”

Next to wikipedia, here is another great resource on the subject: Science Olympics. Here you will also find many examples of Fermi-problems. Some neat ones:

- How many golf balls will fit in a suitcase?
- How many hairs are there on a human head?
- If your life earnings were doled out to you by the hour, how much is your time worth per hour?
- People crowd into London until all available open space within the city limits is covered with standing people. How many people would there be?

More information about Fermi problems in general can be found on Wikipedia.

Creative-thinking question

These are actually just weird questions. Again, keep in mind that the purpose of these questions is to see how you approach a problem that is new to you. For instance: “How are m&m’s made?”, “Without looking at specifications, what is the weight of a Boing 747?” “Why are soda cans produced in that shape?” “Why are manhole covers round?”

Some of these questions can be about things that you know. If you know how m&m’s are made, just answer. If you just now looked at you soda can and asked yourself “Why is it made like that?”, you might want to do some thinking. The answer can be simple: They are made like that cause that way they stack easy. The answer can also be scientific: The curves in the can make sure that the build up pressure inside the can doesn’t make the can go boom. If it would be a metal cylinder with the same thickness of steel everywhere, the can probably can’t stand the build up of pressure inside the can.

Mathematical questions

These questions often have a certain way of looking at a problem to find the solution. Typically, with these questions, when someone gives you the answer you go “aaaahhhhh…of course”. A very famous one here is the riddle that John McClane (played by Bruce Willis) and Zeus Carver (Samuel L Jackson) had to solve in Die Hard: With a Vengeance: You have a jug that can contain 5 liters (let’s call it J5) and a jug that can contain 3 liters (J3). Now, you need to get exactly 4 liters  in the 5-liter-jug. Solution (let’s use water, just like in the movie ):

- fill J3 with water

- poor J3 into J5

- fill J3 again with water

- fill J5 to the top (now you added 2 liters, so you have 1 liter in J3)

- empty J5

- fill J5 with the 1 liter from J3

- fill J3

- poor J3 into J5

And now J5 contains 4 liters of water.

Another one: You have 8 billiard balls. They all have exactly the same weight, except for one. You have a weighing scale like this:

You need to find the billiard ball that has a different weight with the least amount of weighings.

Answer: You can find the billiard ball in two weighings.

Put three billiard balls on each side of the scale. If the scale balances to a side, you know in which batch of three the crooked ball is. Now you put one ball of this batch on each side of the scale. If it balances to a side you know which ball is crooked, if it doesn’t, the crooked ball is the remaining one. If in the measurement of 3 versus 3 the scale stays in balance, you just need to measure the remaining two.

This can also be done with 9 billiard balls, here when the scale balances to one side in the first weighing, the crooked ball is in the last batch of three. And you still have to just weigh two of them to find the crooked billiard ball.

As you can see, there are many examples of these kinds of questions. You can spend a lot of time surfing the web searching for these questions.

There are also several books that cover this subject. Often these books also cover other subjects I talked about in these series (algorithms, programming questions,…)

- How would you move Mount Fuji?(William Poundstone)

- Programming Interviews Exposed (John Mongan, Noah Suojanen, Eric Giguère)

- Puzzles for programmers and pros (Dennis Shasha)

- Cracking the coding interview (Gayle Laakmann)

…and probably many more

Let’s have a look at a binary tree. In my implementation of the binary tree, I use a property to keep track of the fact that the node in question is the root node (= the node where the tree begins), the Parent-property. This refers to the node that has the current node as one of it’s children (or leafs). You can of course browse through your entire tree to find the node that’s not referenced by any other node, but that will probably take a lot of checks, especially if you have a big binary tree. Even when it’s a small binary tree I would use this property. It makes it easier to navigate through the tree.

   1: public class BTNode

   2: {

   3:     public BTNode LeftNode { get; set; }

   4:     public BTNode RightNode { get; set; }

   5:     public BTNode Parent { get; set; }

   6:  

   7:     public int value;    

   8:  

   9:     public BTNode(int val)

  10:     {

  11:         this.value = val;

  12:     }

  13:  

  14:     public void AddNode(BTNode newNode)

  15:     {

  16:         newNode.Parent = this;

  17:  

  18:         if (newNode.value >= this.value)

  19:         {

  20:             if (RightNode == null)

  21:             {

  22:                 RightNode = newNode;

  23:             }

  24:             else

  25:             {

  26:                 RightNode.AddNode(newNode);

  27:             }

  28:         }

  29:         else

  30:         {

  31:             if (LeftNode == null)

  32:             {

  33:                 LeftNode = newNode;

  34:             }

  35:             else

  36:             {

  37:                 LeftNode.AddNode(newNode);

  38:             }

  39:         }

  40:     }

  41:  

  42:     public BTNode Search(int srchValue)

  43:     {

  44:         if (srchValue == this.value)

  45:         {

  46:             return this;

  47:         }

  48:  

  49:         if (srchValue >= this.value)

  50:         {

  51:             if (this.RightNode == null)

  52:             {

  53:                 return null;

  54:             }

  55:             else

  56:             {

  57:                 return this.RightNode.Search(srchValue);

  58:             }

  59:         }

  60:         else

  61:         {

  62:             if (this.LeftNode == null)

  63:             {

  64:                 return null;

  65:             }

  66:             else

  67:             {

  68:                 return this.LeftNode.Search(srchValue);

  69:             }

  70:         }

  71:     }

  72:  

  73:     public void Delete()

  74:     {

  75:         //bottom of tree

  76:         if (this.LeftNode == null && this.RightNode == null)

  77:         {

  78:             if (this.Parent.LeftNode.value == this.value)

  79:             {

  80:                 this.Parent.LeftNode = null;

  81:             }

  82:             else

  83:             {

  84:                 this.Parent.RightNode = null;

  85:             }

  86:         }

  87:  

  88:         //Middle of tree - RightNode

  89:         if (this.LeftNode == null && this.RightNode != null)

  90:         {

  91:             if (this.Parent.LeftNode.value == this.value)

  92:             {

  93:                 this.Parent.LeftNode = this.RightNode;

  94:             }

  95:             else

  96:             {

  97:                 this.Parent.RightNode = this.RightNode;

  98:             }

  99:         }

 100:  

 101:         //Middle of tree - LeftNode

 102:         if (this.LeftNode != null && this.RightNode == null)

 103:         {

 104:             if (this.Parent.LeftNode.value == this.value)

 105:             {

 106:                 this.Parent.LeftNode = this.LeftNode;

 107:             }

 108:             else

 109:             {

 110:                 this.Parent.RightNode = this.LeftNode;

 111:             }

 112:         }

 113:  

 114:         if (this.LeftNode != null && this.RightNode != null)

 115:         {

 116:             if (this.Parent == null)

 117:             {

 118:                 throw new ApplicationException("You can not delete the root node!");

 119:             }

 120:  

 121:             if (this.Parent.LeftNode.value == this.value)

 122:             {

 123:                 this.Parent.LeftNode = this.LeftNode;

 124:                 this.LeftNode.RightNode = this.RightNode;

 125:             }

 126:             else

 127:             {

 128:                 this.Parent.RightNode = this.RightNode;

 129:                 this.RightNode.LeftNode = this.LeftNode;

 130:             }

 131:         }

 132:     }

To use it, you instantiate a node and assign new BTNodes to the leaves. Wherever you are in the tree-structure, you’ll find it easy to search for nodes. Keep in mind that the AddNode and Delete only reflect on the current node.

Ever since I graduated I’ve been employed as a .NET consultant. When applying for jobs (whether it’s at a consultancy firm or as a representative of your firm getting interviewed by a client) there is often a technical interview. Next to the fun object-orientation questions we all love so much (explain polymorphism, data abstraction, inheritance, Liskov’s substitution principle,…), there were sometimes these little exercises they used to test your approach to problem solving or to see how you react to a very unfamiliar problem. These questions can take different forms. You’ve got you’re here-is-a-piece-of-code-and-tell-me-what-the-output-is-questions, mathematical problems, writing code,…Even brain-teasers can be a part of the interview. 

In the “writing code” department you can be asked to write well known data structures yourself (e.g.: write your own linked list/binary tree), write an algorithm (sorting algorithm,search algorithm, reversing collections,…). The meaning of this series is to discuss some of these questions, find out where the pitfalls are and see what side-questions might be added to the exercise.

So let’s get to it! As a first exercise, let’s look at an implementation of a linked list.  In the .NET Framework, you can find a linked list in the System.Collections.Generic library.

For our basic implementation we need a Node-class where we can hold the references for the previous and the next item in the list. We’ll immediately keep references to both the next and the previous node as we’ll notice that it might be handy to navigate through the list. This is already a more complex version of a linked list (since the most simplistic version only holds the reference to the next node).

   1: public class Node

   2: {

   3:     private Node prevNode;

   4:     private Node nxtNode;

   5:     private string strValue;

   6:  

   7:     public Node(Node prevNode, Node nxtNode, string stringValue)

   8:     {

   9:         this.prevNode = prevNode;

  10:         this.nxtNode = nxtNode;

  11:         this.strValue = stringValue;

  12:     }

  13:  

  14:     public Node PrevNode

  15:     {

  16:         get { return this.prevNode; }

  17:         set { this.prevNode = value; }

  18:     }

  19:  

  20:     public Node NxtNode

  21:     {

  22:         get { return this.nxtNode; }

  23:         set { this.nxtNode = value; }

  24:     }

  25:  

  26:     public string StringValue

  27:     {

  28:         get { return this.strValue; }

  29:         set { this.strValue = value; }

  30:     }

  31:  

  32:     public void Delete()

  33:     {

  34:         this.prevNode.nxtNode = this.nxtNode;

  35:         this.nxtNode.prevNode = this.prevNode;

  36:     }

  37: }

This is a basic node-class. As a value I chose a string, but of course, that can be anything you want. This node is what we’ll use to create our list. We’ll have a list-object that contains the first node, and of course, since each node points to the next one in the list, the list-object will contain all the methods to navigate through the list.

   1: public class LinkedList

   2: {

   3:     public LinkedList(string stringValue)

   4:     {

   5:         nCurrent = new Node(null, null, stringValue);

   6:         nCurrent.NxtNode = null;

   7:         nCurrent.PrevNode = null;

   8:     }

   9:  

  10:     int iCount = 1;

  11:     int iCurrent = 0;

  12:     Node nCurrent;

  13:  

  14:     public int Count 

  15:     { 

  16:         get{return this.iCount; }

  17:     }

  18:  

  19:     public Node CurrentNode 

  20:     { 

  21:         get{return this.nCurrent;}

  22:     }

  23:  

  24:     public Node CurrentNodeIndex 

  25:     { 

  26:         get{return this.nCurrent;}  

  27:     }

  28:  

  29:     public void AddNode(string strValue)

  30:     {

  31:         if (nCurrent.NxtNode == null)

  32:         {

  33:             nCurrent.NxtNode = nCurrent;

  34:             nCurrent = new Node(nCurrent, null, strValue);

  35:         }

  36:         else

  37:         {

  38:             nCurrent.NxtNode = nCurrent;

  39:             nCurrent = new Node(nCurrent, nCurrent.NxtNode, strValue);

  40:         }

  41:         iCount++;

  42:         iCurrent++;

  43:     }

  44:  

  45:     public void ToNext()

  46:     {

  47:         Node tmpNode = null;

  48:  

  49:         if (nCurrent.NxtNode == null)

  50:         {

  51:             throw new Exception("there is no next node!");

  52:         }

  53:         else

  54:         {

  55:             tmpNode = nCurrent;

  56:             nCurrent = nCurrent.NxtNode;

  57:             nCurrent.PrevNode = tmpNode;

  58:             iCurrent++;

  59:         }

  60:     }

  61:  

  62:     public void ToPrevious()

  63:     {

  64:         Node tmpNode = null;

  65:  

  66:         if (nCurrent.PrevNode == null)

  67:         {

  68:             throw new Exception("there is no previous node!");

  69:         }

  70:         else

  71:         {

  72:             tmpNode = nCurrent;

  73:             nCurrent = nCurrent.PrevNode;

  74:             nCurrent.NxtNode = tmpNode;

  75:             iCurrent--;

  76:         }

  77:     }

  78:  

  79:     public void GoTo(int index)

  80:     {

  81:         while (iCurrent != index)

  82:         {

  83:             if (iCurrent < index)

  84:             {

  85:                 ToNext();

  86:             }

  87:             else if (iCurrent > index)

  88:             {

  89:                 ToPrevious();

  90:             }

  91:         }

  92:     }

  93:  

  94:     public void First()

  95:     {

  96:         while (nCurrent.PrevNode != null)

  97:         {

  98:             ToPrevious();

  99:         }

 100:     }

 101: }

Now you can instantiate the list. The constructor also requires a string value to define your first element in the list. Then you’ll find the methods to navigate through the list. And the nCurrent-property of the Linked List will contain the node where you navigated to.

A possible variation you might get asked is a circular linked list. This means that the last element you add (which points to null) actually should point to the first element in the list. For a full theoretical explanation I refer to wikipedia.