Facebook Puzzles Rock!

If you want some really good programming challenges go to the facebook puzzles page. These are really neat because you can submit the answer and their email robot will automatically tell you if it is good. So far I've only solved usrbincrash and smallworld. A very evil person also described the gattaca puzzle to me and I've been trying to figure out how to solve it ever since.

From what I've seen these puzzles the very nice characteristic that it is rather easy to come up with a solution. However, that solution will run in exponential time and, thus, will not be accepted by the robot. The solutions they are looking for generally run in quadratic time. Finding these solutions is much, much harder.

If you are confronted with questions like these in an interview, the best strategy is to start by solving them using the obvious-but-slow method. Then, once that works, start to think about how to solve them faster. Sometimes this requires completely re-writing your algorithm, often you will need an aha! moment (wish there was a way to work up to those!). Other times it seems one can gradually get to the solution by adding small improvements.

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"

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!