Schema definitions in Rest API - Time & Space Complexity

Time Complexity: Schema definitions

O(n)

Understanding Time Complexity

When working with schema definitions in REST APIs, it's important to understand how the time to process schemas changes as they grow.

We want to know how the execution time grows when the schema has more fields or nested objects.

Scenario Under Consideration

Analyze the time complexity of the following schema validation code snippet.

function validateSchema(data, schema) {
  for (const field in schema) {
    if (typeof schema[field] === 'object' && schema[field] !== null) {
      validateSchema(data[field], schema[field]);
    } else {
      if (typeof data[field] !== schema[field]) {
        throw new Error('Invalid type');
      }
    }
  }
}
    

This code checks if the data matches the schema by going through each field and validating types, including nested objects.

Identify Repeating Operations

• Primary operation: Looping over each field in the schema object.
• How many times: Once for each field, including recursively for nested objects.

How Execution Grows With Input

As the number of fields in the schema grows, the function checks each one, including nested fields.

Input Size (fields in schema)	Approx. Operations
10	About 10 checks
100	About 100 checks
1000	About 1000 checks

Pattern observation: The number of operations grows roughly in direct proportion to the number of fields.

Final Time Complexity

Time Complexity: O(n)

This means the time to validate grows linearly with the number of fields in the schema.

Common Mistake

[X] Wrong: "The validation time stays the same no matter how big the schema is."

[OK] Correct: Each field must be checked, so more fields mean more work and longer time.

Interview Connect

Understanding how schema validation time grows helps you explain API performance and design better data checks.

Self-Check

"What if the schema included arrays of objects? How would the time complexity change?"

Practice

1. What is the main purpose of a schema definition in a REST API?

easy

A. To improve the speed of the API response

B. To store user login information securely

C. To handle server errors automatically

D. To describe the structure and rules of the data exchanged

Solution

1. Step 1: Understand what schema definitions do

   Schema definitions specify how data should look and what rules it must follow in an API.

2. Step 2: Match purpose with options

   Only To describe the structure and rules of the data exchanged correctly states that schemas describe data structure and rules.

3. Final Answer:

   To describe the structure and rules of the data exchanged -> Option D

4. Quick Check:

   Schema = Data structure and rules [OK]

Hint: Schemas define data shape and rules in APIs [OK]

Common Mistakes:

• Confusing schema with security features
• Thinking schema speeds up API
• Assuming schema handles errors

2. Which of the following is the correct way to define a simple string property called name in an OpenAPI schema?

easy

A. name: string

B. name: { type: 'string' }

C. name: 'string' type

D. name: { string: true }

Solution

1. Step 1: Recall OpenAPI property syntax

   Properties are defined as key-value pairs with a type inside an object, e.g., name: { type: 'string' }.

2. Step 2: Compare options

   Only name: { type: 'string' } matches the correct syntax for defining a string property.

3. Final Answer:

   name: { type: 'string' } -> Option B

4. Quick Check:

   Property syntax = key: { type: 'string' } [OK]

Hint: Use key: { type: 'string' } for string properties [OK]

Common Mistakes:

• Writing type outside an object
• Using plain string without type key
• Confusing property name with type

3. Given this OpenAPI schema snippet, what is the type of the age property?

components:
  schemas:
    User:
      type: object
      properties:
        age:
          type: integer
          minimum: 0

medium

A. integer

B. string

C. boolean

D. array

Solution

1. Step 1: Read the schema property definition

   The age property is defined with type: integer and a minimum value of 0.

2. Step 2: Identify the data type

   The type clearly states integer, meaning whole numbers only.

3. Final Answer:

   integer -> Option A

4. Quick Check:

   age type = integer [OK]

Hint: Look for 'type' key to find property data type [OK]

Common Mistakes:

• Assuming age is string by default
• Confusing integer with boolean
• Ignoring the type key

4. Identify the error in this JSON schema snippet for a REST API:

{
  "type": "object",
  "properties": {
    "id": { "type": "integer" },
    "email": { "type": "string", "format": "email" },
    "active": "boolean"
  },
  "required": ["id", "email"]
}

medium

A. "id" property type should be string

B. "required" must include "active"

C. "active" property should be an object with a type key

D. Missing comma after "email" property

Solution

1. Step 1: Check property definitions

   Each property must be an object with a "type" key. "active" is given as a string "boolean" instead of an object.

2. Step 2: Validate other parts

   "id" type integer is correct, "required" does not need "active", and commas are correctly placed.

3. Final Answer:

   "active" property should be an object with a type key -> Option C

4. Quick Check:

   Property format = object with type key [OK]

Hint: Properties must be objects with type keys, not strings [OK]

Common Mistakes:

• Writing property types as strings directly
• Forgetting to wrap property details in objects
• Assuming required means all properties

5. You want to define a schema for a REST API response that returns a list of users, where each user has a username (string) and roles (array of strings). Which schema snippet correctly represents this?

hard

A. type: object
properties:
users:
type: array
items:
type: object
properties:
username:
type: string
roles:
type: array
items:
type: string

B. type: array
items:
type: object
properties:
username: string
roles: array of strings

C. type: object
properties:
users:
type: object
properties:
username: string
roles: string

D. type: array
items:
type: string
properties:
username: string
roles: array

Solution

1. Step 1: Understand the data structure

   The response is an object with a "users" property that is an array of user objects.

2. Step 2: Check each user object schema

   Each user has "username" as string and "roles" as an array of strings, so nested arrays and objects are needed.

3. Step 3: Match with options

   Only type: object properties: users: type: array items: type: object properties: username: type: string roles: type: array items: type: string correctly nests arrays and objects with proper types and keys.

4. Final Answer:

   type: object properties: users: type: array items: type: object properties: username: type: string roles: type: array items: type: string -> Option A

5. Quick Check:

   Nested arrays and objects = type: object properties: users: type: array items: type: object properties: username: type: string roles: type: array items: type: string [OK]

Hint: Use nested objects and arrays for complex data shapes [OK]

Common Mistakes:

• Writing array items as plain strings
• Confusing object and array types
• Missing nested items key for arrays