Unit 7 Session 2 (Click for link to problem statements)
Understand what the interviewer is asking for by using test cases and questions about the problem.
- Established a set (2-3) of test cases to verify their own solution later.
- Established a set (1-2) of edge cases to verify their solution handles complexities.
- Have fully understood the problem and have no clarifying questions.
- Have you verified any Time/Space Constraints for this problem?
HAPPY CASE
Input: [1, 2, 2, 3, 3, 3, 4]
Output: {1: 1, 2: 2, 3: 3, 4: 1}
Explanation: The frequencies of each element are returned.
EDGE CASE
Input: []
Output: {}
Explanation: An empty array results in an empty frequency dictionary.
Match what this problem looks like to known categories of problems, e.g. Linked List or Dynamic Programming, and strategies or patterns in those categories.
This problem requires an efficient way to count the occurrences of each element in a sorted list:
Plan the solution with appropriate visualizations and pseudocode.
General Idea: Use a modified binary search to find the first and last index of each unique element and then calculate the difference to get the count.
1) Use a helper function to perform binary search to find the first occurrence of each element.
2) Use another helper function to find the last occurrence.
3) The difference between the last and first index, plus one, gives the count of the element.
4) Iterate over the array and apply the above steps to each unique element.
⚠️ Common Mistakes
Implement the code to solve the algorithm.
def find_first(nums, target):
lo, hi = 0, len(nums) - 1
while lo <= hi:
mid = (lo + hi) // 2
if nums[mid] < target:
lo = mid + 1
elif nums[mid] > target or (mid > 0 and nums[mid-1] == target):
hi = mid - 1
else:
return mid
return -1
def find_last(nums, target):
lo, hi = 0, len(nums) - 1
while lo <= hi:
mid = (lo + hi) // 2
if nums[mid] > target:
hi = mid - 1
elif nums[mid] < target or (mid < len(nums) - 1 and nums[mid+1] == target):
lo = mid + 1
else:
return mid
return -1
def find_frequencies(nums):
frequencies = {}
i = 0
while i < len(nums):
if nums[i] in frequencies:
i += 1
continue
first = find_first(nums, nums[i])
last = find_last(nums, nums[i])
frequencies[nums[i]] = last - first + 1
i = last + 1
return frequencies
Review the code by running specific example(s) and recording values (watchlist) of your code's variables along the way.
Evaluate the performance of your algorithm and state any strong/weak or future potential work.
O(n log n)
in the worst case when each element is found using binary search.O(1)
for space, not considering the output dictionary.