Choosing the right data structure in Intro to Computing - Practice Problems & Coding Challenges

Challenge - 5 Problems

🧠 Conceptual

intermediate

Choosing the best data structure for fast lookup

You want to store a collection of unique items and check if an item exists quickly. Which data structure is best?

A Stack because it adds and removes items from one end

B List (array) because it keeps items in order

C Set because it allows fast membership testing

D Queue because it processes items in order

💡 Hint

Think about which structure lets you check if an item is inside without looking at every element.

A set stores unique items and uses a method that lets it check if an item is present very quickly, unlike a list which may need to check each item one by one.

❓ Comparison

intermediate

Comparing list and dictionary for data storage

You need to store student names and their grades. Which data structure is better to quickly find a student's grade by name?

A Dictionary with names as keys and grades as values

B List of tuples (name, grade) because it keeps data together

C Set of names because it stores unique names

D Queue of grades because it processes grades in order

💡 Hint

Think about which structure lets you find a grade by name without searching through all items.

Dictionaries store data as key-value pairs, so you can get a grade by using the student's name as a key instantly, unlike a list where you might have to check each item.

❓ trace

advanced

Trace the output of stack operations

Given the following operations on an empty stack, what is the final content of the stack?

Intro to Computing

stack = []
stack.append(10)
stack.append(20)
stack.pop()
stack.append(30)
stack.pop()
stack.append(40)

A [10, 40]

B [10, 20, 30, 40]

C [40]

D [10, 20]

💡 Hint

Remember that pop() removes the last item added (LIFO).

Step by step: start empty, add 10, add 20, remove 20, add 30, remove 30, add 40. Left with 10 and 40.

❓ identification

advanced

Identify the data structure from behavior

You have a data structure that adds items at one end and removes items from the other end, processing items in the order they were added. What is it?

A Stack

B Set

C Dictionary

D Queue

💡 Hint

Think about the order items come out compared to the order they went in.

A queue adds items at the back and removes from the front, so items come out in the same order they went in (FIFO).

🚀 Application

expert

Choosing data structure for a phone book application

You are designing a phone book app that stores names and phone numbers. Users often search by name, add new contacts, and delete contacts. Which data structure is best to use internally?

A List of tuples (name, number) because it keeps order

B Dictionary with names as keys and numbers as values for fast search, add, and delete

C Set of names because it stores unique names

D Stack because it allows adding and removing contacts easily

💡 Hint

Consider which structure supports fast search, addition, and deletion by key.

Dictionaries allow fast lookup, insertion, and deletion by key, which fits the phone book needs better than lists or stacks.

Practice

1. Which data structure should you use if you want to store a list of items where order matters and duplicates are allowed?

easy

A. List or array

B. Set

C. Dictionary

D. Tuple

Solution

1. Step 1: Understand the need for order and duplicates

   Lists and arrays keep the order of items and allow duplicates, which matches the requirement.

2. Step 2: Compare with other structures

   Sets do not allow duplicates, dictionaries store key-value pairs, and tuples are immutable but also keep order.

3. Final Answer:

   List or array -> Option A

4. Quick Check:

   Order + duplicates = List/array [OK]

Hint: Use lists for ordered data with duplicates [OK]

Common Mistakes:

• Choosing set which removes duplicates
• Choosing dictionary which stores key-value pairs
• Confusing tuple immutability with order

2. Which of the following is the correct way to create an empty set in Python?

easy

A. empty_set = {}

B. empty_set = set()

C. empty_set = []

D. empty_set = ()

Solution

1. Step 1: Recall syntax for empty set

   In Python, {} creates an empty dictionary, not a set.

2. Step 2: Identify correct set creation

   Using set() creates an empty set correctly.

3. Final Answer:

   empty_set = set() -> Option B

4. Quick Check:

   Empty set = set() [OK]

Hint: Use set() to create empty sets, {} is a dict [OK]

Common Mistakes:

• Using {} which creates an empty dictionary
• Using [] which creates a list
• Using () which creates a tuple

3. What will be the output of this Python code?

data = {'apple': 3, 'banana': 5, 'orange': 2}
print(data['banana'])

medium

A. 5

B. 3

C. 'banana'

D. KeyError

Solution

1. Step 1: Understand dictionary key-value access

   In the dictionary, 'banana' is a key with value 5.

2. Step 2: Access the value for 'banana'

   Using data['banana'] returns the value 5.

3. Final Answer:

   5 -> Option A

4. Quick Check:

   Dictionary key 'banana' = 5 [OK]

Hint: Dictionary[key] returns the value for that key [OK]

Common Mistakes:

• Confusing key with value
• Expecting the key name as output
• Mistyping key causing KeyError

4. You want to store unique user IDs and quickly check if a user ID exists. Which data structure is best? The code below has an error. Find and fix it.

user_ids = []
user_ids.add(101)
user_ids.add(102)

medium

A. Use dictionary instead of list

B. Use append instead of add: user_ids.append(101)

C. Change list to set: user_ids = set()

D. No error, code is correct

Solution

1. Step 1: Identify the error in method usage

   Lists do not have an add() method; add() is for sets.

2. Step 2: Choose correct data structure for unique items

   Sets store unique items and support add() method, so change list to set.

3. Final Answer:

   Change list to set: user_ids = set() -> Option C

4. Quick Check:

   Unique items + add() = set [OK]

Hint: Use set() for unique items and add() method [OK]

Common Mistakes:

• Using add() on list causing AttributeError
• Using append() but duplicates allowed
• Choosing dictionary unnecessarily

5. You have a list of student names with possible duplicates. You want to count how many times each name appears. Which data structure is best and why?

hard

A. Use a tuple to store names immutably

B. Use a set to store unique names only

C. Use a list to store all names again

D. Use a dictionary to map names to counts

Solution

1. Step 1: Understand the need to count occurrences

   Counting requires storing each name with its count, which is a key-value pair.

2. Step 2: Choose data structure for key-value pairs

   Dictionaries store keys (names) with values (counts), perfect for this task.

3. Final Answer:

   Use a dictionary to map names to counts -> Option D

4. Quick Check:

   Counting items = dictionary [OK]

Hint: Use dictionary for counting items with keys and values [OK]

Common Mistakes:

• Using set which removes duplicates and loses counts
• Using list which doesn't map names to counts
• Using tuple which is immutable and not for counting