Tutorial 7: Comprehensive Problem Solving with Data Structures

Learning Objectives

Use strings, lists, tuples, sets, dictionaries, and files in problem solving and system design and development with Python.

Overview

Welcome to the capstone tutorial! Over the previous six tutorials, you’ve built a solid foundation in Python’s core data structures: strings, lists, tuples, sets, dictionaries, and file I/O. Now it’s time to bring everything together. You will learn how to choose the right structure for a given problem, design data processing pipelines, and build complete mini‑systems that read, manipulate, and store data. This tutorial is packed with realistic examples, quizzes, exercises, and challenging homework problems to cement your skills.

1. Choosing the Right Data Structure – A Decision Guide

The first step in any data‑oriented problem is deciding which structure best fits your needs. Here’s a quick reference table:

Task	Recommended Structure	Why?
Store an ordered collection of items that may change (add/remove/modify)	`list`	Mutable, ordered, fast indexing.
Store a fixed collection that should never change (e.g., coordinates, constants)	`tuple`	Immutable, more memory‑efficient, hashable (can be a dict key).
Store unique items and test membership frequently, or perform set operations	`set`	O(1) membership, automatically eliminates duplicates.
Map keys to values for fast lookups (e.g., user ID → user data)	`dict`	O(1) key lookup, flexible keys (immutable types).
Preserve insertion order and also need key‑value mapping	`dict` (Python 3.7+)	Order is now a guaranteed feature.
Need to combine multiple data structures (e.g., list of dicts)	Use nested structures	Reflects complex relationships.

1.1 Decision Flowchart

Is order important?
  ├─ Yes → Is data mutable?
  │         ├─ Yes → list
  │         └─ No  → tuple
  └─ No → Are items unique?
            ├─ Yes → set
            └─ No → Need key‑value mapping?
                      ├─ Yes → dict
                      └─ No → list (if no uniqueness, but order not needed) – but usually you want uniqueness for sets; otherwise list is fine.

1.2 Common Scenarios

Reading a CSV file: Each row is a dict (column → value) stored in a list of rows.
Finding duplicates: Use a set to track seen items.
Counting occurrences: Use a dict (item → count).
Representing a fixed record: Use a tuple (e.g., (name, age, city)).
Storing user sessions: Use a dict mapping session ID to user data.
Managing a to‑do list: Use a list of task strings (add/remove).

2. Data Processing Pipelines

A pipeline is a sequence of steps that transform raw input into a desired output. Typical phases:

Acquisition – Read data from a file, database, or user input.
Cleaning – Remove noise, strip whitespace, handle missing values, normalize case.
Transformation – Convert formats, compute derived fields, aggregate.
Analysis – Apply business logic, calculate statistics, filter.
Output – Write results to file, display, or return to caller.

2.1 Example Pipeline – Word Frequency (Enhanced)

We’ll take the basic word counter and enhance it with cleaning steps.

import string

def word_frequency_pipeline(filename, stop_words=None, top_n=None):
    """
    Read a text file, clean each word (lowercase, remove punctuation),
    ignore stop words (if provided), count frequencies, and optionally
    return the top N words.
    """
    # Acquisition
    with open(filename, 'r', encoding='utf-8') as f:
        lines = f.readlines()

    word_counts = {}

    # Process each line
    for line in lines:
        # Cleaning: lower case and remove punctuation
        # We'll use str.translate to remove punctuation efficiently
        translator = str.maketrans('', '', string.punctuation)
        cleaned_line = line.translate(translator).lower()
        words = cleaned_line.split()

        # Transformation: count
        for word in words:
            # Check stop words
            if stop_words and word in stop_words:
                continue
            word_counts[word] = word_counts.get(word, 0) + 1

    # Analysis: sort by frequency descending
    sorted_counts = sorted(word_counts.items(), key=lambda x: x[1], reverse=True)

    # Output
    if top_n:
        return sorted_counts[:top_n]
    return sorted_counts

Example usage:

stop = {'the', 'a', 'an', 'and', 'or', 'but', 'for', 'nor', 'on', 'at', 'to', 'by'}
result = word_frequency_pipeline('sample.txt', stop_words=stop, top_n=10)
for word, count in result:
    print(f"{word}: {count}")

2.2 Streaming vs. Loading All Data

For large files, avoid readlines() (which loads all lines into memory). Instead, iterate over the file object directly:

with open('large_file.txt', 'r') as f:
    for line in f:          # reads one line at a time
        process(line)

This is memory‑efficient and should be your default for text processing.

3. Comprehensive Example 1 – Student Management System

We’ll design a simple system to manage student records. Each student has a unique ID, name, age, and list of courses (or grades). We'll store data in a dictionary keyed by ID, and persist to a CSV file.

3.1 Data Representation

