Small World

Given a list of points in the plane, write a program that outputs each point along with the three other points that are closest to it. These three points ordered by distance.

For example, given a set of points where each line is of the form: ID x-coordinate y-coordinate

1  0.0      0.0
2  10.1     -10.1
3  -12.2    12.2
4  38.3     38.3
5  79.99    179.99

Your program should output:

1 2,3,4
2 1,3,4
3 1,2,4
4 1,2,3
5 4,3,1

This is facebook's smallword puzzle, but I am only asking for a O(n²) solution.



Below is a program that will solve the smallworld puzzle in n-squared time. Notice that this will not be accepted by the facebook robot as it is too slow so don't even bother submitting it (I already tried). If you don't believe me try running it with 10,000 input coordinates.

There is a way to do this in close to linear time, can you figure out how?

#!/usr/bin/env python
import sys
from math import sqrt

class Node:
    def __init__(self,name,x,y):
        self.name =  name
        self.x = x
        self.y = y
        e = Edge(self,self)
        e.distance = 1e1000
        #3 smallest edges, sorted by distance
        self.closest = [e,e,e]

    def __str__(self):
        return str(self.name) + " " + self.closest[0].b.name + "," + self.closest[1].b.name + "," + self.closest[2].b.name

    #O(1) since we keep self.closest limited to 3
    def addNeighbor(self,other):
        """Add other to the closest list, but only if it is
           closer than the farthest one in the list."""
        e = Edge(self,other) # I am always first
        if (e.distance < self.closest[2].distance):
            self.closest.append(e)
            self.closest.sort()
            self.closest = self.closest[:3]
        if (e.distance < other.closest[2].distance):
            e = Edge(other,self) # I am always first
            other.closest.append(e)
            other.closest.sort()
            other.closest = other.closest[:3]


class Edge:
    def __init__(self, a, b):
        self.a = a
        self.b = b
        dx = (a.x - b.x)
        dy = (a.y - b.y)
        self.distance = sqrt(dx*dx + dy*dy)

    def __cmp__(self,other):
        return cmp(self.distance, other.distance)

    def __str__(self):
        return self.a.name + "-" + self.b.name

filename = sys.argv[1]
f=open(filename)
nodes = []

# O(n), where n is the number of nodes (friends)
for l in f:
    items = l.split()
    n = Node(items[0], float(items[1]), float(items[2]))
    nodes.append(n)

# O(n^2)
for i in xrange(0,len(nodes)-1):
    for j in xrange(i+1,len(nodes)):
        nodes[i].addNeighbor(nodes[j])

# O(n)
for n in nodes:
    print n

Nth Smallest Number

Find the nth smallest number in an unsorted array of numbers. Do it in linear time and without using any added memory.


It is easy to come up with a solution to this problem: sort it then return the nth element. The problem is that sorting is O(n log n). The insight comes from knowing how quicksort is implemented and then realizing that it can be modified not to sort all elements but only try to sort those parts of the array that contain the nth element.

One should also ask about the size of n. If n is always a very small or very large (equal to the array size) value then a more straight-forward linear search might be better. The approach shown below works for all values of n and has a linear expected run time.

This algorithm was first published by C.A.R Hoare (quicksort) and appears in Programming Pearls as Problem 11.9.

#!/usr/bin/python
from Numeric import *
from random import *

def split(a):
    """Using a random pivot, order a such that
    a[0..x-1] <= (pivot = a[x]) < a[x+1..]
    Returns x"""
    pivot = randrange(0,len(a))
    a[0],a[pivot] = a[pivot],a[0]
    last = 1;
    for i in range(1,len(a)):
        if (a[i] <= a[0]):
            a[last],a[i] = a[i],a[last]
            last = last + 1
    a[last-1],a[0] = a[0],a[last-1]
    return last - 1

