Guida a Strategia per colloqui di programmazione · 5/6
Per ora questo capitolo è disponibile solo in inglese.
The problems in this chapter were written for this guide to drill the patterns. For each one, first run through the procedure from the earlier chapter on your own (clarify, examples, brute force, optimize) and only then read the solution. Afterwards, cover the code and write it again from scratch; that is where most of the learning happens.
Daily income and spending are given as an integer array amounts (it may contain negatives). Count the contiguous ranges of days whose total is exactly k.
Example: with amounts = [1, 2, -1, 2, 1] and k = 3, the ranges are [1, 2], [2, -1, 2] and [2, 1], so the answer is 3.
Approach: Negative values break the sliding window. Let p be the running prefix sum. A range sums to k exactly when p[j] - p[i] = k, so the number of ranges ending here equals how many earlier prefix sums equal the current prefix minus k. Count prefix sums in a hash map. The key detail is seeding the map with 0 once, which represents the empty prefix.
from collections import defaultdict
def count_sum_k(amounts: list[int], k: int) -> int:
seen = defaultdict(int)
seen[0] = 1 # the state before adding anything
prefix = count = 0
for x in amounts:
prefix += x
count += seen[prefix - k]
seen[prefix] += 1
return count
print(count_sum_k([1, 2, -1, 2, 1], 3)) # 3
print(count_sum_k([0, 0], 0)) # 3Complexity: O(n) time, O(n) space.
Given an integer array nums sorted in ascending order, count the pairs i < j with nums[i] + nums[j] <= target.
Example: with nums = [1, 2, 3, 4, 6] and target = 6, the pairs are (1, 2), (1, 3), (1, 4), (2, 3) and (2, 4), so the answer is 5.
Approach: Put a pointer at each end. If nums[lo] + nums[hi] <= target, every element from lo + 1 through hi can pair with lo, so count hi - lo pairs at once and advance lo. Otherwise, move hi down.
def count_pairs_at_most(nums: list[int], target: int) -> int:
lo, hi = 0, len(nums) - 1
count = 0
while lo < hi:
if nums[lo] + nums[hi] <= target:
count += hi - lo
lo += 1
else:
hi -= 1
return count
print(count_pairs_at_most([1, 2, 3, 4, 6], 6)) # 5
print(count_pairs_at_most([5, 5, 5], 9)) # 0Complexity: O(n) time (O(n log n) if you have to sort first), O(1) space.
An access log is given as an array of user IDs, log. Find the length of the longest contiguous range that contains at most k distinct IDs.
Example: with log = ["a", "b", "a", "c", "c", "c"] and k = 2, the answer is 4, from ["a", "c", "c", "c"].
Approach: Keep a count per ID for the current window in a hash map. After adding one ID on the right, if there are more than k distinct IDs, remove from the left until there are not, deleting any ID whose count drops to 0. The size of the map is then the number of distinct IDs.
from collections import Counter
def longest_at_most_k_distinct(log: list[str], k: int) -> int:
counts: Counter[str] = Counter()
left = best = 0
for right, user in enumerate(log):
counts[user] += 1
while len(counts) > k:
counts[log[left]] -= 1
if counts[log[left]] == 0:
del counts[log[left]]
left += 1
best = max(best, right - left + 1)
return best
print(longest_at_most_k_distinct(["a", "b", "a", "c", "c", "c"], 2)) # 4
print(longest_at_most_k_distinct(["x", "y"], 0)) # 0Complexity: O(n) time, O(k) space.
Given an array of event IDs, return the earliest ID that appears exactly once in the whole array, or None if there is none.
Example: for ["k", "m", "k", "p", "m"] the answer is "p".
Approach: Count occurrences in a first pass, then scan again in the original order for the first value with count 1. Two passes are still O(n).
from collections import Counter
def first_unique(events: list[str]) -> str | None:
counts = Counter(events)
for event in events:
if counts[event] == 1:
return event
return None
print(first_unique(["k", "m", "k", "p", "m"])) # p
print(first_unique(["k", "k"])) # NoneGiven a sorted array nums, count the occurrences of x in O(log n) time.
Approach: The count is the difference between the first position holding a value at least x and the first position holding a value greater than x. The standard bisect module gives both directly. If the interviewer asks you to implement it yourself, write a lower_bound like the one below.
from bisect import bisect_left, bisect_right
def lower_bound(nums: list[int], x: int) -> int:
lo, hi = 0, len(nums) # the answer lies in [lo, hi]
while lo < hi:
mid = (lo + hi) // 2
if nums[mid] < x:
lo = mid + 1
else:
hi = mid
return lo
nums = [1, 2, 2, 2, 5, 7]
print(bisect_right(nums, 2) - bisect_left(nums, 2)) # 3
print(lower_bound(nums, 2), lower_bound(nums, 6)) # 1 5The five problems drill prefix sums, two pointers, variable-size sliding windows, counting and binary search. Rather than memorizing solutions, check that you can say why you picked a pattern: "negatives rule out a window", "the data is sorted, so close in from both ends". Re-solving the same problems in another language is also a good way to review.
0 commenti
Accedi · Accedi per lasciare un commento.