students: dict[int, dict] where each inner dict has keys: id, name, age, courses (list of course names) or grades (dict course→grade). We'll keep it simple: store name, age, and a list of courses.

3.2 Core Functions

import csv
import os

STUDENT_FILE = 'students.csv'

def load_students():
    """Load student data from CSV file into a dict keyed by ID."""
    students = {}
    if not os.path.exists(STUDENT_FILE):
        return students
    with open(STUDENT_FILE, 'r', encoding='utf-8') as f:
        reader = csv.DictReader(f)
        for row in reader:
            # Convert ID to int, courses from string to list
            sid = int(row['id'])
            courses = row['courses'].split(';') if row['courses'] else []
            students[sid] = {
                'id': sid,
                'name': row['name'],
                'age': int(row['age']),
                'courses': courses
            }
    return students

def save_students(students):
    """Save students dict to CSV file."""
    with open(STUDENT_FILE, 'w', newline='', encoding='utf-8') as f:
        fieldnames = ['id', 'name', 'age', 'courses']
        writer = csv.DictWriter(f, fieldnames=fieldnames)
        writer.writeheader()
        for sid, info in students.items():
            # Convert courses list to semicolon-separated string
            courses_str = ';'.join(info['courses'])
            writer.writerow({
                'id': sid,
                'name': info['name'],
                'age': info['age'],
                'courses': courses_str
            })

def add_student(students, name, age, courses=None):
    """Add a new student with auto-incremented ID."""
    if not students:
        new_id = 1
    else:
        new_id = max(students.keys()) + 1
    students[new_id] = {
        'id': new_id,
        'name': name,
        'age': age,
        'courses': courses or []
    }
    save_students(students)
    return new_id

def delete_student(students, sid):
    """Remove a student by ID."""
    if sid in students:
        del students[sid]
        save_students(students)
        return True
    return False

def update_student(students, sid, **kwargs):
    """Update fields of a student. kwargs can be 'name', 'age', 'courses'."""
    if sid not in students:
        raise KeyError(f"Student {sid} not found")
    for key, value in kwargs.items():
        if key in students[sid]:
            students[sid][key] = value
    save_students(students)

def search_students(students, query):
    """Search by name (case-insensitive partial match)."""
    query_lower = query.lower()
    results = []
    for info in students.values():
        if query_lower in info['name'].lower():
            results.append(info)
    return results

3.3 Command‑Line Interface (Optional)

You can build a simple REPL (Read‑Eval‑Print Loop) that uses these functions. This demonstrates a complete system.

4. More Real‑World Problems

4.1 Temperature Data Analysis

Given a CSV with columns city,date,temperature, compute:

Average temperature per city.
Hottest and coldest city.
Number of days above a threshold.

Data structure: Use a dict city → list of temps, or city → total and count.

4.2 Shopping Cart System

Items: list of tuples (product_id, quantity, price).
Use set for unique product IDs.
Use dict for inventory: product_id → {name, price, stock}.
Implement checkout: calculate total, update stock.

5. Performance and Best Practices

5.1 Complexity Overview

Operation	List	Set	Dict
Indexing	O(1)	N/A	O(1) (by key)
Search (in)	O(n)	O(1)	O(1) (keys)
Insert/Delete	O(n) (unless at end)	O(1)	O(1)
Sorting	O(n log n)	N/A	N/A (can sort keys)

Use set for membership tests (e.g., if x in my_set).
Use dict for lookups (e.g., value = my_dict[key]).
Avoid repeated list.index() – it's O(n); consider a dict mapping item → index if you need many lookups.

5.2 Efficient File Reading

Use with to auto‑close.
Iterate over file lines directly (memory efficient).
For binary files, read in chunks.

5.3 Error Handling

Always anticipate failures: missing files, corrupt data, invalid input. Use try/except to fail gracefully.

5.4 Testing

Write small test functions or use doctest to verify your functions. For example:

def test_word_frequency():
    # create a temporary file or use a string
    pass

📝 Quiz – Check Your Understanding

Which data structure would you use to store a collection of unique user IDs for fast membership testing?
- (A) list
- (B) tuple
- (C) set
- (D) dict
Answer
(C) `set`
You need to store product information (ID, name, price) and frequently look up by ID. What structure is best?
- (A) list of tuples
- (B) tuple of lists
- (C) dict with ID as key and a dict/value as value
- (D) set of product objects
Answer
(C) `dict` with ID as key
True or False: When reading a large text file, it is always better to use file.read() to load all content at once for faster processing.

