Algorithms — devising an efficient algorithm

Algorithms — devising an efficient algorithm

*Write a function* that is given an array of names and that removes duplicate names and keeps the remaining names in the order in which they first appeared. (These are customers in the order in which they ordered products from us, and we want a list of them in order of seniority. If Hal Bob Hal Al Al Al were the names, then the array should be changed to Hal Bob Al since those are the 3 different customers, and Hal ordered earlier than Bob ever ordered etc.)

Your function must be infinitely better than O(n2)
Suggestions: ideas that might be useful — binary search, mergesort, structured data, sort, …
I’ll be glad to discuss your algorithm ideas during lab.

// orders[0..n-1] contains the names on orders arranged as they occurred
// post: orders[0..k-1] contains each name once, in the order of first appearance, where k is the return
//requirement — better asymptotic performance than O(n*n)
int cleanCustomerList( string orders[], int n )

Don’t use any library functions (other than rand which was shown in the tutorial).
Make a main program in a separate file to test a small case. I will test your function with a big case (more than 1 million ). Don’t put your main program into the dropbox — just the file with your function.

Tags: