Fibonacci

The Fibonacci series consists of a series of numbers where the next number is calculated by adding the previous two. The first two numbers in the series are 1. That is, the series starts out:

1
1
2
3
5
8
13

Write a function which takes as input an integer x an returns an array of integers filled with fibonacci numbers in order.

First declare the array then fill it with the appropriate numbers by iterating from the smallest to the biggest.

public class Fibonacci {

  public static int[] getSeries(int x){
    int[] result = new int[x];
    result[0]= 1;
    result[1]= 1;
    for (int i=2; i < x; i++){
      result[i] = result[i-1] + result[i-2];
    }
    return result;
  }
  
  public static void main (String [] args){
    int[] fib = Fibonacci.getSeries(20);
    for (int i : fib){
      System.out.println(i);
    }
  }
}

Magic Square

A 3x3 normal magic square is a 3x3 grid where the numbers on each row, each column, and both diagonals all add up to the same number, and the square contains the numbers 1 to 9 exactly. For example, the following is the Lo Shu magic square:

4  9  2
3  5  7
8  1  6

Implement a function which, given a two-dimensional 3 by 3 array of ints returns a boolean that tells us if the given square (represented by the array) is a normal 3 by 3 magic square or not.


All we have to do is check all rows, all cols, and diagonals. A bit tedious but straightforward. Is there a solution that uses significantly fewer lines of code? I can't think of one (in Java).

public class Magic {

  public static boolean check(int[][] a){
    int sum,s;
    sum=0;
    for (int col = 0; col< 3; col++) //first set the sum (15 always?)
      sum += a[0][col];

    //check the next two rows
    s = 0;
    for (int row = 1; row < 3; row++){
      s = 0;
      for (int col = 0; col< 3; col++) 
        s += a[row][col];
      if (s != sum)
        return false;
    }

    //check columns
    for (int col = 0; col< 3; col++) {
      s = 0;
      for (int row = 0; row < 3; row++){
        s += a[row][col];
      }
      if (s != sum)
        return false;
    }

    //check diagonal 1
    s =0;
    for (int row = 0; row < 3; row++){
      s += a[row][row];
    }
    if (s != sum)
      return false;

    //check diagonal 2
    s =0;
    for (int row = 0; row < 3; row++){
      s += a[row][2 - row];
    }
    if (s != sum)
      return false;

    //check that the numbers 1..9 appear
    //We use an array of booleans and mark each one as we find it.
    boolean[] appears = new boolean[9];
    for (int i=0; i < 9; i++){
      appears[i] = false;
    }

    //Check each one
    for (int col = 0; col< 3; col++) {
      for (int row = 0; row < 3; row++){
        int num = a[row][col];
        if (appears[num-1]) //its easy to forget that -1.
          return false; //oops, this number appears twice!
        appears[num-1] = true;
      }
    }

    //I could check here that all the values in appears are true but
    // since there are 9 positions in both appears and a[][], I know
    // that if we get to this point then all the values in appears[]
    // must be true!
    return true;
  }

  public static void main (String[] args){
    int[][] loshu = {{4,9,2},{3,5,7},{8,1,6}};
    System.out.println(Magic.check(loshu));
    int[][] no1 = {{4,9,2},{3,7,5},{8,1,6}};
    System.out.println(Magic.check(no1));
    int[][] no2 = {{4,9,2},{3,3,5},{8,1,6}};
    System.out.println(Magic.check(no2));
  }
  /** From wikipedia: The Lo Shu square (3×3 magic square)

Chinese literature dating from as early as 2800 BC tells the legend of
Lo Shu or "scroll of the river Lo". In ancient China, there was a huge
flood. The people tried to offer some sacrifice to the river god of
one of the flooding rivers, the Lo river, to calm his anger. Then,
there emerged from the water a turtle with a curious figure/pattern on
its shell; there were circular dots of numbers that were arranged in a
three by three nine-grid pattern such that the sum of the numbers in
each row, column and diagonal was the same: 15. This number is also
equal to the number of days in each of the 24 cycles of the Chinese
solar year. This pattern, in a certain way, was used by the people in
controlling the river. */

}
 