Answer
False – for large files, streaming line by line is memory‑efficient.
What is the time complexity of checking if an element is in a set?
- (A) O(n)
- (B) O(1)
- (C) O(log n)
- (D) O(n²)
Answer
(B) O(1) average
Given a list of words, you want to remove duplicates while preserving the original order. Which approach is best?
- (A) Convert to set and back to list (may lose order).
- (B) Use a loop with a set to track seen elements and build a new list.
- (C) Use list.count() to filter.
- (D) Use sort() and then unique.
Answer
(B) Use a loop with a set.
What does the str.translate method do in the word frequency example?
- (A) Converts the string to lowercase.
- (B) Removes punctuation characters.
- (C) Splits the string into words.
- (D) Counts word occurrences.
Answer
(B) Removes punctuation characters.
When saving a dictionary to a CSV file, why is it important to convert lists (like courses) to a string?
- (A) CSV format does not support nested structures directly.
- (B) To save disk space.
- (C) To make the file human‑readable.
- (D) Because CSV requires a delimiter.
Answer
(A) CSV does not support nested structures directly.
Which of the following is NOT a valid key type for a dictionary?
- (A) int
- (B) str
- (C) tuple
- (D) list
Answer
(D) `list` – mutable and unhashable.
In the student management system, the load_students function returns an empty dict if the file doesn't exist. This is an example of:
- (A) Error handling
- (B) Performance optimization
- (C) Data validation
- (D) Code duplication
Answer
(A) Error handling
What is the purpose of the with statement when opening files?
- (A) To handle encoding issues.
- (B) To automatically close the file after the block.
- (C) To open the file in binary mode.
- (D) To speed up read/write operations.
Answer
(B) To automatically close the file after the block.

💻 Exercises – Practice Makes Perfect

Exercise 1: Log File Summary
Write a program that reads a server log file (timestamp,level,message), counts levels, prints summary, and writes ERROR lines to a separate file.

Sample Solution

```python levels = {} errors = [] with open('server.log', 'r', encoding='utf-8') as f: for line in f: parts = line.strip().split(',', 2) if len(parts) == 3: _, level, msg = parts levels[level] = levels.get(level, 0) + 1 if level == 'ERROR': errors.append(line) print(levels) with open('errors.log', 'w', encoding='utf-8') as f: f.writelines(errors) ```

Exercise 2: Unique Word Set
Write a function unique_words(filename) that returns a set of all unique words (case‑insensitive, ignoring punctuation).

Sample Solution

```python import string def unique_words(filename): words = set() with open(filename, 'r', encoding='utf-8') as f: for line in f: line = line.translate(str.maketrans('', '', string.punctuation)).lower() words.update(line.split()) return words ```

Exercise 3: Dictionary Inversion
Given a dict mapping students to courses (as lists), return an inverted dict mapping each course to a list of students.

Sample Solution

```python def invert_dict(d): inverted = {} for student, courses in d.items(): for course in courses: inverted.setdefault(course, []).append(student) return inverted ```

Exercise 4: CSV Filter and Sum
Read a CSV with product,quantity,price, compute total revenue, filter out rows with quantity < 5, and write a new CSV with an extra total column.

Sample Solution

```python import csv rows = [] total_revenue = 0 with open('products.csv', 'r', encoding='utf-8') as f: reader = csv.DictReader(f) for row in reader: qty = int(row['quantity']) price = float(row['price']) total = qty * price total_revenue += total if qty >= 5: row['total'] = f"{total:.2f}" rows.append(row) print("Total revenue:", total_revenue) with open('filtered.csv', 'w', newline='', encoding='utf-8') as f: writer = csv.DictWriter(f, fieldnames=reader.fieldnames + ['total']) writer.writeheader() writer.writerows(rows) ```

Exercise 5: Shopping Cart with Set
Implement a shopping cart as a set of item IDs, with functions to add, remove, display, and compute total price using a product price dict.

Sample Solution

```python prices = {"item1": 10, "item2": 20, "item3": 30} cart = set() def add_item(item): cart.add(item) def remove_item(item): cart.discard(item) def display(): print(cart) def total(): return sum(prices[item] for item in cart) ```

🏠 Homework – Deeper Thinking

Short Answer Questions

1. Inventory Management System
Design a complete inventory system with a dict mapping product ID to details, functions for CRUD, sale processing, and CSV persistence.

Sample Answer

```python import csv INVENTORY_FILE = 'inventory.csv' inventory = {} def load_inventory(): # read CSV and populate inventory dict def save_inventory(): # write inventory dict to CSV def add_product(pid, name, price, stock): inventory[pid] = {'name': name, 'price': price, 'stock': stock} save_inventory() def process_sale(items): # items: list of (pid, qty) total = 0 for pid, qty in items: if pid not in inventory or inventory[pid]['stock'] < qty:raiseValueError("Insufficientstock")inventory[pid]['stock']-= qty total+= inventory[pid]['price'] *qtysave_inventory()returntotal```

