CareerCup

Treat a birthdate as a string formatted as "yyyymmdd". for example, "Feb 9th, 1980" is converted into a string of "19800209". Now use this string as the key of each family member. Keys are compared according to the following lexicographic order. 0<1<2<3...<9. In-order traversal suffices to print out the names from oldest to youngest.

Use a linked list.
Node - Name + Date of Birth (Just for printing) + Num of days from 1900

you can store use birthdates formatted as (year, month, day) as keys to element in the list of family members.
Now first sort the list based on day, then sort the list based on month and then sort the list based on year.

You would have all birthdates in sorted order.

The sort would take O(3nlogn). You can optimize this using bucket sort. You can do it in O(n) but with bucket space

how about inserting into the linked list in a sorted manner based on the date.

class Member {

String name;
Date birthDate;

public:

Member(String name, Date birthDate)
{/* .... */}
}

class Family {
public:
void addMember(Member familyMember)
{ /* .. add it to a max heap based on birthDate .. */ }
void printNames()
{
while(heap ! Empty)
print(heap->remove());
}
}

Order analysis:
===============
adding takes O(nlogn). n is the number of members. each addition takes logn to re-heapify.
printing takes O(n). therefore approximately O(nlogn)

A date class already exists in some form or another in a library. Hence, create a composition containing a person's family dates. The aggregation will use a Binary Search Tree to maintain order. Each date has a hash value that you can use for ordering. Insertion is O(logn). Traversal is O(n).

Testing:

case 1:Insert three duplicate dates.
case 2:Insert 3 sequential dates from low-high.
case 3:Insert 3 sequential dates from high-low.
case 4:Insert 3 dates out of order.

Along with the idea of BST - I guess a TRIE structure will be faster. Since the length of the input is fixed to 8 digits always, an insertion, lookup is O(1). We can print all elements in non decreasing order in O(n) time. Care should be taken to maintain the TRIE with year digits first, month digits next and then date digits...

I agree with BST.

insertion O(logn), lookup O(logn)
print will be reverse inorder traversal (right, root, left) O(n)

linked list insertion O(n) lookup O(n)
print iteration O(n)

Instead of manipulating a BST directly, wrap it in a HashMap to get O(1) access on top.

public class DateOrder
{
System.Collections.Hashtable Dates = new System.Collections.Hashtable();
public void InsertDate(DateTime date)
{
DateTime firstDate = new DateTime(1900,1,1);
TimeSpan difference = date.Subtract(firstDate);
Dates[difference.Days ] = date;
}

public void Print()
{
foreach(DateTime date in Dates.Values )
{
if (! date.Equals(null))
{
Console.WriteLine(date.ToShortDateString());
}
}
}
}

Base on the question, we are allowed to use class. So we can define a comparable function for sort function in STL. This function return bool value by comparing the value of year, month and date.
Test cases:
1. Y2k year
2. Months: 12 months
3. Dates: Jan - 31, Feb -28(for leap year 29), ...,
4. All independant methods in Date class(if we write our own)
5. all independant methods in Person(constructor, ...)
6. all independant methods in Familty(constructor, ...)
7. all dependant methods in Person(getBirthDate...)
8. all dependant methods in Familty(comp, sort, printout...)

i believe we sould count on the finite numbers of years that are possible.
set the oldest one to be 120 years old. than if we are on 2006, than the oldest one was born on 1886 (= START) and if i am going to live another 60 years than the youngest one in my family (that i am going to know) might be borned on (2006+60=2066= END). therefore, i find the most easy way to implement that matter is with an array and link list (in the same manner of hash table connected to link list)
the array index will be arr[START]..arr[END]

ADD operation:
add the date of the person to the arr[year] entry.
if he is the only person in that year add a node to the year.
if he is not the only person, add him to the right place from older to younger.

the performance should be a hash table performance ~ O(1) add, O(1) get element=> 0(n) get all elements
Tests:
test ADD:
1. add to year smaller than START
2. add to year in the future - later than current day
3. add a not valid date, like feb. 30
4. add 2 dates that are equal
5. add a valid date

test getALL:
1. call getAll and compare to your input

//there will be an integer used to sort the BST and a string used to print.
class Node{
int bday; //integer value used for sorting BST
Node* left;
Node* right;
Char* strBday; // entered as mm/dd/yyyy

// birthday will be entered in form mm/dd/yyyy this function will convert the string to an integer value that will be used to insert into the the familyTree
int convert(char* strBday);
}

class familyTree{

Node* head;
void print();
void insert(Node* person);
void remove(Node* person);
}

BST`s idea is best.. trie wont be useful here as it is a good data structure for searching and not for sorting...