2D Cellular Automata

A two-dimensional cellular automata implements the same idea but in a two-dimensional array. The most famous one is Conway's game of life which uses the following rules:

1. Any live cell with fewer than two live neighbours dies, as if by loneliness.


2. Any live cell with more than three live neighbours dies, as if by overcrowding.


3. Any live cell with two or three live neighbours lives, unchanged, to the next generation.


4. Any dead cell with exactly three live neighbours comes to life.

Where the neighbors of a cell are those which immediately surround it. Thus, if you start with

.......
.......
.......
..XXX..
.......
.......

then the next step is

.......
.......
...X...
...X...
...X...
.......

Write a class which implements and displays Conway's game of life. This time, try to make the cells on the edge (border) neighbors of those at the other side, that is, make the space wrap around.


This program is too long to fit on a whiteboard (at least, in Java) but a good programmer should be able to write out the basic functions in a piece of paper, but getting all the details correct (such as the module arithmetic and the update function) will likely require testing. It is a good test of your debugging abilities as well as your matrix manipulation capabilities.

public class TwoDCell {
  private int[][] board;

  /**Creates a square board */
  public TwoDCell(int length){
    board = new int[length][length];
    for (int i = 0; i < board.length; i++)
      for (int j=0; j < board[i].length; j++)
        board[i][j] = 0;
  }

  /** Ugly hack, just for testing. Its a flipper. */
  public void setup(){
    board[4][3] = 1;
    board[4][4] = 1;
    board[4][5] = 1;}

  /** A true modulo function for the board. Negative numbers get
     wrapped around, as well as numbers bigger than the size of the
     board. Only works if n >= -board.length.*/
  private int mod(int n){
    if (n < 0) return board.length + n;
    return n % board.length;
  }

  /** Return the number of neighbors, assumes that x,y are not on the
     border of the board. This works out because I set 0 to be a dead
     cell and 1 to be a live cell...sneaky me.*/
  public int getNumNeighbors(int x, int y){
    return //picture this
      board[mod(x-1)][mod(y-1)] + board[x][mod(y-1)] + board[mod(x+1)][mod(y-1)] + 
      board[mod(x-1)][y]                             + board[mod(x+1)][y] +
      board[mod(x-1)][mod(y+1)] + board[x][mod(y+1)] + board[mod(x+1)][mod(y+1)];
  }
  
  /** Take a step in Conway's Game of Life */
  public void step(){
    int[][] newBoard = new int[board.length][board.length];

    //Apply the rule of Life
    for (int i = 0; i < board.length; i++)
      for (int j=0; j < board[i].length; j++){
        int neighbors = getNumNeighbors(i,j);
        if (board[i][j] == 1) {
          if (neighbors < 2) {
            newBoard[i][j] = 0;}
          else if (neighbors < 4) {
            newBoard[i][j] = 1;}
          else { //5 or more 
            newBoard[i][j] = 0;}}
        else {//dead cell
          if (neighbors == 3) {
            newBoard[i][j] = 1;}
          else 
            newBoard[i][j] = 0;}};

    board = newBoard;
  }

  /**The Obvious visualization */
  public String toString(){
    String result = "";
    for (int i=0; i< board.length; i++){
      for (int j=1; j < board.length; j++){
        if (board[i][j] == 0) 
          result += '.';
        else
          result += 'X';}
      result += '\n';}
    return result;}

  //Unit testing
  public static void main(String[] argc){
    TwoDCell life = new TwoDCell(8);
    life.setup();
    System.out.println(life);
    life.step();
    System.out.println(life);
    life.step();
    System.out.println(life);
  }

Cellular Automata

A one-dimensional cellular automata is an array where each position is either off (.) or on (X). At each time step the contents of each cell are updated using a simple rule such as the following:

* If a cell is off then next time it will be in the same state that the cell to its right is currently at.
* If a cell is on then next time it will be off if both of its neighbors are currently on, otherwise it will stay on.

For example, if you start with

....X

then next time you will have

...XX

and the next two steps will be

..XXX
.XX.X

Write a problem that implements and displays this one dimensional cellular automata rule. You can assume that the first and last positions never change their state.


This problem might be a bit too long to solve on a whiteboard (at least in Java) but you should be able to write it down in one sheet of paper. All we do is create a new row from the old one.

public class OneDCell {
  private char[] row;

