Generic interface for collections in Typescript - Time & Space Complexity

Time Complexity: Generic interface for collections

O(n)

Understanding Time Complexity

When working with generic interfaces for collections, it's important to know how the time to perform actions changes as the collection grows.

We want to find out how the number of steps grows when we add or check items in the collection.

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

interface Collection<T> {
  add(item: T): void;
  contains(item: T): boolean;
}

class SimpleCollection<T> implements Collection<T> {
  private items: T[] = [];

  add(item: T): void {
    this.items.push(item);
  }

  contains(item: T): boolean {
    return this.items.includes(item);
  }
}
    

This code defines a generic collection interface and a simple class that stores items in an array. It adds items and checks if an item exists.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: The contains method uses includes, which checks each item one by one.
• How many times: It may check up to all items in the array, depending on where the item is found.

How Execution Grows With Input

Explain the growth pattern intuitively.

Input Size (n)	Approx. Operations
10	Up to 10 checks
100	Up to 100 checks
1000	Up to 1000 checks

Pattern observation: The number of checks grows directly with the number of items. More items mean more steps to find one.

Final Time Complexity

Time Complexity: O(n)

This means the time to check if an item exists grows in a straight line with the number of items in the collection.

Common Mistake

[X] Wrong: "Checking if an item exists is always fast and takes the same time no matter how many items there are."

[OK] Correct: Because the method checks items one by one, more items mean more checks, so it takes longer as the collection grows.

Interview Connect

Understanding how generic collections work and how their operations scale helps you explain your code choices clearly and confidently in real projects and interviews.

Self-Check

"What if we changed the internal storage from an array to a Set? How would the time complexity of contains change?"

Practice

1. What does the <T> represent in a generic interface in TypeScript?

easy

A. A function inside the interface

B. A fixed type like number or string

C. A placeholder for any type that will be specified later

D. A variable name for a property

Solution

1. Step 1: Understand generic syntax

   The <T> in TypeScript generics is a placeholder representing any type that will be provided when the interface is used.

2. Step 2: Differentiate from fixed types

   Unlike fixed types like number or string, T is flexible and can represent any type, making the interface reusable.

3. Final Answer:

   A placeholder for any type that will be specified later -> Option C

4. Quick Check:

   Generic <T> = placeholder type [OK]

Hint: Remember <T> means 'any type' placeholder [OK]

Common Mistakes:

• Thinking T is a fixed type
• Confusing T with a function
• Assuming T is a variable name

2. Which of the following is the correct syntax to declare a generic interface named Collection with a type parameter T?

easy

A. interface Collection<T> { items: T[]; }

B. interface Collection { items: T[]; }

C. interface Collection<T> { items: Array; }

D. interface Collection<T> { items: T; }

Solution

1. Step 1: Check generic declaration

   The correct syntax to declare a generic interface uses <T> after the interface name, like interface Collection<T>.

2. Step 2: Verify property type

   The property items should be an array of type T, so items: T[] is correct.

3. Final Answer:

   interface Collection<T> { items: T[]; } -> Option A

4. Quick Check:

   Generic interface syntax = interface Collection<T> { items: T[]; } [OK]

Hint: Generic interface needs <T> and array type T[] [OK]

Common Mistakes:

• Omitting <T> after interface name
• Using Array without type parameter
• Declaring items as single T instead of array

3. Given the interface and usage below, what is the output of console.log(numbers.items[1])?

interface Collection<T> {
  items: T[];
}
const numbers: Collection<number> = { items: [10, 20, 30] };
console.log(numbers.items[1]);

medium

A. 10

B. 20

C. 30

D. undefined

Solution

1. Step 1: Understand the generic interface usage

   The interface Collection<T> is used with number, so items is an array of numbers: [10, 20, 30].

2. Step 2: Access the second element in the array

   Arrays are zero-indexed, so items[1] is the second element, which is 20.

3. Final Answer:

   20 -> Option B

4. Quick Check:

   Array index 1 = 20 [OK]

Hint: Remember arrays start at index 0 [OK]

Common Mistakes:

• Confusing index 1 with index 0
• Assuming generic changes array order
• Expecting undefined for valid index

4. Identify the error in this code snippet using a generic interface:

interface Collection<T> {
  items: T[];
}
const strings: Collection<string> = { items: [1, 2, 3] };

medium

A. The array items contain numbers, but the interface expects strings

B. The interface is missing the generic type parameter

C. The variable strings should be declared with type number

D. The interface property items should not be an array

Solution

1. Step 1: Check the generic type used

   The variable strings is declared as Collection<string>, so items must be an array of strings.

2. Step 2: Check the assigned array type

   The assigned array is [1, 2, 3], which is an array of numbers, not strings, causing a type mismatch error.

3. Final Answer:

   The array items contain numbers, but the interface expects strings -> Option A

4. Quick Check:

   Type mismatch in generic array = The array items contain numbers, but the interface expects strings [OK]

Hint: Check if array elements match generic type [OK]

Common Mistakes:

• Ignoring type mismatch between generic and array
• Forgetting to specify generic parameter
• Assuming interface property can be non-array

5. You want to create a generic interface KeyValueCollection that stores key-value pairs where keys are strings and values can be any type T. Which interface definition correctly achieves this?

hard

A. interface KeyValueCollection<T> { [T: string]: string; }

B. interface KeyValueCollection<T> { keys: string[]; values: T[]; }

C. interface KeyValueCollection<T> { key: string; value: T; }

D. interface KeyValueCollection<T> { [key: string]: T; }

Solution

1. Step 1: Understand key-value pair requirement

   The interface should allow any string as a key and associate it with a value of generic type T.

2. Step 2: Check index signature syntax

   Using [key: string]: T; means any string key maps to a value of type T, which matches the requirement.

3. Step 3: Eliminate other options

   interface KeyValueCollection<T> { keys: string[]; values: T[]; } separates keys and values arrays, which is less direct. interface KeyValueCollection<T> { key: string; value: T; } defines a single pair, not a collection. interface KeyValueCollection<T> { [T: string]: string; } has incorrect syntax.

4. Final Answer:

   interface KeyValueCollection<T> { [key: string]: T; } -> Option D

5. Quick Check:

   Index signature with generic value = interface KeyValueCollection<T> { [key: string]: T; } [OK]

Hint: Use index signature [key: string]: T for generic key-value [OK]

Common Mistakes:

• Using arrays for keys and values separately
• Defining only one key-value pair instead of collection
• Incorrect index signature syntax