Consider how you might implement an address book, where you store the name, emai
ID: 3828838 • Letter: C
Question
Consider how you might implement an address book, where you store the name, email, phone number, and other information about your friends. For each question below, justify your answer based on what common operations (eg. finding someone by name, etc.) you would expect, and why your selected data structure and/or algorithm provides a good tradeoff between runtime complexity and memory use. Note that some questions may require nested data structures (eg. a Map where the values are Sets).
What data structure would you use for the overall address book to store Person classes? Justify your answer.
What data structure(s) and algorithm(s) would you use to check that no two people have the same email address? Justify your answer.
If you want to list your friends with July birthdays in order by date, what data structure(s) and algorithm(s) would you use? Assume there is "birthday" field that contains a Date class that has month and date member variables. State any other assumptions and justify your answer.
If you have to frequently find friends who live in particular cities, what data structure might you use to make this efficient? Assume you have a "city" field for each person. Justify your answer. Hint: think back to the search engine lecture.
Assume you have information about whether your contacts are friends with each other. If you take yourself out of the graph, what data structure(s) and algorithm(s) would you use to determine how many unrelated groups of friends would you have? Justify your answer.
Explanation / Answer
1) Threaded Binary Search Tree or AVL Tree will be a better data structure to store the information mentioned above.
2) Every Node of tree will contain information of a person with PID(person Id) as a search key.
struct node_person
{ int PID;
char name[];
long int phone;
string email;
etc,.......
}
3) for serrching , as it is binary search; will run in O( log n ) time.
4) for finding the extracted info. like list of persons in city="xyz" ; you just have to query the tree by PID and match the queried field as node_person --> city.
5) Inorder traversal will list the records in ascending order.
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.