Algorithm: The Fibonacci Sequence

Problem

Implement a function that returns the Fibonnaci number for a given integer input.

Analysis

The Fibonacci sequence is the recurrence defined as

$$f(n) = f(n - 1) + f(n - 2)$$ $$\text{where }f(0) = 0\text{ and }f(1) = 1$$

Or in simpler terms, it's the sequence of numbers starting with 0 and 1 that is constructed by adding the previous 2 numbers together. Here are numbers 0 through 15:

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, ...

Algorithm: Implement a queue using 2 stacks

Problem

Implement a queue using two stacks.

Analysis

A queue can actually be implemented using a single stack, this method makes use of recursion however which makes uses another stack of sorts, the call stack. This method involves popping each item off the queue and then recursively calling itself until the last element is found, on the way back down the call stack we push the items back on to the stack.

queuepop()
  value ← stack.pop()
  if stack is empty
    return value
  else
    result ← queuepop()
    stack.push(value)
    return result

This isn't very efficient though considering that the pop function is \(O(n)\), we can do better.

So how can we make use of the second stack to better the running time of the algorithm? Think about what a stack and a queue actually is, if we have a stack and reverse it, it will be in the order in which a queue would serve it up.

Algorithm: Reverse a string

Problem

Reverse a string in the most efficient way possible. For example an input of "abc123" will result in the output "321cba".

Analysis

This is a very common interview question, it tests whether a candidate understands how string concatenation and immutability works. A simple algorithm that does the job loops through each character and constructs a string in reverse order.

function reverse (text)
  define result ← ""
  foreach character c in text
    result ← c + result
  return result

The above algorithm is not very efficient though. This is because strings are immutable which means they cannot be modified after they are created. The algorithm creates a new string every iteration which takes worst case \(O(n)\), making the algorithm \(O(n^2)\).

The string can be reversed in \(O(n)\) time with a couple of different methods: using StringBuilder to construct the string as above, or by converting the string to a character array and back.

Algorithm: Integer division without the division operator (/)

Problem

Implement a function that performs integer division on two integers without the use of the division / operator. For example for the input of 10 and 4 should result in the output of 2.

Analysis

If you have not thought about this problem before you may be a little taken aback. It's actually a fairly simple problem, think about what division actually does, it counts how much of a certain number (the divisor) makes up another number (the dividend). One way we could do this using just the minus - operator is to count how many times you can subject the divisor from the dividend before 0 is reached.

Algorithm: All permutations of a set

Problem

Implement a function that gets all possible permutations (or orderings) of the characters in a string. For example for the input string "abc", the output will be "abc", "acb", "bac", "bca", "cab" and "cba".

Analysis

This problem is very similar to all combinations of a set, though the actual computing of the values will be quite different. Let's start by defining the inputs and outputs.

ArrayList<String> getPermutations(String characters);

Now let's look at how this problem is naturally solved. When I write down a set of permutations by hand, I tend to start with the first letter (a), and then find all permutations without that letter in it. So for "abc" I would write:

a bc
a cb
b ac
b ca
c ab
c ba

Algorithm: All combinations of a set

Problem

Implement a function that gets all possible combinations (or subsets) of the characters in a string with length of at least one. For example for the input string "abc", the output will be "a", "b", "c", "ab", "ac", "bc" and "abc".

Analysis

Firstly we will define our method signature. It's fairly simple as it's described in the problem, the input is a String and the output is a list of Strings

ArrayList<String> getCombinations(String characters);