Introduction to Efficient Queries Using TypeScript

Greetings, aspiring coders! Today, we're going to delve deep into the complexities of data structures, specifically how to handle queries efficiently using TypeScript . This is a common problem often encountered in numerous data science and algorithmic challenges. So let's gear up to unravel the mysteries of managing sorted sets and get our hands dirty with some interactive problem-solving!

Simulating Sorted Set Operations and Time Complexity

Before delving into the task, let's understand how we can achieve sorted set functionality in TypeScript. Although TypeScript, like JavaScript, does not have a built-in data structure specifically for sorted sets, we can use arrays and objects to simulate this behavior with additional type safety. To maintain a sorted set in TypeScript: We can store elements in an array and keep it sorted upon every insertion or deletion. This approach will involve operations like using a binary search to find the correct position for insertion or deletion: Inserting an element directly at the correct position using binary search takes O(N) in the worst case. Removing an element also involves finding its position using binary search, which takes O(N) in the worst case. Finding the smallest element greater than or equal to a given value can be achieved through a binary search, making this lookup operation O(log N) . Understanding these operations can help us utilize arrays and objects efficiently while leveraging TypeScript's strong type system.

Task Statement

We are tasked with designing a TypeScript function named processQueries that can process a series of distinct requests or queries efficiently. The queries comprise a list of two integers — the type of operation and the operand. There are three types of operations we'll handle: Adding an integer to the set (operation type 0) Removing an integer from the set (operation type 1). Whenever this operation is invoked, we can guarantee that the integer exists in the set. Finding the smallest integer that is greater than or equal to a given value (operation type 2). The function should return an array of numbers where each element is the current size of the set for operation types 0 or 1, and the smallest possible integer for operation type 2 . If such an integer does not exist, the function should return -1 . Ensure each part of the function has correct type annotations for function parameters and return types in TypeScript.

Join the 1M+ learners on CodeSignal

Be a part of our community of 1M+ users who develop and demonstrate their skills on CodeSignal

TypeScript