def sortNthElement(a, n, first = 0):
    """Sorts at least the nth element of a[].  That is, the nth
    element of a sorted a[] is placed in the nth position. Other
    elements are also moved in a[]."""
    if (len(a) <= 1):
        return
    mid = split(a)
    if (n < first + mid):
        sortNthElement(a[0:mid],n,first)
    elif (n  > first + mid):
        sortNthElement(a[mid+1:],n,first+mid+1)


def findNthSmallest(a,n):
    """Returns the nth smallest number in a[].
       Effects: modifies the order of numbers in a[]"""
    sortNthElement(a,n)
    return a[n]

#Using a regular array, like a = [0,1,2], will not work because
# slicing (a[0:5]) those creates new copies, but slices of an
# array([]) still refer to the original.

def runTests():
    l = []
    for i in range(0,1000):
        l.append(i)
    a = array(l)
    for i in range(0,1000):
        shuffle(a)
        choice = randrange(0,len(a))
        assert (findNthSmallest(a,choice) == choice)
    #now, with repeats
    l = []
    for i in range(0,1000):
        l.append(i) 
        l.append(i)
    a = array(l)
    for i in range(0,1000):
        shuffle(a)
        choice = randrange(0,len(a))
        assert (findNthSmallest(a,choice) == choice / 2)
    print "Tests OK"

Search in a Sorted List

Implement a function which, given an array of sorted numbers and a number will determine if that number is in the array.


The solution is to implement a binary search algorithm. As Programming Pearls tells us, this is a notoriously difficult simple algorithm to get correct. Much unit testing is needed. In fact, the one I wrote below is probably wrong.

There are two implementations: one is recursive and I am fairly sure that one is correct, and the other is iterative and I can't be sure its really completely correct without a lot of testing.

#include<iostream>
#include<vector>
#include<algorithm>

using namespace std;

bool myBinarySearchHelper(vector<int> & v, int start, int end, int e){
  if (start == end) 
    return (e == v[start]);
  int mid = (end+start)/2;
  if (e <= v[mid])
    return myBinarySearchHelper(v,start,mid,e);
  else 
    return myBinarySearchHelper(v,mid+1,end,e);
}

bool myBinarySearchRecursive(vector<int> & v, int e){
  return myBinarySearchHelper(v, 0 , v.size(), e);
}

bool myBinarySearch(vector<int> & v, int e){
  int start = 0;
  int end = v.size();
  while (start < end){
    int mid = (end+start)/2;
    if (e == v[mid])
      return true;
    if (e < v[mid])
      end = mid;
    else
      start = mid + 1;
  }
  return false;
}

void print(int e){
  cout << e << ' ';
}

int main() {
  vector<int> v;
  v.push_back(1); v.push_back(2); v.push_back(3); 
  v.push_back(4); v.push_back(6); v.push_back(8);
  v.push_back(9); v.push_back(10);
  
  for_each(v.begin(), v.end(), print);
  cout << endl;
  
  for (int i = 3; i< 12; i++){
    if (myBinarySearch(v, i)) 
      cout << i << " is in " << endl;
    else
      cout << i << " is not in" << endl;
  }
  return 0;
  
}

Running Time

Calculate the time T(N) that each of the following recursive functions takes to execute. That is, find the recursive function T(N), for example: T(N) = 3* T(N/2). You do not need to solve the recursive equation.

int foo(int N) {
  if (N == 0)
    return 1;
  else 
    return N * foo(N-1);
}


int bar(int N) {
  if (N == 1)
    return 1;
  for (int i = 1; i < N; i++){
    bar(N-1);
  }
}

int bazo(int N) {
  if (N < 1)
    return 1;
  for (int i = 1; i < N*N; i++){
    for (j = 1; j < i; j++) {
      bazo(N/2);
    }
  }
}

int hard(int N) {
  if (N < 1)
    return 1;
  return (N*hard(N/2))/hard(N-1);
}

Any computer science student shoud be able to calculate hat:

foo(N) = T(N) = T(N-1) = T(N)
bar(N) = T(N) = (N-1)*T(N-1)
bazo(N) = T(N) = N2*O(N2)*T(N/2)
hard(N) = T(N) = T(N/2)+T(N-1)