  public OneDCell(int length){
    row = new char[length];
    for (int i = 0; i < row.length; i++){
      row[i] = '.';}
    row[row.length-1] = 'X';
  }

  /** Implement Wolfram's rule 110.
   * Did you know: Stephen Wolfram believes
   * the universe is best
   * understood using cellular automata */
  public void step(){
    char[] newRow = new char[row.length];

    //To Do: Generalize this to encode anyone of the 2^8 rules.
    for (int x=1; x < row.length -1; x++){
      if (row[x] == '.'){
        newRow[x] = row[x+1];
      }
      else {
        if (row[x-1] == 'X' && row[x+1] == 'X'){
          newRow[x] = '.';}
        else {
          newRow[x] = 'X';}
      }
    }
    //Set the first and last
    newRow[0] = row[0];
    newRow[row.length-1] = row[row.length-1];
    row = newRow;
  }

  /**The Obvious visualization */
  public String toString(){
    String result = "";
    for (int i=0; i< row.length; i++){
      result += row[i];}
    return result;}

  //Unit testing
  public static void main(String[] argc){
    OneDCell ca = new OneDCell(80);

    //Behold! complexity arises out of simplicity!
    while (true) {
      System.out.println(ca);
      ca.step();}
  }
}

Make a Distribution

Write a function which takes as input a string that consists only of the digits from 0 to 9 and outputs a distribution (like a grade distribution) showing how many times each digit appears in the string. Specifically, the following main

public static void main(String args[]){
    String s = "01223334444566";
    Distribution.doDistribution(s);
  }
}

should produce the following output:

0:*
1:*
2:**
3:***
4:****
5:*
6:**
7:
8:
9:

We have an outer look that iterates over the numbers (chars) 0 to 9 and then we count how many times each one has occurred. Note that while the numbers in the example are in order, the instructions do not make that claim. A good programmer should realize that if the number are, in fact, always in order that we could re-write this program to use only one loop.

public class Distribution{
  public static void doDistribution(String s){
    for (char c = '0'; c <= '9' ; c++){
      int index = 0;
      int count = 0;
      while ((index = s.indexOf(c,index)) != -1){
        count++;
        index++;
      }
      System.out.print(c + ":");
      for (;count > 0; count--){
        System.out.print("*");
      }
      System.out.println();
    }
  }
  
  public static void main(String args[]){
    String s = "01223334444566";
    Distribution.doDistribution(s);
  }
}

Limit Instances

Implement a class that limits the number of instances of itself to 4.


The answer will depend on the programming language. In fact, this might be technically impossible in some languages. However, in C++, Java, C#, and most others the basic idea is to use a static (class) variable to keep track of the number of instances and then write a constructor that refuses to work.

public class stooge{

  public static int num = 0; 

  public void stooge( )
  {
    if (num < 4)
    {
      super( );
      num++;
    }
    else {
      throw new Exception("ERROR: too many instances");
    }
  }

}

Bigger than N

Write a function which, given an array and a number n, returns an array of all the numbers in the original array that are bigger than n.


Just search the array linearly and find all the elements that are bigger than n. The one tricky part is that you need to save these in an array and, depending on the language/libraries you are using, you might need to declare the size of the array first. Here I decided to first count the number of items bigger than n, then declare the array, then populate. This program must go over the array twice but only uses as much memory as needed.

A better solution would use an extensible array (ArrayList in Java).

