Practice Problems: Implementing Queues and Custom BSTs in JavaScript | CodeSignal Learn

Practice Problems: Implementing Queues and Custom BSTs in JavaScript | CodeSignal Learn

Skip to main content

Introduction to Practice Problems

Welcome to the practical segment of our JavaScript programming journey! Today, we're applying the knowledge from past lessons to solve two practice problems using advanced JavaScript data structures: queues, deques, and binary search trees with custom class keys .

First Practice Problem: Implementing Queues with Deques

Consider an event-driven system, like a restaurant. Orders arrive, and they must be handled in the order they were received, following the First In, First Out (FIFO) principle. This principle makes it a perfect scenario for a queue or deque implementation in JavaScript. class Queue {constructor() {// Initializing an empty queue this.buffer = [];} // Adding (enqueueing) an item to the queue enqueue(val) {this.buffer.unshift(val);} // Removing (dequeuing) an item from the queue dequeue() {return this.buffer.pop();} // Checking if the queue is empty isEmpty() {return this.buffer.length === 0;} // Checking the size (number of items) in the queue size() {return this.buffer.length;}} // Example usage: const queue = new Queue(); queue.enqueue('order1'); queue.enqueue('order2'); console.log(queue.dequeue()); // Outputs 'order1' console.log(queue.isEmpty()); // Outputs false console.log(queue.size()); // Outputs 1 This code demonstrates the creation and operation of a Queue class, which leverages JavaScript arrays to efficiently implement a queue. The Queue class includes methods to enqueue (add) an item, dequeue (remove) an item, check if the queue is empty, and return the queue's size. Enqueue operations add an item to the beginning of the array (simulating the arrival of a new order), while dequeue operations remove an item from the end (simulating the serving of an order), maintaining the First In, First Out (FIFO) principle.

Analyzing the First Problem Solution

We've mimicked a real-world system by implementing a queue using JavaScript arrays. The enqueuing of an item taps into the FIFO principle, similar to the action of receiving a new order at the restaurant. The dequeuing serves an order, reflecting the preparation and delivery of the order.

Second Practice Problem: Using Binary Search Trees for a Leaderboard

Sign up

Join the 1M+ learners on CodeSignal

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

JavaScript

class Queue {
    constructor() {
        // Initializing an empty queue
        this.buffer = [];
    }

    // Adding (enqueueing) an item to the queue
    enqueue(val) {
        this.buffer.unshift(val);
    }

    // Removing (dequeuing) an item from the queue
    dequeue() {
        return this.buffer.pop();
    }

    // Checking if the queue is empty
    isEmpty() {
        return this.buffer.length === 0;
    }

    // Checking the size (number of items) in the queue
    size() {
        return this.buffer.length;
    }
}

// Example usage:
const queue = new Queue();
queue.enqueue('order1');
queue.enqueue('order2');
console.log(queue.dequeue()); // Outputs 'order1'
console.log(queue.isEmpty()); // Outputs false
console.log(queue.size());    // Outputs 1

For the second problem, envision a leaderboard for a video game. Players with their scores can be represented as objects of a custom class, then stored in a binary search tree (BST) for easy and efficient access using the @datastructures-js/binary-search-tree library.

Here is the new solution using a BST:

JavaScript

const { BinarySearchTree } = require('@datastructures-js/binary-search-tree');

class Player {
    constructor(name, score) {
        this.name = name;
        this.score = score;
    }

    // Comparator function for custom class
    compareTo(other) {
        if (this.score === other.score) {
            return this.name.localeCompare(other.name);
        }
        return this.score - other.score;
    }

    // Defining the string representation of Player object
    toString() {
        return `(${this.name}, ${this.score})`;
    }
}

class Leaderboard {
    constructor() {
        this.bst = new BinarySearchTree((playerA, playerB) => playerA.compareTo(playerB));
    }

    addPlayer(player) {
        this.bst.insert(player);
    }

    removePlayer(player) {
        this.bst.remove(player);
    }

    getTopPlayers() {
        const players = [];
        this.bst.traverseInOrder((node) => players.push(node.getValue()));
        return players;
    }
}

// Example usage:
const scores = new Leaderboard();
const player1 = new Player("John", 900);
const player2 = new Player("Doe", 1000);

scores.addPlayer(player1);
scores.addPlayer(player2);

for (const player of scores.getTopPlayers()) {
    console.log(player.toString()); // Outputs '(John, 900)' then '(Doe, 1000)'
}

This code snippet introduces a Player class for representing players in a video game, incorporating a custom comparator function to allow sorting by score (primary) and name (secondary). Instances of this class are then stored in a custom Leaderboard class using a binary search tree (BST) from the @datastructures-js/binary-search-tree library. The BST ensures that players are stored in sorted order based on their scores and names. This essential for functionalities like leaderboards, where players need to be ranked efficiently according to their performance.