2. Anagram Groups with File I/O
Read words from a file, group anagrams, output groups to a file, and print the group with the most words.

Sample Answer

```python from collections import defaultdict def anagram_groups_from_file(input_file, output_file): groups = defaultdict(list) with open(input_file, 'r', encoding='utf-8') as f: for word in f.read().split(): key = ''.join(sorted(word.lower())) groups[key].append(word) with open(output_file, 'w', encoding='utf-8') as f: for group in groups.values(): f.write(','.join(group) + '\n') largest = max(groups.values(), key=len) print("Largest group:", largest) ```

3. Data Cleaning and Analysis
Clean a messy CSV, compute average salary by city, and write a clean CSV with salary grade.

Sample Answer

```python import csv def clean_csv(input_file, output_file, city_avg_file): rows = [] city_salaries = {} with open(input_file, 'r', encoding='utf-8') as f: reader = csv.reader(f) header = next(reader) # Name,Age,City,Salary for row in reader: if len(row) < 4:continuename = row[0].strip() city = row[2].strip() try:age = int(row[1]) ifrow[1].strip()else0salary = float(row[3]) ifrow[3].strip()else0.0exceptValueError:age,salary = 0, 0.0grade = 'low' ifsalary<30000else'medium'ifsalary<70000else'high'rows.append([name,age,city,salary,grade])city_salaries.setdefault(city,[]).append(salary)#WritecleanedCSVwithopen(output_file,'w',newline='',encoding='utf-8')asf:writer = csv.writer(f) writer.writerow(['Name','Age','City','Salary','Grade'])writer.writerows(rows)#Writecityaverageswithopen(city_avg_file,'w',encoding='utf-8')asf:forcity,salariesincity_salaries.items():avg = sum(salaries)/len(salaries)f.write(f"{city}:{avg:.2f}\n")```

4. Building a Simple Search Engine (In‑Memory)
Build an inverted index (word → set of document IDs) and implement a search for AND queries. Persist to JSON.

Sample Answer

```python import json def build_index(documents): index = {} for doc_id, text in enumerate(documents): words = set(text.lower().split()) for word in words: index.setdefault(word, set()).add(doc_id) return index def search(query, index): words = query.lower().split() if not words: return set() result = index.get(words[0], set()) for word in words[1:]: result &= index.get(word, set()) return result # Save/load with json (convert sets to lists) ```

Essay Questions

5. Simulating a Bank Account System
Design a system with accounts, transactions, deposit/withdraw/transfer, and file persistence.

Sample Answer

```python import csv, datetime ACCOUNTS_FILE = 'accounts.csv' TRANSACTIONS_FILE = 'transactions.csv' accounts = {} def load_accounts(): # read CSV, populate accounts dict with history list def save_accounts(): # write accounts and transactions to CSV def create_account(owner, balance=0): acc_no = max(accounts.keys())+1 if accounts else 1 accounts[acc_no] = {'owner': owner, 'balance': balance, 'history': []} save_accounts() return acc_no def deposit(acc_no, amount, desc=""): accounts[acc_no]['balance'] += amount accounts[acc_no]['history'].append((datetime.date.today(), amount, desc)) save_accounts() def withdraw(acc_no, amount): if accounts[acc_no]['balance'] < amount:raiseValueError("Insufficientfunds")accounts[acc_no]['balance']-= amount accounts[acc_no]['history'].append((datetime.date.today(),-amount,"Withdrawal"))save_accounts()deftransfer(from_acc,to_acc,amount):withdraw(from_acc,amount)deposit(to_acc,amount,"Transferfrom"+str(from_acc))```

Homework Hints

Q1: Use dict for inventory, csv.DictReader/DictWriter. For sale, loop, check stock, update.
Q2: Key = ''.join(sorted(word)); use a dictionary mapping key to list.
Q3: Use csv.reader; handle exceptions with try/except; use strip(), isdigit(), etc.
Q4: Index: {word: set(doc_ids)}; search: intersect sets for all words.
Q5: Use datetime for dates; save accounts to CSV, transactions to separate CSV with account number.

Summary

In this capstone tutorial, you have:

Learned how to choose the right data structure based on problem requirements.
Designed and implemented data processing pipelines that clean, transform, and aggregate data.
Built a complete student management system with file persistence.
Explored performance considerations and best practices.
Solved a variety of practical problems that combine all the skills from previous tutorials.

You are now ready to tackle real‑world challenges that require thoughtful data organization and manipulation. Keep practicing, and always think about the trade‑offs between different structures. The more you work with them, the more intuitive your choices will become.

What’s next? Continue building your own projects, explore more advanced libraries like pandas for data analysis, or dive into object‑oriented programming to structure larger systems.

Happy problem solving!

Previous | Tutorial index | Next