LRU cache with OrderedDict

LRU cache with OrderedDict

MediumCollections Programs · 15 of 20

Write a small least-recently-used cache that holds 2 items.

Output
['a', 'c']

Approach

  1. move_to_end on access; popitem(last=False) evicts the oldest.

Solution

Python
from collections import OrderedDict class LRUCache:    def __init__(self, capacity):        self.capacity = capacity        self.data = OrderedDict()     def get(self, key):        if key not in self.data:            return None        self.data.move_to_end(key)        return self.data[key]     def put(self, key, value):        self.data[key] = value        self.data.move_to_end(key)        if len(self.data) > self.capacity:            self.data.popitem(last=False) cache = LRUCache(2)cache.put("a", 1)cache.put("b", 2)cache.get("a")cache.put("c", 3)print(list(cache.data))
Output
['a', 'c']

Line by line

Lines 22-24

Reading “a” makes it recently used, so adding “c” evicts “b”.

Learn the concept

New to this topic? Read the lesson, then come back.

More collections programs

← All 20 Collections Programs

Records with namedtuple

Records with namedtuple

EasyCollections Programs · 13 of 20

Write a Python program to store employee records as named tuples.

Output
Asha QA 52000
Ravi Dev 61000
Ravi

Approach

  1. namedtuple("Employee", [...]).

Solution

Python
from collections import namedtuple Employee = namedtuple("Employee", ["name", "dept", "salary"])staff = [Employee("Asha", "QA", 52000), Employee("Ravi", "Dev", 61000)]for e in staff:    print(e.name, e.dept, e.salary)print(max(staff, key=lambda e: e.salary).name)
Output
Asha QA 52000
Ravi Dev 61000
Ravi

Learn the concept

New to this topic? Read the lesson, then come back.

More collections programs

← All 20 Collections Programs

Moving average with deque

Moving average with deque

MediumCollections Programs · 11 of 20

Write a Python program to compute a moving average over a window of 3 values.

Output
[20.0, 30.0, 40.0]

Approach

  1. Keep the window in a deque with maxlen and average it each step.

Solution

Python
from collections import deque values = [10, 20, 30, 40, 50]window = deque(maxlen=3)averages = []for v in values:    window.append(v)    if len(window) == 3:        averages.append(sum(window) / 3)print(averages)
Output
[20.0, 30.0, 40.0]

Learn the concept

New to this topic? Read the lesson, then come back.

More collections programs

← All 20 Collections Programs

Rotate a deque

Rotate a deque

EasyCollections Programs · 12 of 20

Write a Python program to rotate a list of players for a round-robin game.

Output
1 ['A', 'B', 'C', 'D']
2 ['B', 'C', 'D', 'A']
3 ['C', 'D', 'A', 'B']

Approach

  1. rotate(n) moves items from the end to the front.

Solution

Python
from collections import deque players = deque(["A", "B", "C", "D"])for round_no in range(1, 4):    print(round_no, list(players))    players.rotate(-1)
Output
1 ['A', 'B', 'C', 'D']
2 ['B', 'C', 'D', 'A']
3 ['C', 'D', 'A', 'B']

Learn the concept

New to this topic? Read the lesson, then come back.

More collections programs

← All 20 Collections Programs

Keep the last N items

Keep the last N items

EasyCollections Programs · 10 of 20

Write a Python program that keeps only the 3 most recent log lines.

Output
['log 4', 'log 5', 'log 6']

Approach

  1. deque(maxlen=3) drops the oldest automatically.

Solution

Python
from collections import deque recent = deque(maxlen=3)for i in range(1, 7):    recent.append(f"log {i}")print(list(recent))
Output
['log 4', 'log 5', 'log 6']

Learn the concept

New to this topic? Read the lesson, then come back.

More collections programs

← All 20 Collections Programs

Stack with deque

Stack with deque

EasyCollections Programs · 9 of 20

Write a Python program that uses a deque as a last-in, first-out stack.

Output
back to product -> search

Approach

  1. append and pop from the same end.

Solution

Python
from collections import deque history = deque()for page in ["home", "search", "product"]:    history.append(page)print("back to", history.pop(), "->", history[-1])
Output
back to product -> search

Learn the concept

New to this topic? Read the lesson, then come back.

More collections programs

← All 20 Collections Programs

Queue with deque

Queue with deque

EasyCollections Programs · 8 of 20

Write a Python program that uses a deque as a first-in, first-out queue.

Output
serving Asha | waiting: ['Ravi', 'Meena']
serving Ravi | waiting: ['Meena']
serving Meena | waiting: []

Approach

  1. append to join, popleft to serve.

Solution

Python
from collections import deque queue = deque()for customer in ["Asha", "Ravi", "Meena"]:    queue.append(customer)while queue:    print("serving", queue.popleft(), "| waiting:", list(queue))
Output
serving Asha | waiting: ['Ravi', 'Meena']
serving Ravi | waiting: ['Meena']
serving Meena | waiting: []

Learn the concept

New to this topic? Read the lesson, then come back.

More collections programs

← All 20 Collections Programs

Count with defaultdict(int)

Count with defaultdict(int)

EasyCollections Programs · 6 of 20

Write a Python program to count characters with defaultdict(int).

Output
{'b': 1, 'a': 3, 'n': 2}

Approach

  1. Missing keys start at 0.

Solution

Python
from collections import defaultdict counts = defaultdict(int)for ch in "banana":    counts[ch] += 1print(dict(counts))
Output
{'b': 1, 'a': 3, 'n': 2}

Learn the concept

New to this topic? Read the lesson, then come back.

More collections programs

← All 20 Collections Programs

Unique values per key

Unique values per key

EasyCollections Programs · 7 of 20

Write a Python program that collects the unique cities each customer ordered from.

Output
{'asha': ['Mumbai', 'Pune'], 'ravi': ['Delhi']}

Approach

  1. defaultdict(set).

Solution

Python
from collections import defaultdict orders = [("asha", "Pune"), ("ravi", "Delhi"), ("asha", "Mumbai"), ("asha", "Pune")]cities = defaultdict(set)for customer, city in orders:    cities[customer].add(city)print({k: sorted(v) for k, v in cities.items()})
Output
{'asha': ['Mumbai', 'Pune'], 'ravi': ['Delhi']}

Learn the concept

New to this topic? Read the lesson, then come back.

More collections programs

← All 20 Collections Programs

Group words by first letter

Group words by first letter

EasyCollections Programs · 5 of 20

Write a Python program to group words by their first letter with defaultdict.

Output
{'a': ['apple', 'avocado'], 'b': ['banana', 'blueberry'], 'c': ['cherry']}

Approach

  1. defaultdict(list).

Solution

Python
from collections import defaultdict words = ["apple", "avocado", "banana", "blueberry", "cherry"]groups = defaultdict(list)for w in words:    groups[w[0]].append(w)print(dict(groups))
Output
{'a': ['apple', 'avocado'], 'b': ['banana', 'blueberry'], 'c': ['cherry']}

Learn the concept

New to this topic? Read the lesson, then come back.

More collections programs

← All 20 Collections Programs