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.

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”.

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.

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.

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.

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.

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.

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.

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.

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.

Give a worst-case asymptotic analysis for all methods where N is the number of votes and M is the number of candidates.