Implementing a Constant-Time Set with O(1) Insert, Remove, Lookup, Clear, and Iterate Operations in Go

Interview Question:

You are given an array of size N to implement a set data structure. The set should support the following operations:

• Insert(x): Insert an element x into the set, where 0 ≤ x < N.
• Remove(x): Remove an element x from the set.
• Lookup(x): Check if an element x is present in the set.
• Clear(): Clear all elements from the set.
• Iterate(): Iterate over all elements currently in the set.

All operations should have a time complexity of O(1).

Constraints:

• Elements to be stored are integers in the range [0, N-1].
• The set should be implemented using arrays of size N.
• The operations must be efficient, with all of them running in constant time.

Solution

To achieve all operations in O(1) time, we can implement a data structure known as a sparse set. This structure leverages arrays and direct indexing to provide constant-time insertions, deletions, lookups, and clear operations.

Data Structures Used

1. values []int: An array to store the current elements in the set.
2. indices []int: An array to map each element to its index in the values array.
3. timestamps []int: An array to track the presence of elements in the set.
4. size int: An integer to keep track of the number of elements in the set.
5. timeStamp int: A counter incremented on each Clear() to reset the set efficiently.
6. capacity int: The maximum number of elements (N).

Implementation in Go

package main

import "fmt"

type FastSet struct {
    size       int
    values     []int
    indices    []int
    timestamps []int
    timeStamp  int
    capacity   int
}

// NewFastSet initializes a new FastSet with capacity N
func NewFastSet(N int) *FastSet {
    return &FastSet{
        values:     make([]int, N),
        indices:    make([]int, N),
        timestamps: make([]int, N),
        timeStamp:  1,
        capacity:   N,
    }
}

// Insert adds x to the set if it's not already present
func (fs *FastSet) Insert(x int) {
    if x < 0 || x >= fs.capacity {
        fmt.Printf("Value %d out of bounds\n", x)
        return
    }
    if fs.timestamps[x] != fs.timeStamp {
        fs.timestamps[x] = fs.timeStamp
        fs.indices[x] = fs.size
        fs.values[fs.size] = x
        fs.size++
    }
}

// Remove deletes x from the set if it's present
func (fs *FastSet) Remove(x int) {
    if x < 0 || x >= fs.capacity {
        fmt.Printf("Value %d out of bounds\n", x)
        return
    }
    if fs.timestamps[x] == fs.timeStamp {
        idx := fs.indices[x]
        last := fs.values[fs.size-1]
        fs.values[idx] = last
        fs.indices[last] = idx
        fs.size--
        fs.timestamps[x] = 0 // Optional: reset timestamp
    }
}

// Contains checks if x is in the set
func (fs *FastSet) Contains(x int) bool {
    if x < 0 || x >= fs.capacity {
        fmt.Printf("Value %d out of bounds\n", x)
        return false
    }
    return fs.timestamps[x] == fs.timeStamp
}

// Clear empties the set
func (fs *FastSet) Clear() {
    fs.size = 0
    fs.timeStamp++
    if fs.timeStamp == 0 { // Handle overflow
        fs.timeStamp++
    }
}

// Iterate over the elements in the set
func (fs *FastSet) Iterate() []int {
    return fs.values[:fs.size]
}

func main() {
    N := 10
    set := NewFastSet(N)

    // Insert elements
    set.Insert(3)
    set.Insert(5)
    set.Insert(7)
    fmt.Println("Set after inserts:", set.Iterate())

    // Check if elements are in the set
    fmt.Println("Contains 5?", set.Contains(5)) // true
    fmt.Println("Contains 2?", set.Contains(2)) // false

    // Remove an element
    set.Remove(5)
    fmt.Println("Set after removing 5:", set.Iterate())
    fmt.Println("Contains 5?", set.Contains(5)) // false

    // Insert a new element
    set.Insert(2)
    fmt.Println("Set after inserting 2:", set.Iterate())
    fmt.Println("Contains 2?", set.Contains(2)) // true

    // Clear the set
    set.Clear()
    fmt.Println("Set after clearing:", set.Iterate())
    fmt.Println("Contains 3?", set.Contains(3)) // false

    // Insert after clearing
    set.Insert(1)
    set.Insert(9)
    fmt.Println("Set after inserting 1 and 9:", set.Iterate())
    fmt.Println("Contains 1?", set.Contains(1)) // true
    fmt.Println("Contains 9?", set.Contains(9)) // true
}

Explanation

Insert Operation

• Time Complexity: O(1)
• Mechanism:
  • Check if x is within bounds (0 ≤ x < N).
  • Use timestamps[x] to check if x is already in the set.
    • If not, set timestamps[x] to the current timeStamp.
    • Assign x to values[size].
    • Update indices[x] with the current size.
    • Increment size.

Remove Operation

• Time Complexity: O(1)
• Mechanism:
  • Check if x is within bounds.
  • Use timestamps[x] to check if x is in the set.
    • If it is, find the index idx of x in values.
    • Swap values[idx] with the last element values[size-1].
    • Update indices for the swapped element.
    • Decrement size.
    • Optionally reset timestamps[x] (not necessary due to timeStamp logic).

Lookup (Contains) Operation

• Time Complexity: O(1)
• Mechanism:
  • Check if x is within bounds.
  • Return true if timestamps[x] == timeStamp, indicating that x is in the set.
  • Otherwise, return false.

Clear Operation

• Time Complexity: O(1)
• Mechanism:
  • Reset size to 0.
  • Increment timeStamp to invalidate all previous timestamps.
  • Handle potential overflow of timeStamp.

Iterate Operation

• Time Complexity: O(1) to retrieve the slice; O(k) to process all elements.
• Mechanism:
  • Return a slice of values up to size, which contains all current elements in the set.

Advantages of This Approach

• Constant-Time Operations: All set operations are performed in O(1) time.
• Efficient Memory Usage: Uses fixed-size arrays without additional memory overhead.
• No Hashing Overhead: Avoids the need for hash tables or maps.

Example Output

Set after inserts: [3 5 7]
Contains 5? true
Contains 2? false
Set after removing 5: [3 7]
Contains 5? false
Set after inserting 2: [3 7 2]
Contains 2? true
Set after clearing: []
Contains 3? false
Set after inserting 1 and 9: [1 9]
Contains 1? true
Contains 9? true

Understanding the Solution

Sparse Set Concept

A sparse set allows us to represent a set of integers from a fixed range efficiently. By using arrays and direct indexing, we can achieve constant-time operations.

• values[]: Stores the current elements in the set in a compact form.
• indices[]: For each possible element, stores its index in values[] if it's in the set.
• timestamps[]: Tracks whether an element is currently in the set based on the current timeStamp.

How TimeStamp Works

• Initialization: timeStamp starts at 1.
• Insertion: An element x is considered in the set if timestamps[x] == timeStamp.
• Clear Operation: Incrementing timeStamp effectively clears the set, as all previous timestamps become invalid.
• Overflow Handling: If timeStamp wraps around to 0, we handle it by ensuring it never equals 0.

Lookup Operation

• The Contains(x int) bool function allows us to check if an element x is present in the set in O(1) time.
• This is achieved by checking if timestamps[x] equals the current timeStamp.
• This operation is crucial for many applications where membership checks are frequent.

Why Use TimeStamp Instead of Resetting Arrays

Resetting the entire timestamps array on a Clear() operation would take O(N) time. By incrementing timeStamp, we avoid this overhead, keeping the Clear() operation at O(1).

Swapping Elements on Removal

When removing an element, we swap it with the last element in values[] to maintain a contiguous block of active elements. This allows for efficient iteration over the set.