Lab

13.4.2. Lab#

  • Use this lab to practice the chapter’s coding skills in runnable Python code.

  • Sign in from the account menu before you start working on the lab.

  • Launch Live Code (the rocket) to write and run code in the coding cells.

  • Multiple submissions are allowed. The highest score is kept.

### Question 1: Stack Class: Browsing History
# Implement a Stack class backed by a list, with:
# - push(item): add item to the top of the stack
# - pop(): remove and return the top item (LIFO order)
# - peek(): return the top item without removing it
# - __len__: number of items currently on the stack
# Push 'home', then 'products', then 'checkout' onto a Stack named history
# with push().
# Pop twice and print each popped value, then print len(history).
# Print exactly these three lines:
# checkout
# products
# 1
### Your code starts here.



### Your code ends here.

Hide code cell source

 
### Solution
class Stack:
    def __init__(self):
        self.items = []

    def push(self, item):
        self.items.append(item)

    def pop(self):
        return self.items.pop()

    def peek(self):
        return self.items[-1]

    def __len__(self):
        return len(self.items)

history = Stack()
history.push("home")
history.push("products")
history.push("checkout")

print(history.pop())
print(history.pop())
print(len(history))

checkout
products
1

### Question 2: Queue Class: Serve a Customer Line
# Import deque with: from collections import deque
# Implement a Queue class backed by a deque, with:
# - enqueue(item): add item to the back of the line
# - dequeue(): remove and return the item at the front (FIFO order);
#   use self.items.popleft() so removal happens from the front
# - __len__: number of items currently waiting
# Enqueue 'apple', 'banana', 'cherry' in a Queue named customers.
# Serve two customers by calling dequeue() twice and print each result,
# then print len(customers). Print exactly these three lines:
# apple
# banana
# 1
### Your code starts here.



### Your code ends here.

Hide code cell source

 
### Solution
from collections import deque


class Queue:
    def __init__(self):
        self.items = deque()

    def enqueue(self, item):
        self.items.append(item)

    def dequeue(self):
        return self.items.popleft()

    def __len__(self):
        return len(self.items)

customers = Queue()
customers.enqueue("apple")
customers.enqueue("banana")
customers.enqueue("cherry")

print(customers.dequeue())
print(customers.dequeue())
print(len(customers))

apple
banana
1

### Question 3: Add a Node to an Org-Chart Tree
# org_chart is built from the TreeNode class taught in 13.3: each node
# has a value (the employee name) and a children list, and
# add_child(child) appends a child node.
# Write add_employee(node, manager_name, new_name) that searches the
# tree recursively for the node whose value is manager_name, and, once
# found, adds TreeNode(new_name) to that manager with add_child.
# Return True once added, False if the manager was never found
# (search the rest of the tree recursively otherwise).
# Write list_names(node) that returns a flat list of every value in
# the tree, visiting a node before its children (root first).
# Call add_employee(org_chart, 'charlie', 'erin'), then print
# list_names(org_chart) exactly:
# ['operations', 'charlie', 'erin', 'dana']
class TreeNode:
    def __init__(self, value):
        self.value = value
        self.children = []

    def add_child(self, child):
        self.children.append(child)


org_chart = TreeNode("operations")
org_chart.add_child(TreeNode("charlie"))
org_chart.add_child(TreeNode("dana"))
### Your code starts here.



### Your code ends here.

Hide code cell source

 
### Solution
class TreeNode:
    def __init__(self, value):
        self.value = value
        self.children = []

    def add_child(self, child):
        self.children.append(child)


org_chart = TreeNode("operations")
org_chart.add_child(TreeNode("charlie"))
org_chart.add_child(TreeNode("dana"))

def add_employee(node, manager_name, new_name):
    if node.value == manager_name:
        node.add_child(TreeNode(new_name))
        return True
    for child in node.children:
        if add_employee(child, manager_name, new_name):
            return True
    return False

def list_names(node):
    names = [node.value]
    for child in node.children:
        names.extend(list_names(child))
    return names

add_employee(org_chart, "charlie", "erin")
print(list_names(org_chart))

['operations', 'charlie', 'erin', 'dana']

### Question 4: Breadth-First Traversal of a Graph
# graph is an adjacency-list dict mapping each person to their
# connections. Write bfs_order(graph, start) that performs a
# breadth-first traversal starting at start and returns the list of
# names in the order they were first visited.
# Use a deque as the queue (from collections import deque; append to
# enqueue, popleft() to dequeue) and a set named visited to track
# visited names (use the in operator to test whether a name is new).
# Call bfs_order(graph, 'alice') and print exactly:
# ['alice', 'bob', 'charlie', 'dana', 'erin']
graph = {
    "alice": ["bob", "charlie"],
    "bob": ["alice", "dana"],
    "charlie": ["alice", "dana"],
    "dana": ["bob", "charlie", "erin"],
    "erin": ["dana"],
}
### Your code starts here.



### Your code ends here.

Hide code cell source

 
### Solution
from collections import deque

graph = {
    "alice": ["bob", "charlie"],
    "bob": ["alice", "dana"],
    "charlie": ["alice", "dana"],
    "dana": ["bob", "charlie", "erin"],
    "erin": ["dana"],
}

def bfs_order(graph, start):
    visited = set()
    order = []
    queue = deque([start])
    while queue:
        node = queue.popleft()
        if node in visited:
            continue
        visited.add(node)
        order.append(node)
        for neighbor in graph.get(node, []):
            if neighbor not in visited:
                queue.append(neighbor)
    return order

print(bfs_order(graph, "alice"))

['alice', 'bob', 'charlie', 'dana', 'erin']

### Question 5: Pick the Right Structure
# For each workload description below, assign the best-fitting
# Python structure as a string: 'list', 'set', 'dict', 'queue', or
# 'stack'.
# Fill in each value in the workload dict, then print workload.
# Print exactly this dict:
# {'process refund requests in the order received': 'queue', 'undo the last edit in a text editor': 'stack', 'track unique visitor IDs seen today': 'set', 'look up an account plan by username': 'dict'}
workload = {
    "process refund requests in the order received": "",
    "undo the last edit in a text editor": "",
    "track unique visitor IDs seen today": "",
    "look up an account plan by username": "",
}
### Your code starts here.



### Your code ends here.

Hide code cell source

 
### Solution
workload = {
    "process refund requests in the order received": "",
    "undo the last edit in a text editor": "",
    "track unique visitor IDs seen today": "",
    "look up an account plan by username": "",
}

workload["process refund requests in the order received"] = "queue"
workload["undo the last edit in a text editor"] = "stack"
workload["track unique visitor IDs seen today"] = "set"
workload["look up an account plan by username"] = "dict"

print(workload)

{'process refund requests in the order received': 'queue', 'undo the last edit in a text editor': 'stack', 'track unique visitor IDs seen today': 'set', 'look up an account plan by username': 'dict'}