Unit 4 Session 1 Advanced (Click for link to problem statements)
Understand what the interviewer is asking for by using test cases and questions about the problem.
Q: What is the structure of the input?
Q: What is the output?
Q: What should the function return if there are multiple patterns of the same length?
Q: Are there any constraints on the input, such as the length of the list?
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.
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