public class BiggerThanN {
  /** @param a an array of integers of length > 0
      @param n
      Returns an array of all a[i] for which a[i] > n.*/
  public static int[] biggerThanN(int[] a, int n){
    //I don't know how many items are bigger than n so I must
    //first count them so I can then create an array of the correct
    //size
    int count = 0;
    for (int i =0; i < a.length; i++){
      if (a[i] > n) {
        count++;}
    }
    int result[] = new int[count];
    int j = 0;
    for (int i =0; i < a.length; i++){
      if (a[i] > n) {
        result[j++] = a[i];}}
    return result;
  }

  public static void printArray(int[] a){
    for (int i=0; i < a.length; i++){
      System.out.println(a[i]);}
  }

  //Do some unit testing
  public static void main (String [] argv){
    int[] a = new int[5];
    a[0] = 1; a[1] = 3; a[2] = 2; a[3] = 7; a[4] = 5;
    printArray(a);
    System.out.println("-");
    printArray(biggerThanN(a,4));
    System.out.println("-");
    printArray(biggerThanN(a,2));
  }
}

Find the Maximum

Write a function which finds the maximum number in an array or numbers.


This problem ensures you know how to implement a loop and search in an array.

public class FindMax {
  /** @param a an array of integers of length > 0
      Returns the maximum integer in a */
  public static int findMax(int[] a){
    int theMax = a[0];
    for (int i =0; i < a.length; i++){
      if (a[i] > theMax) {
        theMax = a[i];}
    }
    return theMax;
  }

  //Do some unit testing
  public static void main (String [] argv){
    int[] a = new int[5];
    a[0] = 1; a[1] = 3; a[2] = 2; a[3] = 7; a[4] = 5;
    System.out.println(findMax(a));
  }
}

Reverse Array

Write a function which reverses the contents of an array in place.


Just swap the first one with the last one, then the second one with the next to last one, and so on. If there are an even number of elements then we swap the last two, if odd then we end up swapping the last (middle) element with itself, which is OK.

public class Reverse {

  public static void swap(int[] a, int x, int y){
  int t = a[x];
  a[x] = a[y];
  a[y] = t;
}

  /** Reverses the order of the elements in a, regardless of the size of a. */
  public static void reverseArray(int[] a){
    //the -1 is tricky
    for (int i=0; i<(a.length-1)/2; i++){
      Reverse.swap(a,i,a.length - 1 -i);
    }
  }

  //Unit testing
  public static void main (String [] argv){
    int[] a = new int[9];
    //Should test with odd and even.
    for (int i=0; i < a.length; i++){
      a[i] = i*i;}
    for (int i=0; i < a.length; i++){
      System.out.print(a[i] + " ");}
    System.out.println("");
    Reverse.reverseArray(a);
    for (int i=0; i < a.length; i++){
      System.out.print(a[i] + " ");}
    System.out.println(""); }
}

Read a File

Write a program that reads and properly parses a file called "people.txt" which contains the name of the person followed by his age and then his height in feet. A sample file looks like:

Mario 34 4.5
Donkey Kong 15 5.7
Luigi 38 5.8
Princess Peach Toadstoll 25 5.2

A very easy question. You need to remember how to loop to read a file and, more importantly, that this data should go into a record or class. Since each row represents a person, a good programmer should initially default to thinking about each row as an object with various attributes.

The only tricky part in this example is the fact that a person's name could be any number of words. Thus, we have to look for the first integer before we can declare that the complete name has been found.

import java.io.*;
import java.util.Scanner;

public class Person {
  private String name;
  private int age;
  private double height;

  public Person (Scanner in){
    name = "";
    while (!in.hasNextInt()){
      name += in.next() + " ";
    }
    age = in.nextInt();
    height = in.nextDouble();
    in.nextLine();
  }

  public String toString(){
    return name + " " + age + " " + height;
  }

  public static void main (String[] args){
    String filename = "people.txt";
    try {
      Scanner in = new Scanner(new File(filename));
      while (in.hasNextLine()){
        Person p = new Person(in);
        System.out.println(p);
      }
    } catch (FileNotFoundException e){
      System.out.println("Sorry, could not find file " + e);
    }
  }
}