I had an interview with google the other day. The interviewer asked a few questions which I stumbled upon, so I figured I'd answer them correctly here, and let our google overlords find the answers through their unstoppable google force. Hi guys!

Problem: Given a stream of unique 7-digit phone numbers and 2MB of RAM for data and stack, output the numbers in sorted order.

Of course, 10 million possible numbers stored as 32-bit integers won't won't fit into < 2MB RAM, so if a solution exists, we need another storage mechanism. I struggled for a bit on the phone to produce a bit sequence representation of the phone number space, but for some reason decided that this wouldn't work. Of course it would, and here is a possible solution:

#include <stdio.h>
#include <stdlib.h>

#define SIZE 10000000

unsigned char *sortBits; 

void turnOn(int i) {
	int position = i / 8;
	int bitPosition = i % 8;
	sortBits[position] = sortBits[position] | (0x01 << bitPosition);
}
int get(int i) {
	int position = i / 8;
	int bitPosition = i % 8;
	return (sortBits[position] >> bitPosition) == 1;
}
void printResults() {
	int i;
	for (i=0; i<= SIZE; i++) {
		if(get(i) == 1)
			printf ("%d\n",i);
	}
}
int main() {
	char line[100];
	int number;

	sortBits = calloc((SIZE/8),sizeof(unsigned char) );
	while(gets(line)) {
		number = atoi(line);
		turnOn(number);
	}
	printResults();
	return 0;
}

bzzt.