Data Structures
Data structures are formats for organizing, managing, and storing data. Python’s primary built-in data structures are: * **List**: Mutable, ordered sequence of ...
Definition
Data structures are formats for organizing, managing, and storing data. Python’s primary built-in data structures are:
- List: Mutable, ordered sequence of items.
- Tuple: Immutable, ordered sequence of items.
- Dictionary (Dict): Mutable, unordered collection of key-value pairs (guaranteed insertion order since Python 3.7).
- Set: Mutable, unordered collection of unique elements.
Why It Exists
Handling large context datasets, sliding windows of conversation histories, and vector indexes requires choosing the correct data structure. An incorrect structure can slow down searches from to , causing severe runtime latency issues.
How It Works
MEMORY STRUCTURES
List: [ Element 0 | Element 1 | Element 2 ] --> Contiguous Array (O(N) search)
Dictionary: { Key ──► Hash Function ──► Index } --> Hash Table (O(1) search)
Tuple: ( Element 0 | Element 1 ) --> Static Memory Allocation (Immutable)
* **Lists** use dynamic contiguous arrays under the hood. Resizing requires copying elements to a larger memory region.
* **Dictionaries** use hash tables. Resolving keys takes constant time ($O(1)$) on average.
* **Tuples** are stored directly in a static memory block, making them cheaper to construct and hashable as dictionary keys.Real-World Example
In Retrieval-Augmented Generation (RAG) systems, a Set is used to store deduplicated document IDs fetched from different retrieval queries, ensuring that duplicate passages are never fed to the LLM context window.
Python Example
Here is a production-style batch prompt formatting pipeline utilizing zip, dictionary comprehensions, and tuple unpacking:
from typing import List, Tuple, Dict
def prepare_prompt_batches(users: List[Tuple[str, str]], template: str) -> Dict[str, str]:
"""
Zips raw user metadata and returns a fast O(1) dictionary mapping
user IDs to formatted prompt payloads.
"""
# Comprehension with dynamic token replacement
return {
user_id: template.format(name=name)
for user_id, name in users
}
if __name__ == "__main__":
user_records = [
("usr_001", "Alice"),
("usr_002", "Bob"),
("usr_003", "Charlie")
]
prompt_template = "Hello {name}, how can I help you today?"
batches = prepare_prompt_batches(user_records, prompt_template)
print("Formatted User 002:", batches["usr_002"])Interview Questions
- Beginner: What is the difference between a list and a tuple?
- Intermediate: How do Python dictionaries achieve average time complexity for lookup operations?
- Advanced: Why can't a mutable list be used as a key in a dictionary? Explain the concept of hashability.
Interview Answers
- Beginner: A list is mutable (can be changed after creation), whereas a tuple is immutable (cannot be altered). Lists are written with square brackets
[], and tuples are written with parentheses(). - Intermediate: Python dictionaries use hash tables. The key is passed through a hash function to generate an integer index mapping directly to a memory slot. This direct lookup bypasses sequential scanning, resulting in average lookup time.
- Advanced: Dictionary keys must be hashable. An object is hashable if it has a hash value that never changes during its lifetime (implements
__hash__()and__eq__()). Since lists are mutable, their contents can change, which would alter their hash value and corrupt the lookup mechanics of the hash table.
Common Mistakes
- Sequential lists for membership checks: Using
if user_id in user_list:which runs in time. Convert the list to aSet(if user_id in user_set:) to change search performance to .
Assignment
Write a function that accepts a list of dictionary metadata and returns a list of unique category strings using a Set, maintaining the order of appearance.