Frequenties tellen en groeperen
Gebruik Counter en defaultdict om tekenfrequenties te tellen, anagrammen op gesorteerde sleutel te groeperen en de meest voorkomende top-k-elementen te vinden.
Frequenties tellen en groeperen is een gratis Voorbereiding op programmeerinterviews-les op CoddyKit. Dit is les 3 van 4. Je kunt de volledige les hieronder gratis lezen en daarna in de browser praktisch oefenen met een ingebouwde code-editor en een AI-begeleider die 24/7 beschikbaar is. Deze les maakt deel uit van het leertraject Voorbereiding op programmeerinterviews. Je voortgang wordt gesynchroniseerd op het web en in de CoddyKit-app. De cursus Voorbereiding op programmeerinterviews bevat in totaal 4 lessen.
Frequenties tellen: het kernpatroon
Frequenties tellen is een van de veelzijdigste patronen in technische sollicitatiegesprekken. Door bij te houden hoe vaak elk element in een lijst of tekenreeks voorkomt, kun je vragen over duplicaten, anagrammen, de meest voorkomende elementen en geldige ordeningen in O(n)-tijd beantwoorden — veel beter dan het alternatief van sorteren en scannen in O(n log n).
Counter en defaultdict(int) van Python zijn de standaardhulpmiddelen. Beide maken een koppeling van element naar aantal; Counter ondersteunt daarnaast rekenkundige bewerkingen en most_common.
from collections import Counter
words = ['apple', 'banana', 'apple', 'cherry', 'banana', 'apple']
freq = Counter(words)
print(freq) # Counter({'apple':3,'banana':2,'cherry':1})
print(freq['apple']) # 3
print(freq['grape']) # 0 (not KeyError)
print(freq.most_common(2)) # [('apple',3),('banana',2)]Geldig anagram (LeetCode 242)
LeetCode 242 'Geldig anagram': bepaal of twee tekenreeksen anagrammen van elkaar zijn. Twee tekenreeksen zijn anagrammen als ze dezelfde frequenties van tekens hebben. Vergelijk hun Counter-objecten of sorteer beide tekenreeksen. Counter gebruiken kost O(n), sorteren kost O(n log n). De aanpak met Counter is optimaal en geeft de definitie rechtstreeks weer.
from collections import Counter
def isAnagram(s, t):
return Counter(s) == Counter(t)
# Alternative: manual frequency array for lowercase letters only
def isAnagram_arr(s, t):
if len(s) != len(t):
return False
freq = [0] * 26
for c in s: freq[ord(c) - ord('a')] += 1
for c in t: freq[ord(c) - ord('a')] -= 1
return all(f == 0 for f in freq)
print(isAnagram('anagram', 'nagaram')) # True
print(isAnagram('rat', 'car')) # False
print(isAnagram_arr('listen', 'silent')) # TrueAnagrammen groeperen (LeetCode 49)
LeetCode 49 'Anagrammen groeperen': krijg een lijst met tekenreeksen en groepeer alle anagrammen bij elkaar. Het belangrijkste inzicht: anagrammen hebben dezelfde gesorteerde tekenreeks. Gebruik een defaultdict(list) met als sleutel de gesorteerde tuple van de tekenreeks (tuples zijn hashbaar). Elke groep wordt onder dezelfde sleutel opgebouwd. Tijd: O(n × L log L), waarbij L de maximale lengte van een tekenreeks is.
from collections import defaultdict
def groupAnagrams(strs):
groups = defaultdict(list)
for s in strs:
key = tuple(sorted(s)) # hashable canonical form
groups[key].append(s)
return list(groups.values())
print(groupAnagrams(['eat','tea','tan','ate','nat','bat']))
# [['eat','tea','ate'], ['tan','nat'], ['bat']]
# Alternative key: tuple of 26 character counts (O(L) not O(L log L))
def groupAnagrams_v2(strs):
groups = defaultdict(list)
for s in strs:
key = tuple(ord(c) - ord('a') for c in sorted(s))
groups[tuple(Counter(s)[chr(ord('a')+i)] for i in range(26))].append(s)
return list(groups.values())
K meest voorkomende elementen (LeetCode 347)
LeetCode 347 'K meest voorkomende elementen': geef de k meest voorkomende elementen terug. Een rechtstreekse aanpak kost O(n log n): tel de frequenties, sorteer op aflopende frequentie en neem de eerste k elementen. De optimale aanpak in O(n) gebruikt bucket sort: maak bakken met frequenties als index (1 tot en met n), plaats elk element in de bak voor zijn frequentie en doorloop daarna de bakken van de hoogste naar de laagste frequentie om k elementen te verzamelen.
from collections import Counter
def topKFrequent(nums, k):
freq = Counter(nums)
# Bucket sort by frequency
buckets = [[] for _ in range(len(nums) + 1)]
for num, count in freq.items():
buckets[count].append(num)
result = []
for i in range(len(buckets) - 1, -1, -1):
result.extend(buckets[i])
if len(result) >= k:
return result[:k]
return result
print(topKFrequent([1,1,1,2,2,3], 2)) # [1, 2]
print(topKFrequent([1], 1)) # [1]Tekens op frequentie sorteren (LeetCode 451)
LeetCode 451 'Tekens op frequentie sorteren': herschik een tekenreeks zodat tekens in aflopende volgorde van hun frequentie verschijnen. Tel de frequenties, sorteer de tekens op aflopende frequentie en voeg ze samen. most_common gebruiken is de netste Python-aanpak. Tijd: O(n log n) voor het sorteren van de unieke tekens op frequentie.
from collections import Counter
def frequencySort(s):
freq = Counter(s)
return ''.join(ch * count for ch, count in freq.most_common())
print(frequencySort('tree')) # 'eetr' or 'eert'
print(frequencySort('cccaaa')) # 'cccaaa' or 'aaaccc'
print(frequencySort('Aabb')) # 'bbAa' or 'bbaA'Takenplanner (LeetCode 621)
LeetCode 621 'Takenplanner': krijg taken en een wachttijd n en bepaal de minimale tijd om alle taken te voltooien. Het belangrijkste inzicht: de taak met de hoogste frequentie bepaalt de structuur. Plaats max_count exemplaren van de meest voorkomende taak met (n) tussenruimtes ertussen. De totale minimumtijd = max((max_count - 1) * (n + 1) + num_tasks_with_max_count, total_tasks). Als er genoeg verschillende taken zijn om de tussenruimtes te vullen, is de inactieve tijd 0.
from collections import Counter
def leastInterval(tasks, n):
freq = Counter(tasks)
max_count = max(freq.values())
# How many tasks share the max frequency
num_max = sum(1 for v in freq.values() if v == max_count)
# Minimum slots needed based on most frequent task
min_slots = (max_count - 1) * (n + 1) + num_max
return max(min_slots, len(tasks))
print(leastInterval(['A','A','A','B','B','B'], 2)) # 8
print(leastInterval(['A','A','A','B','B','B'], 0)) # 6
print(leastInterval(['A','A','A','A','B','B','B','C','C','D'], 2)) # 10Meerderheidsstemming met Counter
LeetCode 169 'Meerderheidselement': vind het element dat meer dan n/2 keer voorkomt. Hoewel Boyer-Moore de optimale oplossing met O(1) ruimte is, lost Counter.most_common(1) dit rechtstreeks op in O(n)-tijd en met O(n) ruimte. Als tijdens een technisch sollicitatiegesprek O(1) ruimte wordt genoemd, presenteer je Boyer-Moore als vervolgvraag; als extra ruimte is toegestaan, is Counter duidelijker.
from collections import Counter
def majorityElement_counter(nums):
freq = Counter(nums)
return freq.most_common(1)[0][0]
# Boyer-Moore O(1) space
def majorityElement_moore(nums):
candidate, count = None, 0
for num in nums:
if count == 0:
candidate = num
count += (1 if num == candidate else -1)
return candidate
nums = [2, 2, 1, 1, 2, 2, 2]
print(majorityElement_counter(nums)) # 2
print(majorityElement_moore(nums)) # 2Eerste niet-herhaalde teken
LeetCode 387 'Eerste unieke teken in een tekenreeks': vind de index van het eerste teken dat precies één keer voorkomt. Aanpak in twee doorgangen: de eerste doorgang bouwt een frequentietelling op; de tweede doorgang vindt het eerste teken met aantal 1. Tijd: O(n), ruimte: O(1), omdat het alfabet vastligt op 26 tekens.
from collections import Counter
def firstUniqChar(s):
freq = Counter(s)
for i, ch in enumerate(s):
if freq[ch] == 1:
return i
return -1
print(firstUniqChar('leetcode')) # 0 (l)
print(firstUniqChar('loveleetcode')) # 2 (v)
print(firstUniqChar('aabb')) # -1Som van deelarray is gelijk aan K (LeetCode 560)
LeetCode 560 'Som van deelarray is gelijk aan K': tel deelarrays waarvan de som k is. De brute-forceaanpak kost O(n²). De aanpak in O(n): houd een lopende prefixsom bij en een frequentietabel van prefixsommen die je tot nu toe bent tegengekomen. Voor elke positie i is het aantal deelarrays die op i eindigen en som k hebben gelijk aan het aantal eerdere prefixsommen dat gelijk is aan (current_prefix_sum - k). Initialiseer de tabel met {0: 1} om deelarrays te verwerken die op index 0 beginnen.
from collections import defaultdict
def subarraySum(nums, k):
freq = defaultdict(int)
freq[0] = 1 # prefix sum of 0 seen once (empty prefix)
prefix_sum = 0
count = 0
for num in nums:
prefix_sum += num
# How many earlier prefix sums allow a k-sum subarray ending here
count += freq[prefix_sum - k]
freq[prefix_sum] += 1
return count
print(subarraySum([1, 1, 1], 2)) # 2
print(subarraySum([1, 2, 3], 3)) # 2
print(subarraySum([1, -1, 1, -1, 1], 0)) # 4Rekenkundige bewerkingen en doorsnede met Counter
Counter ondersteunt rekenkundige bewerkingen: + voegt samen (telt aantallen op), - trekt af (kapt af op 0), & neemt het minimum (doorsnede) en | neemt het maximum (unie). Deze bewerkingen vereenvoudigen problemen zoals 'gemeenschappelijke tekens in meerdere tekenreeksen vinden' of 'het minimale aantal tekens verwijderen om van de ene tekenreeks een anagram van de andere te maken'.
from collections import Counter
A = Counter('abccdd')
B = Counter('ccdde')
print('Add: ', dict(A + B)) # sum of counts
print('Subtract: ', dict(A - B)) # A - B, clipped at 0
print('Intersect:', dict(A & B)) # min of shared counts
print('Union: ', dict(A | B)) # max counts
# Min steps to make s anagram of t (LeetCode 1347)
s, t = 'leetcode', 'practice'
diff = Counter(t) - Counter(s)
print('Chars to add:', sum(diff.values())) # 5Samenvatting: wanneer gebruik je frequenties tellen
Kies voor frequenties tellen wanneer een probleem gaat over: controleren of twee tekenreeksen gelijk zijn als je ze herschikt (anagram), de meest of minst voorkomende elementen vinden, controleren of een verzameling de juiste 'bestanddelen' heeft, of een probleem over een deelarray of deeltekenreeks omzetten in een probleem met een prefixsom en een hashmap. De kern is dat de volgorde binnen een groep niet belangrijk is — alleen de aantallen tellen.
Gebruik altijd Counter voor duidelijkheid; schakel alleen over naar een gewone dict of array als je fijnmazigere controle nodig hebt of strikt O(1) ruimte wilt gebruiken met een begrensd alfabet.
Korte kennischeck
Toets je begrip van de concepten uit Data Structures & Algorithms — Coding Interview Prep in deze les.
Samenvatting van de les
In deze les heb je geleerd dat Counter frequenties in O(n) telt met most_common, rekenkundige operatoren en toegang met standaardwaarde nul, dat groeperen op basis van een canonieke vorm (gesorteerde tuple) het groeperen van anagrammen oplost in O(nL log L) en dat een prefixsom met frequentiekaart het probleem van de som van een deelarray gelijk aan k omzet van O(n²) naar O(n). Hierna behandelen we het probleem van de langste opeenvolgende reeks en het ontwerp van een LRU-cache.
Leer Voorbereiding op programmeerinterviews met een AI-tutor — gratis
Schrijf echte code en voer die uit in je browser, krijg direct hulp van een AI-tutor die 24/7 beschikbaar is en ga verder waar je gebleven bent op het web of in de app.
- Cursussen
- 90
- Lessen
- 360
Veelgestelde vragen
Is de les “Frequenties tellen en groeperen” gratis?
Ja — de volledige tekst van “Frequenties tellen en groeperen” kun je hier gratis op het web lezen. Als je interactief wilt oefenen met een ingebouwde code-editor en een AI-begeleider die 24/7 beschikbaar is, en de rest van de cursus Voorbereiding op programmeerinterviews wilt ontgrendelen, kun je upgraden naar CoddyKit PRO. De cursus Voorbereiding op programmeerinterviews bevat in totaal 4 lessen.
Wat leer ik in “Frequenties tellen en groeperen”?
Gebruik Counter en defaultdict om tekenfrequenties te tellen, anagrammen op gesorteerde sleutel te groeperen en de meest voorkomende top-k-elementen te vinden. Je oefent met Voorbereiding op programmeerinterviews door code rechtstreeks in de browser uit te voeren. Een AI-begeleider die 24/7 beschikbaar is beantwoordt je vragen terwijl je de les doorwerkt.
Heb ik ervaring nodig om met Voorbereiding op programmeerinterviews te beginnen?
Ervaring vooraf is niet nodig. Voorbereiding op programmeerinterviews op CoddyKit is opgebouwd voor beginners tot gevorderden, zodat je hier of bij het begin kunt starten en in je eigen tempo kunt leren. Dit is les 3 van 4.
Hoe lang duurt de les “Frequenties tellen en groeperen”?
De meeste lessen van CoddyKit duren ongeveer 5–10 minuten. Elke les is kort en interactief, zodat je gestaag vooruitgaat en op het web en in de app precies verdergaat waar je was gebleven.
Kan ik code schrijven en uitvoeren in deze les over Voorbereiding op programmeerinterviews?
Ja. Elke les over Voorbereiding op programmeerinterviews bevat een ingebouwde code-editor, zodat je rechtstreeks in je browser echte code kunt schrijven en uitvoeren en direct feedback van AI krijgt — lokale installatie is niet nodig.
Alle lessen in deze cursus
- Internals van hashfuncties en botsingsafhandeling
- Two-sum en de vele varianten
- Frequenties tellen en groeperen
- Langste opeenvolgende reeks en LRU-cache