Frequent Co working Spaces - codepath/compsci_guides GitHub Wiki

Unit 4 Session 2 Standard (Click for link to problem statements)

U-nderstand

Understand what the interviewer is asking for by using test cases and questions about the problem.

• Q: What is the goal of the problem?
  • A: The goal is to determine which co-working space(s) were visited most frequently over the past month.
• Q: What are the inputs?
  • A: The input is a list of strings, where each string represents the name of a co-working space visited.
• Q: What are the outputs?
  • A: The output is a list of the most frequently visited co-working space(s). If there is a tie, return all tied spaces.
• Q: How should ties be handled?
  • A: If multiple spaces have the same highest frequency, return all of them.
• Q: Are there any assumptions about the input?
  • A: The input list can contain repeated strings representing multiple visits to the same space.

P-lan

Plan the solution with appropriate visualizations and pseudocode.

General Idea: Use a dictionary to count the frequency of visits to each co-working space. Then, identify the maximum frequency and collect all spaces that have this frequency.

1) Initialize an empty dictionary `frequency_map` to store the frequency of each space.
2) Iterate through the `visits` list:
   a) For each space, increment its count in `frequency_map`.
3) Identify the maximum visit count `max_visits` from the dictionary.
4) Initialize an empty list `most_frequent` to store the spaces with the maximum frequency.
5) Iterate through `frequency_map`:
   a) Add each space to `most_frequent` if its count equals `max_visits`.
6) Return the `most_frequent` list.

**⚠️ Common Mistakes**

- Forgetting to account for ties, resulting in only one space being returned when multiple should be.
- Not correctly initializing or updating the frequency dictionary.
- Assuming the input list is always non-empty.

I-mplement

def most_frequent_spaces(visits):
    frequency_map = {}

    for space in visits:
        if space in frequency_map:
            frequency_map[space] += 1
        else:
            frequency_map[space] = 1

    max_visits = 0
    most_frequent = []

    for space, count in frequency_map.items():
        if count > max_visits:
            max_visits = count
            most_frequent = [space]
        elif count == max_visits:
            most_frequent.append(space)

    return most_frequent

Example Usage:

visits = ["WeWork", "Regus", "Spaces", "WeWork", "Regus", "WeWork"]
print(most_frequent_spaces(visits))  
# Output: ['WeWork']

visits_2 = ["IndieDesk", "Spaces", "IndieDesk", "WeWork", "Spaces", "IndieDesk", "WeWork"]
print(most_frequent_spaces(visits_2))  
# Output: ['IndieDesk']

visits_3 = ["Hub", "Regus", "WeWork", "Hub", "WeWork", "Regus", "Hub", "Regus"]
print(most_frequent_spaces(visits_3))  
# Output: ['Hub', 'Regus']