App Usage Pattern Recognition - codepath/compsci_guides GitHub Wiki

Unit 4 Session 1 Advanced (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 structure of the input?

  • A: The input is a list of strings, where each string represents the name of an app used during a particular hour (from hour 0 to hour 23).

• Q: What is the output?

  • A: The output is a tuple containing the longest repeating pattern of app usage (as a list of strings) and how many times the pattern repeats (integer).

• Q: What should the function return if there are multiple patterns with the same number of repeats?

  • A: The function should return the first pattern found.

• Q: Are there any constraints on the input, such as the length of the list?

  • A: It is assumed that the list contains exactly 24 elements, representing a full day's usage.

P-lan

Plan the solution with appropriate visualizations and pseudocode.

General Idea: Use a sliding window approach to find all possible patterns of app usage, then check for repeating patterns. Track the longest repeating pattern found.

1) Initialize variables `max_pattern` to an empty list and `max_repeats` to 0.
2) Iterate over the list `app_logs` with an outer loop starting at index `i`.
   a) Use an inner loop starting at index `i + 1` to define a potential pattern `pattern`.
   b) Calculate the length of `pattern` and initialize `repeat_count` to 1.
   c) Check if `pattern` repeats by sliding through the rest of the list in chunks of `pattern_length`.
      - If `pattern` repeats, increment `repeat_count`.
      - If `pattern` stops repeating, break the loop.
   d) If `repeat_count` is greater than 1 and the total repeated length is within bounds, update `max_pattern` and `max_repeats`.
3) Return `max_pattern` and `max_repeats`.

**⚠️ Common Mistakes**

- Forgetting to check the full length of the repeating pattern and its total occurrences.
- Not correctly handling the case where multiple patterns of the same length are found.

I-mplement

def find_longest_repeating_pattern(app_logs):
    n = len(app_logs)
    max_pattern = []
    max_repeats = 0

    for i in range(n):
        for j in range(i + 1, n):
            pattern = app_logs[i:j]
            pattern_length = len(pattern)
            repeat_count = 1

            # Check if the pattern repeats
            for k in range(j, n, pattern_length):
                if app_logs[k:k + pattern_length] == pattern:
                    repeat_count += 1
                else:
                    break

            # Update the longest pattern if it repeats more than once
            if repeat_count > 1 and repeat_count * pattern_length <= n:
                if pattern_length * repeat_count > max_repeats * len(max_pattern):
                    max_pattern = pattern
                    max_repeats = repeat_count

    return max_pattern, max_repeats