function processQueries(queries: [number, number][]): number[] {
    const sortedSet: number[] = [];
    const results: number[] = [];

function processQueries(queries: [number, number][]): number[] {
    const sortedSet: number[] = [];
    const results: number[] = [];

TypeScript

function binarySearchIndex(arr: number[], value: number): number {
    let left: number = 0;
    let right: number = arr.length - 1;

    while (left <= right) {
        const mid: number = left + Math.floor((right - left) / 2);
        if (arr[mid] < value) {
            left = mid + 1;
        } else if (arr[mid] > value) {
            right = mid - 1;
        } else {
            return mid; // Value found
        }
    }

    return left; // Appropriate insert position
}

function binarySearchIndex(arr: number[], value: number): number {
    let left: number = 0;
    let right: number = arr.length - 1;

    while (left <= right) {
        const mid: number = left + Math.floor((right - left) / 2);
        if (arr[mid] < value) {
            left = mid + 1;
        } else if (arr[mid] > value) {
            right = mid - 1;
        } else {
            return mid; // Value found
        }
    }

    return left; // Appropriate insert position
}

TypeScript

function processQueries(queries: [number, number][]): number[] {
    const sortedSet: number[] = [];
    const results: number[] = [];

    for (const query of queries) {
        const operation: number = query[0];
        const value: number = query[1];

        if (operation === 0) {
            const index: number = binarySearchIndex(sortedSet, value);
            sortedSet.splice(index, 0, value);
            results.push(sortedSet.length);
        } else if (operation === 1) {
            const index: number = binarySearchIndex(sortedSet, value);
            if (index !== sortedSet.length && sortedSet[index] === value) {
                sortedSet.splice(index, 1);
            }
            results.push(sortedSet.length);
        }
    }

    return results;
}

function processQueries(queries: [number, number][]): number[] {
    const sortedSet: number[] = [];
    const results: number[] = [];

    for (const query of queries) {
        const operation: number = query[0];
        const value: number = query[1];

        if (operation === 0) {
            const index: number = binarySearchIndex(sortedSet, value);
            sortedSet.splice(index, 0, value);
            results.push(sortedSet.length);
        } else if (operation === 1) {
            const index: number = binarySearchIndex(sortedSet, value);
            if (index !== sortedSet.length && sortedSet[index] === value) {
                sortedSet.splice(index, 1);
            }
            results.push(sortedSet.length);
        }
    }

    return results;
}

TypeScript

function processQueries(queries: [number, number][]): number[] {
    const sortedSet: number[] = [];
    const results: number[] = [];

    for (const query of queries) {
        const operation: number = query[0];
        const value: number = query[1];

        if (operation === 0) {
            const index: number = binarySearchIndex(sortedSet, value);
            sortedSet.splice(index, 0, value);
            results.push(sortedSet.length);
        } else if (operation === 1) {
            const index: number = binarySearchIndex(sortedSet, value);
            if (index !== sortedSet.length && sortedSet[index] === value) {
                sortedSet.splice(index, 1);
            }
            results.push(sortedSet.length);
        } else if (operation === 2) {
            let left: number = 0;
            let right: number = sortedSet.length - 1;
            let result: number = -1;

            while (left <= right) {
                const mid: number = Math.floor((left + right) / 2);
                if (sortedSet[mid] >= value) {
                    result = sortedSet[mid];
                    right = mid - 1;
                } else {
                    left = mid + 1;
                }
            }

            results.push(result);
        }
    }
    return results;
}

// Example usage
const queries: [number, number][] = [
    [0, 10],
    [2, 10],
    [0, 20],
    [1, 10],
    [2, 10]
];

console.log(processQueries(queries)); // Output: [1, 10, 2, 1, 20]

function processQueries(queries: [number, number][]): number[] {
    const sortedSet: number[] = [];
    const results: number[] = [];

    for (const query of queries) {
        const operation: number = query[0];
        const value: number = query[1];

        if (operation === 0) {
            const index: number = binarySearchIndex(sortedSet, value);
            sortedSet.splice(index, 0, value);
            results.push(sortedSet.length);
        } else if (operation === 1) {
            const index: number = binarySearchIndex(sortedSet, value);
            if (index !== sortedSet.length && sortedSet[index] === value) {
                sortedSet.splice(index, 1);
            }
            results.push(sortedSet.length);
        } else if (operation === 2) {
            let left: number = 0;
            let right: number = sortedSet.length - 1;
            let result: number = -1;

            while (left <= right) {
                const mid: number = Math.floor((left + right) / 2);
                if (sortedSet[mid] >= value) {
                    result = sortedSet[mid];
                    right = mid - 1;
                } else {
                    left = mid + 1;
                }
            }

            results.push(result);
        }
    }
    return results;
}

// Example usage
const queries: [number, number][] = [
    [0, 10],
    [2, 10],
    [0, 20],
    [1, 10],
    [2, 10]
];

console.log(processQueries(queries)); // Output: [1, 10, 2, 1, 20]

TypeScript

function processQueries(queries: [number, number][]): number[] {
    const sortedSet: number[] = [];
    const results: number[] = [];

TypeScript

function binarySearchIndex(arr: number[], value: number): number {
    let left: number = 0;
    let right: number = arr.length - 1;

    while (left <= right) {
        const mid: number = left + Math.floor((right - left) / 2);
        if (arr[mid] < value) {
            left = mid + 1;
        } else if (arr[mid] > value) {
            right = mid - 1;
        } else {
            return mid; // Value found
        }
    }

    return left; // Appropriate insert position
}

TypeScript

function processQueries(queries: [number, number][]): number[] {
    const sortedSet: number[] = [];
    const results: number[] = [];

    for (const query of queries) {
        const operation: number = query[0];
        const value: number = query[1];

        if (operation === 0) {
            const index: number = binarySearchIndex(sortedSet, value);
            sortedSet.splice(index, 0, value);
            results.push(sortedSet.length);
        } else if (operation === 1) {
            const index: number = binarySearchIndex(sortedSet, value);
            if (index !== sortedSet.length && sortedSet[index] === value) {
                sortedSet.splice(index, 1);
            }
            results.push(sortedSet.length);
        }
    }

    return results;
}

TypeScript

function processQueries(queries: [number, number][]): number[] {
    const sortedSet: number[] = [];
    const results: number[] = [];

    for (const query of queries) {
        const operation: number = query[0];
        const value: number = query[1];

        if (operation === 0) {
            const index: number = binarySearchIndex(sortedSet, value);
            sortedSet.splice(index, 0, value);
            results.push(sortedSet.length);
        } else if (operation === 1) {
            const index: number = binarySearchIndex(sortedSet, value);
            if (index !== sortedSet.length && sortedSet[index] === value) {
                sortedSet.splice(index, 1);
            }
            results.push(sortedSet.length);
        } else if (operation === 2) {
            let left: number = 0;
            let right: number = sortedSet.length - 1;
            let result: number = -1;

            while (left <= right) {
                const mid: number = Math.floor((left + right) / 2);
                if (sortedSet[mid] >= value) {
                    result = sortedSet[mid];
                    right = mid - 1;
                } else {
                    left = mid + 1;
                }
            }

            results.push(result);
        }
    }
    return results;
}

// Example usage
const queries: [number, number][] = [
    [0, 10],
    [2, 10],
    [0, 20],
    [1, 10],
    [2, 10]
];

console.log(processQueries(queries)); // Output: [1, 10, 2, 1, 20]