Midterm

Individual interview questions.

Describe 3 approaches to design a data type that can:

1. Add words.
2. Return a list of all the unique words in alphabetical order.
3. Return the number of times a given word has been added.

For your most efficient approach, give a worst-case asymptotic analysis for all methods where N is the total number of words. If helpful, you can choose your own variable to describe the number of unique words.

Describe 3 approaches to design a data type that can:

1. Add “observed” words.
2. Add “known” words.
3. Return how many “observed” words are present in “known”.

For your most efficient approach, give a worst-case asymptotic analysis for all methods where N is the number of “observed” words and M is the number of “known” words.

Describe 3 approaches to design a data type that can:

1. Add user reviews, where a user review has a name, a date, and a rating.
2. Return the reviews that fall between a given start and end date range.
3. Return the reviews by a given name.

For your most efficient approach, give a worst-case asymptotic analysis for all methods where N is the total number of reviews and M is the number of reviews returned by the date range query.

Describe 3 approaches to design a data type that can:

1. Add numbers.
2. Return the value that is closest to the median of all added values.
3. Remove the value that is closest to the median of all added values.

For your most efficient approach, give a worst-case asymptotic analysis for all methods where N is the size of the data type.

Describe 3 approaches to design a data type that can:

1. Add places, where a place consists of an (x, y) coordinate pair.
2. Return the closest place to a given x coordinate.
3. Return the closest place to a given y coordinate.

For your most efficient approach, give a worst-case asymptotic analysis for all methods where N is the size of the data type.

Describe 3 approaches to design a data type that can:

1. Add numbers.
2. Remove the minimum number.
3. Remove the maximum number.

For your most efficient approach, give a worst-case asymptotic analysis for all methods where N is the size of the data type.

Describe 3 approaches to design a data type that can:

1. Add an element to the front (index 0), which increases the index of every other element.
2. Return the element at index i.
3. Promote the element at index i to index 0.

For your most efficient approach, give a worst-case asymptotic analysis for all methods where N is the size of the data type.

Describe 3 approaches to design a data type that can:

1. Add words.
2. Return the most frequent word.
3. Return the most frequent word of given length k.

For your most efficient approach, give a worst-case asymptotic analysis for all methods where N is the size of the data type.

Describe 3 approaches to design a data type that can:

1. Add a post written by a given user.
2. Undo the last post written by a given user.
3. Return a list of all posts written by a given user in the order that they were added.

For your most efficient approach, give a worst-case asymptotic analysis for all methods where N is the number of posts and M is the number of users.

Describe 3 approaches to design a data type that can:

1. Cast a vote for a candidate.
2. Return the number of votes for a given candidate.
3. Return the candidate with the greatest number of votes.

For your most efficient approach, give a worst-case asymptotic analysis for all methods where N is the number of votes and M is the number of candidates.