Skip to main content Link Menu Expand (external link) Document Search Copy Copied

Interview Questions

Data structure and algorithm design.

Describe 2 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.

Finally, implement your most efficient approach in the code challenge.

WordCounter

Describe 2 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.

Finally, implement your most efficient approach in the code challenge.

WordTracker

Describe 2 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.

Finally, implement your most efficient approach in the code challenge.

PlacesDatabase

Describe 2 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. You may assume all numbers are unique.

Finally, implement your most efficient approach in the code challenge.

MinMaxPQ

Describe 2 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.

Finally, implement your most efficient approach in the code challenge.

VotingSystem