Language Vocabulary Sampling
You are given a stream of conversation in a mysterious language from planet Mars. Approximate the set of word vocabulary in this language.
Problem Statement
You are given a reference to an instance of a class called "WordStream" that has a method called "string GetNextMartianWord()", where Martian is a mysterious language from planet Mars. This method gives you a random word from the Martian language, picked with equal probability, and with replacement (i.e. it could pick the same word more than once). Given N is the maximum number of times that you can sample Martian language by calling this method, and the guarantee that N is at least an order of magnitude larger than the number of possible Martian words, write a pseudocode algorithm to approximate the number of words Martians have in their language.
Note: The signature of your method is:
int ApproximateHowManyMartianWords (WordStream wordStream, int N)
Evaluation
 Completeness of the pseudocode algorithm (25%)
 Correctness of the algorithm, demonstrated by quick manual unit tests (25%)
 What is the time and space complexity in terms of N? (25%)
 Describe how you would change your code to print the most frequently encountered 3letter prefix before returning. (25%)
References
I designed this question
Recommended reading

Circular Linked List Detection
A linked list is given. Write an algorithm that detects whether it's a singly linked list or a circularly linked list.

Graph Cycle Detection
You have a directed connected graph. Write an algorithm that detects any cycle, if one exists, and returns a list of its nodes.

Calculate your Social Graph Klout Score
Write the algorithm that LinkedIn.com uses to tell you how many professionals you have access to.

Reverse the order of the words in a String inplace.
Reverse the order of the words in a String inplace.
 Author
 Amin Ariana
 Published
 January 2010