DNA

As you know, the DNA that guides the development of all living things is just a very long string where each character is one of the four letters: A, G, C, T. Implement a class called DNAString which stores as its member variable one such string, can turn itself into a string, and implements a function called positionOf which takes as input a string and returns the starting position of that substring in the DNA string.


For the positionOf we search from left to right. The inner break means we don't waste time on impossible matches.

public class DNAString {

  /** The gene. I choose to represent it as an array since its is then
     more natural to access random positions and I can change it in
     place without copying the whole thing (Remember: Strings are
     immutable). */
  protected char[] strand;

  public DNAString(int length){
    strand= new char[length];
  }

  public void set(String g){
    for (int i=0; i < g.length(); i++){
      strand[i] = g.charAt(i);
    }
  }

  public String toString(){
    String result = "";
    for (char g : strand){
      result += g;
    }
    return result;
  }

  /** @param s the substring we are looking for.
  Returns the starting position of s in this DNAString or -1 if s is
  not found anywhere in this strand */
  public int positionOf(String s){
    for (int i=0; i < strand.length - s.length(); i++){
      boolean match = true;
      for (int j =0; j< s.length(); j++){
        if (strand[i+j] != s.charAt(j)) {
          match = false;
          break;
        }
      }
      if (match) {
        return i;
      }
    }
    return -1;
  }


  public static void main (String [] args){
    String joeDNA = "AGCTGAAAAAGTCCCCACGATCATCAAGACTTGACTACGCTAGC";
    DNAString joe = new DNAString(joeDNA.length());
    joe.set(joeDNA);
    System.out.println(joe);

    System.out.println("AAGT is first found at position " + joe.positionOf("AAGT"));
    
  }
}

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);
    }
  }
}

Find Duplicate in Linear Time

You are given an array of numbers that contains all numbers from 0 to n, in some random order, except that one number is missing and another number is repeated (thus, there are still n numbers in the array). Find the repeated number in linear time and do not use any other data structure.

The numbers in the array can just be placed in the appropriate place in the array, just use the number as it's own position index. If when you go to place a number i in position i you notice that a[i] already contains i then you know you found the duplicate. If not, place it and use the number that was there as your new index.

#!/usr/bin/python
from Numeric import *

def find(a):
    i = 0
    while True:
        print a
        if (a[i] == i):
            i += 1
            continue
        if (a[a[i]] == a[i]):
            print "Repeat is %d" % a[i]
            return a[i]
        c = a[a[i]]
        a[a[i]] = a[i]
        a[i] = c
        i = c

        
#Test cases
a = array([0,3,2,1,4,4,6])
a = array([0,1,2,3,4,4,6])
a = array([4,4,2,3,0,1,6])
a = array([4,4,0,1,2,3,6])

find(a)

Sorting a Big File

You have a file that contains at most 10^7 positive integers, all distinct, all between 0 and 10^7. You want to sort these numbers but only have about 2 megabytes of RAMs. How do you do it?

Before you read the answer here is a tip: the best answer sorts the file in linear time reading every number into memory only once.

Give up? Since the file contains all distinct integers between 0 and 10,000,000, we can use bits to represent whether every number in this range exists. For this we need only 10^7 bits or 1,250,000 bytes (1.25MB) so it can fit in memory. Here is some pseudocode:

boolean bit[10000000]; 
//An array of bits. I'm assuming a boolean array of size 8
// uses only one byte.
//Set it to 0
for (int i = i; i < n; i++){
  bit[i] = 0;
 }

//read every number from file
f = filestream("filename"); //pseudocode

while (int i << f){
  bit[i] = 1;
 };

//write it out
for (int i = i; i < n; i++){
  if (bit[i] == 1)
    cout << i;
 };

This is a very old question. It appears in Programming Pearls by Jon Bentley, a really fun read!

No Calculators Allowed

Without using a calculator, what is 2 to the 12th power?



This is a quick weed out question to differentiate the tech types from the non-tech people. Every programmer should be able to start reciting: 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048, 4096.