Formatting structured data in Python - Time & Space Complexity

Time Complexity: Formatting structured data

O(n^2)

Understanding Time Complexity

When we format structured data, like turning a list or dictionary into a string, the time it takes depends on how much data we have.

We want to know how the work grows as the data gets bigger.

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

    def format_data(data):
        result = ""
        for key, value in data.items():
            result += f"{key}: {value}\n"
        return result
    

This code takes a dictionary and creates a string with each key and value on its own line.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Looping through each key-value pair in the dictionary.
• How many times: Once for every item in the dictionary.

How Execution Grows With Input

As the number of items grows, the work grows in a similar way.

Input Size (n)	Approx. Operations
10	About 10 loops and string additions
100	About 100 loops and string additions
1000	About 1000 loops and string additions

Pattern observation: The work grows directly with the number of items; double the items, double the work.

Final Time Complexity

Time Complexity: O(n^2)

This means the time to format the data grows quadratically with the number of items due to string concatenation in a loop.

Common Mistake

[X] Wrong: "Formatting data is always super fast and doesn't depend on size."

[OK] Correct: Actually, the more items you have, the more work the program must do to format each one, so time grows with size.

Interview Connect

Understanding how formatting time grows helps you explain how programs handle bigger data smoothly and why efficiency matters.

Self-Check

"What if we used a list of tuples instead of a dictionary? How would the time complexity change?"

Practice

1. What does the indent parameter do in json.dumps() when formatting structured data?

easy

A. Adds spaces and new lines to make the output easier to read

B. Converts data into a binary format

C. Removes all spaces and new lines for compact output

D. Encrypts the JSON data for security

Solution

1. Step 1: Understand the purpose of json.dumps()

   This function converts Python data into a JSON string.

2. Step 2: Role of indent parameter

   The indent parameter adds spaces and new lines to format the JSON string nicely for readability.

3. Final Answer:

   Adds spaces and new lines to make the output easier to read -> Option A

4. Quick Check:

   indent = readable JSON [OK]

Hint: Remember: indent means pretty print with spaces [OK]

Common Mistakes:

• Thinking indent compresses JSON
• Confusing indent with encryption
• Assuming indent changes data content

2. Which of the following is the correct syntax to format a Python dictionary data as a JSON string with indentation of 4 spaces?

easy

A. json.dumps(data, indent=4)

B. json.dumps(data, indent='4')

C. json.dumps(data, indent=True)

D. json.dumps(data, space=4)

Solution

1. Step 1: Check the correct parameter type for indent

   The indent parameter expects an integer number of spaces, not a string or boolean.

2. Step 2: Validate each option

   json.dumps(data, indent=4) uses indent=4 correctly. json.dumps(data, indent='4') uses a string '4' which is invalid. json.dumps(data, indent=True) uses boolean True which is invalid. json.dumps(data, space=4) uses a wrong parameter name space.

3. Final Answer:

   json.dumps(data, indent=4) -> Option A

4. Quick Check:

   Indent value must be integer [OK]

Hint: Use integer for indent, not string or boolean [OK]

Common Mistakes:

• Passing indent as a string instead of integer
• Using wrong parameter name like 'space'
• Passing boolean instead of number

3. What is the output of this code?

import json
data = {'name': 'Alice', 'age': 30}
print(json.dumps(data, indent=2))

medium

A. {"name": "Alice", "age": 30}

B. {
"name": "Alice",
"age": 30
}

C. {name: Alice, age: 30}

D. SyntaxError

Solution

1. Step 1: Understand json.dumps with indent=2

   The function converts the dictionary to a JSON string with 2 spaces indentation for each nested level.

2. Step 2: Check the output format

   The output will have new lines and spaces, keys and string values in double quotes, and numeric values as is.

3. Final Answer:

   { "name": "Alice", "age": 30 } -> Option B

4. Quick Check:

   Indent=2 adds spaces and new lines [OK]

Hint: Indent adds new lines and spaces for readability [OK]

Common Mistakes:

• Expecting compact JSON without spaces
• Using single quotes instead of double quotes
• Confusing Python dict print with JSON string

4. The following code throws an error. What is the mistake?

import json
data = {'x': 1, 'y': 2}
print(json.dumps(data, indent=2.0))

medium

A. json.dumps requires a second argument for separators

B. The data dictionary keys must be strings only

C. json.dumps cannot format dictionaries

D. The indent parameter should be an integer, not a float

Solution

1. Step 1: Identify the error cause

   The indent parameter is given as a float 2.0 instead of an integer 2.

2. Step 2: Understand parameter type requirements

   json.dumps expects indent to be an integer number of spaces for formatting, passing a float causes a TypeError.

3. Final Answer:

   The indent parameter should be an integer, not a float -> Option D

4. Quick Check:

   Indent must be int, not float [OK]

Hint: Check indent type: must be integer, not float [OK]

Common Mistakes:

• Passing indent as float instead of int
• Thinking keys must be strings for json.dumps
• Expecting separators argument is mandatory

5. You have a list of dictionaries representing users:

users = [{'name': 'Bob', 'age': 25}, {'name': 'Eve', 'age': 28}]

How do you create a JSON string with indentation of 2 spaces and keys sorted alphabetically?

hard

A. json.dumps(users, indent='2', sort_keys=True)

B. json.dumps(users, indent=2, sort=True)

C. json.dumps(users, indent=2, sort_keys=True)

D. json.dumps(users, pretty=2, sort_keys=True)

Solution

1. Step 1: Use json.dumps with indent and sort_keys

   The indent parameter formats the JSON with spaces and new lines. The sort_keys=True sorts dictionary keys alphabetically.

2. Step 2: Validate correct parameter names and types

   json.dumps(users, indent=2, sort_keys=True) uses correct parameters and types. json.dumps(users, indent=2, sort=True) uses invalid parameter sort. json.dumps(users, indent='2', sort_keys=True) passes indent as string which is invalid. json.dumps(users, pretty=2, sort_keys=True) uses invalid parameter pretty.

3. Final Answer:

   json.dumps(users, indent=2, sort_keys=True) -> Option C

4. Quick Check:

   Use indent=int and sort_keys=True [OK]

Hint: Use sort_keys=True and indent as integer [OK]

Common Mistakes:

• Using wrong parameter names like sort or pretty
• Passing indent as string
• Forgetting sort_keys to sort keys