Forem: Ricardo Borges

Kafka fundamentals with a practical example

Ricardo Borges — Thu, 26 Dec 2024 21:17:15 +0000

Over the past few weeks, I’ve been diving into Kafka and taking notes along the way, which I decided to organize and structure into a blog post, on it, apart from concepts and tips there is a practical example built with NestJS and KafkaJs.

What is Kafka?

Apache Kafka is a distributed event-streaming platform designed to handle real-time events. It enables storing, processing, and retrieving large-scale, high-throughput, low-latency data streams, making it suitable for building real-time data pipelines and event-driven applications.

Key Features:

Event Streaming: Kafka organizes data into topics, which are ordered logs of events.
Distributed Architecture: Kafka is built for scalability and fault tolerance. It operates as a cluster of nodes called brokers and can distribute data across multiple servers.
Publish-Subscribe Model: Producers write messages to the topics, and consumers read messages from them. Kafka supports multiple consumers, allowing different applications to independently process the same data stream.
High Performance: Kafka is optimized for high throughput, processing millions of messages per second with low latency.
Durable Storage: Kafka stores messages on disk with configurable retention periods, ensuring data persistence and reliability.
Partitioning and Replication: Topics are divided into partitions for scalability and replicated across brokers for fault tolerance.
Replayability: Consumers can re-read messages by resetting their offset, enabling data reprocessing or recovery.
Integration and Ecosystem: Kafka integrates with various systems and has tools like Kafka Connect (for data integration) and Kafka Streams (for stream processing).

Advantages

Reliability: It ensures fault tolerance through data distribution, replication, and partitioning.
Scalability: Kafka can process massive data volumes and scale horizontally without downtime.
Durability: Messages are promptly stored, ensuring resilience and data persistence.
Performance: Kafka maintains high performance under extreme data loads, handling large volumes of data without downtime or data loss.

Disadvantages

These trade-offs are intentional design choices to maximize Kafka's performance but may pose challenges for use cases requiring greater flexibility:

Limited Flexibility: Kafka lacks support for extended queries, such as filtering specific data in reports. Consumers must handle these tasks, as Kafka retrieves messages by offsets in the order they are received.
Not Designed for Long-Term Storage: Kafka excels in streaming data but isn't suited for storing historical data for extended periods. Data duplication can make storage costly for large datasets.
No Wildcard Topic Support: Kafka doesn’t allow consuming from multiple topics using wildcard patterns (e.g., log-2024-*).

Use cases

Real-Time Analytics: Process and analyze data streams as they occur.
Event Sourcing: Record all changes to an application’s state as a sequence of events.
Log Aggregation: Collect and manage logs from distributed systems.
Data Pipelines: Stream data between systems reliably and efficiently.
IoT Applications: Handle sensor data from IoT devices in real-time.

How does Kafka work?

Kafka integrates the features of both queuing and publish-subscribe messaging models, offering consumers the advantages of each approach.

Queuing enables scalable data processing by distributing tasks across multiple consumer instances but traditional queues do not support multiple subscribers.
The publish-subscribe model supports multiple subscribers but cannot distribute tasks among multiple worker processes as each message is sent to all subscribers.

Kafka employs a partitioned log system to combine the benefits of queuing and publish-subscribe models. Logs, which are ordered sequences of records, are divided into partitions, with each partition assigned to different subscribers (consumers). This setup enables multiple subscribers to share a topic while maintaining scalability.

Events, Topics, and Partitions

We have seen that Kafka is a platform designed to handle real-time events, before talking about how those events are handled we need to have a definition for them:

An event is an action, incident, or change that's recorded applications, for example, a payment, a website click, or a temperature reading.

Events in Kafka are modeled as key/value pairs, where both keys and values are serialized into byte sequences.

Values often represent serialized domain objects or raw inputs, such as sensor outputs or other application data. They encapsulate the core information being transmitted in the Kafka event.
Keys can be complex domain objects, however are often simple types like strings or integers. Instead of uniquely identifying an individual event (as a primary key does in a relational database), keys typically identify entities within the system, such as a specific user, order, or connected device.

Kafka organizes events into ordered logs called topics. When an external system writes an event to Kafka, it is appended to the end of a topic. Messages remain in topics for a configurable duration, even after being read. Unlike queues, topics are durable, replicated, and fault-tolerant, efficiently storing event records. However, logs can only be scanned sequentially, not queried.

Topics are stored as log files on disk, however, disks have limitations such as finite size and I/O. To overcome this, Kafka allows topics to be divided into partitions, breaking a single log into multiple logs that can be distributed across different servers. This partitioning enables Kafka to scale horizontally, enhancing its capacity to handle large volumes of events and high throughput.

Kafka assigns messages to partitions based on whether they have a key:

No Key: Messages are distributed round-robin across all partitions, ensuring an even data distribution but not preserving message order.
With Key: The partition is determined by hashing the key, ensuring that messages with the same key always go to the same partition and maintain their order.

Brokers

Kafka operates as a distributed data infrastructure using nodes called brokers, which collectively form a Kafka cluster. Brokers can run on bare metal hardware, a cloud instance, in a container managed by Kubernetes, in Docker on your laptop, or wherever JVM processes can run.

Brokers focus on:

Writing new events to partitions.
Serving reads from partitions.
Replicating partitions across brokers.

They do not perform message computation or topic-to-topic routing, keeping their design simple and efficient.

Replication

Kafka ensures data durability and fault tolerance by replicating partition data across multiple brokers. The primary copy of a partition is the leader replica, while additional copies are follower replicas. Data is written to the leader, which automatically replicates updates to the followers.

This replication process ensures:

Data safety, even in the event of broker or storage failures.
Automatic failover, where another replica takes over as leader if the current leader fails.

Developers benefit from these guarantees without needing to manage replication directly, as Kafka handles it transparently.

Producers

A Kafka producer is a client application that sends (publishes) data to Kafka topics. It’s responsible for creating and transmitting messages (records) to the Kafka cluster. Producers determine the topic and partition where messages will be stored based on their configuration and the presence of a message key. Producers are responsible for, but not limited to:

Message Composition:
- Each message consists of a key (optional), a value (the actual data), and metadata.
- The key determines the partition for the message, ensuring order for messages with the same key.
Partition Assignment:
- If a key is provided, the producer uses a hashing algorithm to determine the partition.
- Without a key, messages are distributed across partitions in a round-robin manner for load balancing.
Compression:

Producers can compress messages to reduce network bandwidth and storage use.

Consumers

A Kafka consumer is a client application that reads messages from Kafka topics, it retrieves messages from Kafka partitions at their own pace, allowing for real-time or batch processing of data. Notice that Kafka does not push messages to consumers, they pull messages from Kafka partitions by requesting the data.

Consumers also keep track of the offsets they have processed. Offsets can be committed automatically or manually, ensuring data is not lost if a consumer fails. This allows for flexible consumption, including replaying messages by resetting the offset.

Consumer groups

A consumer group is a set of consumers that cooperate to consume data from some topics, which allows for distributed processing of a topic's messages.

Partitions of a topic are divided among the consumers in the group, ensuring each message is processed by only one consumer within the group. Multiple consumer groups can independently consume the same topic without interference.

When a new consumer joins a group or an existing consumer fails, Kafka reassigns partitions among the consumers in the group to ensure all partitions are covered.

Serialization and Deserialization

Serialization and deserialization in Kafka are about converting data between its original format and a byte array for transmission and storage, allowing producers and consumers to communicate efficiently.

Serialization

Is the process of converting an object or data structure into a byte stream so it can be transmitted or stored. Before a producer sends data to a Kafka topic, it serializes the data (key and value) into byte arrays.

Common Serialization Formats:

JSON: Human-readable, widely compatible.
Avro: Compact and efficient, schema-based.
Protobuf: Compact, schema-based, and language-agnostic.
String: Simple text-based serialization.
Custom Serialization: For application-specific needs.

Deserialization

Is the reverse process, where a byte stream is converted back into its original object or data structure. When a consumer reads data from a Kafka topic, it deserializes the byte array back into a usable format for processing.

Compression

Compression is reducing the size of messages before they are stored or transmitted. It optimizes storage usage, reduces network bandwidth consumption, and improves overall performance by sending smaller payloads between producers, brokers, and consumers.

When a producer sends messages to a Kafka topic, it can compress the message before the transmission. The compressed message is stored on brokers as-is and decompressed by consumers when they read the messages.

Advantages

Reduced Network Bandwidth: Smaller payloads mean less data is transmitted over the network.
Lower Storage Requirements: Compressed messages take up less space on disk.
Improved Throughput: Smaller messages allow for faster data transfer and processing.

When to use?

Use cases with large message sizes: Compression greatly reduces data size.
High-throughput systems: Reduces the strain on network and storage resources.
Batching: Compression works best when producers batch multiple messages together.

While compression saves resources, it's essential to balance the trade-off between CPU usage and compression benefits, choosing the codec that suits your use case.

Supported Compression Types

None: No compression (default).
Gzip: High compression ratio but higher CPU usage.
Snappy: Balanced compression speed and CPU usage, suitable for real-time use cases.
LZ4: Faster compression and decompression, optimized for low-latency systems.
Zstd: High compression ratio with better performance than Gzip, supported in newer Kafka versions.

Tuning

Optimizing Apache Kafka's performance involves fine-tuning various components to balance throughput and latency effectively. This article only scratches the surface of this subject, here are some aspects to consider when tuning Kafka:

Partition Management:
- Partition Count: Increase the number of partitions to enhance parallelism and throughput. However, avoid excessive partitions to prevent management overhead. Align the number of partitions with your consumer capabilities and desired consumption rate.
Producer Configuration:
- Batching: Configure batch.size and linger.ms to enable efficient batching of messages, reducing the number of requests and improving throughput.
- Compression: Implement compression (e.g., compression.type=snappy) to decrease message size, reducing network and storage usage. Be mindful of the additional CPU overhead introduced by compression.
Consumer Configuration:
- Fetch Settings: Adjust fetch.min.bytes and fetch.max.wait.ms to control how consumers retrieve messages, balancing latency and throughput according to your application's needs.

Practical example

Imagine an application that records the temperature in a room and transmits this data using Kafka, where another application processes it. For simplicity, we'll focus exclusively on the Kafka aspect, with both the producer and consumer implemented within the same application. In this scenario, each recorded temperature at a specific moment represents an event:

{
  temperature: 42,
  timeStamp: new Date(),
};

All the code will be in this repository.

First, we need a Kafka broker, but instead of installing Kafka in our machine let’s just this Docker Kafka image.

Start by pulling that image:

docker pull apache/kafka

Then run it mapping the port that Kafka listens on the same port on our machine:

docker run -d -p 9092:9092 --name broker apache/kafka:latest

That’s it, we have a Kafka broker running, before continuing you might want to play around with it by creating topics, sending and consume messages, to do that just follow the instructions on that image page.

To build our application we’re going to use NestJS with KafkaJS, start by creating the app with Nest CLI

nest new my-nest-project

Inside the project folder install kafkajs

npm i kafkajs

And generate the following modules

nest g mo kafka

nest g mo producer

nest g mo consumer

nest g mo temperature

The Kafka module will handle all Kafka-specific operations, including managing consumer and producer classes for connecting, disconnecting, sending, and receiving messages. This will be the only module directly interacting with the kafkajs package.

The Producer and Consumer modules will act as interfaces between the pub-sub platform (Kafka, in this case) and the rest of the application, abstracting platform-specific details.

The Temperature module will manage the events. It doesn't need to know which pub-sub platform is being used, it only requires a consumer and a producer to function.

With the modules created, let’s also create a folder src/interface and add the following interfaces in it:

// src/interfaces/producer.interface.ts

export interface IProducer {
  produce: (message: any) => Promise<void>;
  connect: () => Promise<void>;
  disconnect: () => Promise<void>;
  isConnected: () => boolean;
}

// src/interfaces/consumer.interface.ts

export type ConsumerMessage = {
  key?: string;
  value: any;
};

export type OnMessage = (message: ConsumerMessage) => Promise<void>;

export interface IConsumer {
  connect: () => Promise<void>;
  disconnect: () => Promise<void>;
  consume: (onMessage?: OnMessage) => Promise<void>;
  isConnected: () => boolean;
}

In src/kafka/ folder add the producer and consumer classes that implement those interfaces:

// src/kafka/kafka.producer.ts

export class KafkaProducer implements IProducer {
  private readonly logger = new Logger(KafkaProducer.name, { timestamp: true });
  private readonly kafka: Kafka;
  private readonly producer: Producer;
  private connected: boolean = false;

  constructor(
    private readonly broker: string,
    private readonly topic: string,
  ) {
    // The client must be configured with at least one broker
    this.kafka = new Kafka({
      brokers: [this.broker],
    });
    this.producer = this.kafka.producer();
  }

  async produce(
    message: Message,
    compression?: CompressionTypes,
    acks?: number,
    timeout?: number,
  ) {
    // To produce, at least a topic and a list of messages must be provided
    await this.producer.send({
      topic: this.topic,
      messages: [message],
      compression,
      timeout,
      acks,
    });
  }

  // To produce a message, the producer must be connected
  async connect() {
    try {
      // Just hooking up some logs in the producer events
      // And storing the connection status
      this.producer.on('producer.connect', () => {
        this.logger.log(
          `producer connected. broker: ${this.broker} topic: ${this.topic}`,
        );
        this.connected = true;
      });

      this.producer.on('producer.disconnect', () => {
        this.logger.log(
          `producer disconnected. broker: ${this.broker} topic: ${this.topic}`,
        );
        this.connected = false;
      });

      // Connect to Kafka
      await this.producer.connect();
    } catch (err) {
      this.logger.error(
        `failed to connect to kafka. broker: ${this.broker} topic: ${this.topic}`,
        err,
      );
    }
  }

  async disconnect() {
    await this.producer.disconnect();
  }

  isConnected(): boolean {
    return this.connected;
  }
}

// src/kafka/kafka.cosumer.ts

export class KafkaConsumer implements IConsumer {
  private readonly logger = new Logger(KafkaConsumer.name, { timestamp: true });
  private readonly kafka: Kafka;
  private readonly consumer: Consumer;
  private connected: boolean = false;

  constructor(
    private readonly broker: string,
    private readonly topic: string,
    private readonly groupId: string,
  ) {
    if (this.broker && this.topic && this.groupId) {
      // The client must be configured with at least one broker
      this.kafka = new Kafka({
        brokers: [this.broker],
      });
      this.consumer = this.kafka.consumer({ groupId: this.groupId });
    } else {
      this.logger.warn('Broker, topic and groupId must be provided');
    }
  }

  // The onMessage function will be called when a message is received
  async consume(onMessage: OnMessage) {
    // Here we subscribe to the topic ...
    await this.consumer.subscribe({ topic: this.topic });

    // ... and handle the messages
    await this.consumer.run({
      eachMessage: async (payload) => {
        try {
          this.logger.log(
            `message: ${payload.message.value.toString()} (topic: ${payload.topic}, partition: ${payload.partition})`,
          );

          await onMessage({
            key: payload.message.key?.toString(),
            value: payload.message.value.toString(),
          });
        } catch (err) {
          this.logger.error('error on consuming message', err);
        }
      },
    });
  }

  // To consume, the consumer must be connected
  async connect() {
    try {
      // Just hooking up some logs in the consumer events
      // And storing the connection status
      this.consumer.on('consumer.connect', () => {
        this.logger.log(
          `consumer connected. broker: ${this.broker} topic: ${this.topic}`,
        );
        this.connected = true;
      });

      this.consumer.on('consumer.disconnect', () => {
        this.logger.log(
          `consumer disconnected. broker: ${this.broker} topic: ${this.topic}`,
        );
        this.connected = false;
      });

      await this.consumer.connect();
    } catch (err) {
      this.logger.error(
        `failed to connect to kafka. broker: ${this.broker} topic: ${this.topic}`,
        err,
      );
    }
  }

  async disconnect() {
    await this.consumer.disconnect();
  }

  isConnected(): boolean {
    return this.connected;
  }
}

Don’t forget to export these classes in kafka.module.ts

// src/kafka/kafka.module.ts

@Module({
  imports: [],
  providers: [KafkaProducer, KafkaConsumer],
  exports: [KafkaProducer, KafkaConsumer],
})
export class KafkaModule {}

As it is now we could go to the temperature module and instantiate those Kafka classes and start using them. However, it would be better if the temperature module didn’t have to worry about which pub-sub platform it was using. Instead, it should simply work with an injected producer and/or consumer, focusing solely on sending and receiving messages, regardless of the underlying platform. This way, if we decide to switch to a different pub-sub platform in the future, we won’t need to make any changes to the temperature module.

To achieve this abstraction, we can create Producer and Consumer classes that handle the specifics of Kafka’s Producer and Consumer implementations. Let’s start with the Producer:

// src/producer/producer.service.ts

@Injectable()
export class ProducerService implements OnApplicationShutdown {
  // Expects any producer that implements the IProducer interface
  private readonly producer: IProducer;

  constructor(
    @Inject('broker') broker: string,
    @Inject('topic') topic: string,
  ) {
    this.producer = new KafkaProducer(broker, topic);
  }

  /** The produce() and message can receive more parameters,
   * refer to produce method in src/kafka/kafka.producer.ts
   */
  async produce(message: { key?: string; value: string }) {
    if (!this.producer.isConnected()) {
      await this.producer.connect();
    }
    await this.producer.produce(message);
  }

  async onApplicationShutdown() {
    await this.producer.disconnect();
  }
}

// src/producer/producer.module.ts

@Module({
  imports: [KafkaModule],
  providers: [
    ProducerService,
    {
      provide: 'broker',
      useValue: 'default-broker-value',
    },
    {
      provide: 'topic',
      useValue: 'default-topic-value',
    },
  ],
  exports: [ProducerService],
})
export class ProducerModule {}

Now, the Consumer:

// src/consumer/consumer.service.ts

@Injectable()
export class ConsumerService implements OnApplicationShutdown {
  // Expects any consumer that implements the IConsumer interface
  private readonly consumer: IConsumer;

  constructor(
    @Inject('broker') broker: string,
    @Inject('topic') topic: string,
    @Inject('groupId') groupId: string,
  ) {
    this.consumer = new KafkaConsumer(broker, topic, groupId);
  }

  async consume(onMessage: OnMessage) {
    if (!this.consumer.isConnected()) {
      await this.consumer.connect();
    }
    await this.consumer.consume(onMessage);
  }

  async onApplicationShutdown() {
    await this.consumer.disconnect();
  }
}

// src/consumer/consumer.module.ts

@Module({
  imports: [KafkaModule],
  providers: [
    ConsumerService,
    {
      provide: 'broker',
      useValue: 'default-broker-value',
    },
    {
      provide: 'topic',
      useValue: 'default-topic-value',
    },
    {
      provide: 'groupId',
      useValue: 'default-groupId-value',
    },
  ],
  exports: [ConsumerService],
})
export class ConsumerModule {}

Now, we can focus on building the temperature module. In the temperature.service.ts file, we’ll create a method to register a temperature, which in this example will simply send the temperature data to the broker using a producer. Additionally, we’ll implement a method to handle incoming messages for demonstration purposes.

These methods can be invoked by another service or a controller. However, for simplicity, in this example, we’ll call them directly when the application starts, utilizing the onModuleInit method.

// src/temperature/temperature.service.ts

@Injectable()
export class TemperatureService implements OnModuleInit {
  private readonly logger = new Logger(TemperatureService.name, {
    timestamp: true,
  });
  private readonly producerService: ProducerService;
  private readonly consumerService: ConsumerService;

  constructor(private readonly configService: ConfigService) {
    this.producerService = new ProducerService(
      this.configService.get('BROKER'),
      this.configService.get('TOPIC'),
    );

    this.consumerService = new ConsumerService(
      this.configService.get('BROKER'),
      this.configService.get('TOPIC'),
      'temperature-consumer',
    );
  }

  async registerTemperature(temperature: number) {
    const message = {
      temperature,
      timeStamp: new Date(),
    };

    await this.producerService.produce({
      value: JSON.stringify(message),
    });
  }

  async handleTemperatureReading() {
    await this.consumerService.consume(async (message: ConsumerMessage) => {
      this.logger.log(message);
      // TODO  handle consumed message
    });
  }

  // Called when the application starts, only for testing purposes
  async onModuleInit() {
    await this.registerTemperature(30);
    // await this.handleTemperatureReading();
  }
}

// src/temperature/temperature.module.ts

@Module({
  imports: [ProducerModule, ConsumerModule],
  providers: [TemperatureService],
})
export class TemperatureModule {}

That's it! With the broker running in the Docker container, you can start the application to send and receive messages. Additionally, you can open a shell inside the broker container using the following command:

docker exec --workdir /opt/kafka/bin/ -it broker sh

From there, you can interact with the broker directly and send messages to the application, receive messages from it, create new topics, etc.

This is the repository with the code of this example.

How to set up Commitzen with Husky

Ricardo Borges — Wed, 11 Oct 2023 20:24:00 +0000

Conventional commits specification contains a set of rules for creating an explicit commit history, which makes it easier to write automated tools on top of, for example, semantic release. You can manually follow this convention in your project or use a tool to assist you, such as Commitizen.

There are some ways to use Commitizen in your project, in this post, I will show you how to set it up with Husky, so whenever you run git commit, you'll be prompted to fill out any required commit fields at commit time.

To start, install Commitzen and Husky packages:

npm i commitizen husky --save-dev

Next, initialize your project to use the cz-conventional-changelog adapter

commitizen init cz-conventional-changelog --save-dev --save-exact

That command will do the following:

Install the cz-conventional-changelog adapter npm module;
Save it to package.json's dependencies or devDependencies;
Add the config.commitizen key to the root of your package.json.

Finally, in the package.json file, set a Husky´s hook to trigger Commitzen on commit command

"husky": {
  "hooks": {
    "prepare-commit-msg": "exec < /dev/tty && npx cz --hook || true"
  }
}

And that´s it, you are all set. Make some changes to your code, run git commit, and follow the Commitzen instructions.

OOP Concepts in practice using TypeScript

Ricardo Borges — Thu, 09 Sep 2021 14:05:21 +0000

The idea of this post is to modify a very small part of imaginary software by applying OOP concepts. For this post, I'll presume that you are familiar with OOP and the definitions of classes, objects, methods, and attributes. I'll use as an example an audio streaming software in its very early stages.

We'll start with this:

An Album and a Track class, and another file that plays a track.

export class Album {
  name: string;

  constructor(name: string) {
    this.name = name;
  }
}

export class Track {
  name: string;
  length: number;
  album: Album;

  constructor(name: string, length: number, album: Album) {
    this.name = name;
    this.length = length;
    this.album = album;
  }
}

// meanwhile in another file ...

function play() {
    // Finds the track 
    // Play it
}

We will start to apply the OOP concepts, but we'll keep it simple, especially because the goal here is to understand those concepts and not to build a real audio streaming API.

Encapsulation

All those properties in the Track class are accessible by anyone, let's change that by encapsulating them. Encapsulation is a mechanism to hide information, those information are the classes members, like properties and methods, this is achieved by using the modifiers public, protected, and private.

public members can be accessed anywhere, this is the default modifier.
protected members are visible inside of the class they’re declared in and its subclasses.
private members are only visible inside of the class they’re declared in.

To encapsulate all those properties we follow these steps:

Add modifier private
Add _ before the property name, for example, _name
Implement the accessors get and set. These methods will be invoked whenever you try to get o set the property value.

Making all properties private the Track class will look like this:

export class Track {
  private _name: string;
  private _length: number;
  private _album: Album;

  constructor(name: string, length: number, album: Album) {
    this._name = name;
    this._length = length;
    this._album = album;
  }

  get name(): string {
    return this._name;
  }

  set name(name: string) {
    this._name = name;
  }

  get length(): number {
    return this._length;
  }

  set length(length: number) {
    this._length = length;
  }

  get album(): Album {
    return this._album;
  }

  set album(album: Album) {
    this._album = album;
  }
}

Abstraction

Abstraction is about hiding complexity details from the user, for example, to drive a car you don't need to know how its engine works, so in a car it's abstracted and an interface (steering wheel, pedals, gear shift, etc.) is provided to you, and you only need to know how to operate that interface.

Take a look at how a track is being played, it first finds the track, and then plays it. Seems simple, now suppose we have to do the same all over places whenever we need to play a track, that would be redundant, but there are other problems, everyone who is writing a code to play a track need to know how to do it, and what if something in playing track changes? We would have to change it in many places.

This is an opportunity to abstract that logic, we do that by moving it to inside the track class, and now whenever a track needs to be played, anyone only has to call that play method without knowing its details:

export class Track {
  private _name: string;
  private _length: number;
  private _album: Album;

  constructor(name: string, length: number, album: Album) {
    this._name = name;
    this._length = length;
    this._album = album;
  }

  get name(): string {
    return this._name;
  }

  set name(name: string) {
    this._name = name;
  }

  get length(): number {
    return this._length;
  }

  set length(length: number) {
    this._length = length;
  }

  get album(): Album {
    return this._album;
  }

  set album(album: Album) {
    this._album = album;
  }

    function play() {
        // Play it
    }
}

// To instantiate and play a track
const album = new Album("Rocks");
const track = new Track("Combination", 264, album);

track.play();

Inheritance

Suppose that now our audio streaming software needs to add support to podcasts, and these podcasts have episodes, how would we do that? We could simply add a Podcast class, and a type property in track class:

export class Podcast {}

export class Track {
  private _name: string;
  private _length: number;
    private _type: string; // track or episode
  private _album?: Album;
  private _podcast?: Podcast;


    ...
}

That works but it is more difficult to maintain, we have to consider the type in this class behaviors, like in the play method, and if we have to support another type of media, we would have to modify everything again, besides that approach goes against two SOLID's principle at least, but this is a topic for another post.

So, how can we solve this problem? Enters the inheritance: A mechanism that allows us to create class hierarchies, where a subclass can inherit properties and behaviors from its superclass. This is great for reusability.

So, the solution I suggest is the following:

First, create an Audio class, with the properties and behaviors that are common for tracks and episodes, this will be our superclass:

export class Audio {
  private _name: string;
  private _length: number;

  constructor(name: string, length: number) {
    this._name = name;
    this._length = length;
  }

    /** getters and setters */

    function play() {
        // Play it
    }
}

Then, the Track class will derive from the Audio class, meaning it will inherit the Audio class properties and behaviors:

export class Track extends Audio {
  private _album: Album;

  constructor(name: string, length: number, album: Album) {
    super(name, length);
    this._album = album;
  }

  get album(): Album {
    return this._album;
  }

  set album(album: Album) {
    this._album = album;
  }
}

The extends keyword means that the Track class is inheriting from the Audio class, and since Track is extending another class, we have to call super in the constructor, even if there are not any properties to pass to the superclass. Also, super can be used to call the parent class methods.

It's worthy to note that a superclass can be called a parent class, and a subclass can also be called a child class.

Finally, we create the Podcast and Episode classes, Episode will extend Audio class too:

export class Podcast {
  name: string;

  constructor(name: string) {
    this.name = name;
  }
}

export class Episode extends Audio {
  private _podcast: Podcast;

  constructor(name: string, length: number, podcast: Podcast) {
    super(name, length);
    this._podcast = podcast;
  }

  get podcast(): Podcast {
    return this._podcast;
  }

  set podcast(podcast: Podcast) {
    this._podcast = podcast;
  }
}

Polymorphism

Now suppose that for some reason, when users close the streamer and open it again, only podcasts episodes need to play where they left off, and tracks have to start from the beginning. As you know the play method is in the Audio class, so it is the same for both episodes and tracks, how do we implement this feature? Polymorphism comes to the rescue!

Polymorphism is the idea of an object can take multiple forms as the word suggests, we'll use it to make the play method perform differently for tracks and episodes. In practice, we do that by overriding it in the Episode class, which means we implement the play method in the Episode class differently from how it is implemented in the superclass:

export class Episode extends Audio {

    /** everything else remains the same */

    function play() {
      // Check where it left off
      // Play it
    }
}

Another way to achieve polymorphism is to overload methods, those are methods with the same name but different signatures, like different data types or number of arguments, however, this is different in TypeScript, to overload a method we have to add optional arguments or overload function declarations in an interface and implement the interface.

This is it, the idea was to briefly explain what each one is and provide an example. I wanted to focused on these four concepts and left other concepts out, therefore there is still room to improve this implementation.

Data Structures in TypeScript - Hash Table

Ricardo Borges — Thu, 02 Sep 2021 16:39:11 +0000

A Hash table is a data structure with a highly efficient lookup, which store key values pairs. Each key is generated by a hash function based on the value being stored. Also, the hash table has to handle collisions that happens when the same key is generated for different values.

  [1]
  [2] = ["A"] // value A store in the key 2
  [3]
  [4] = ["B"]

Whenever we need to retrieve a value we use its key, so this operation will be done in a constant time, considering that a good hash function is being used and the values are uniformly distributed across the hash table, which means fewer collisions. Inserting a value into a hash table, is pretty straightforward, just generate the key, and use it to find the right position in the hash table.

A basic hash function

A hash function should be easy to compute because it will be used whenever is necessary to insert or search a value, also this function has to provide uniform distribution across the hash table in order to avoid clustering which would affect the hash table performance.

For this example, our hash table will store strings, so the hash function will sum the ASCII values of each character, then it will divide that sum by the size of the hash table and get the reminder using the modulo operator (%), the result will be the key.

// hash function
hash(value: string): number {
  const sum = value
      .split("")
      .reduce((acc: number, char: string) => acc + char.charCodeAt(0), 0);

  // force sum into the hash table size
  return sum % this.size;
}

How to handle collisions

Collisions happen when the same key is generated for different values, a common strategy to handle collisions is Separate chaining:, instead of storing the value directly in the hash table, we store it in a Linked List, and the generated key points to that Linked list. If there were too many collisions, searching a value would take a linear time complexity O(n) instead of O(1), this time can be reduced to O(log n) using another data structure like a Binary Search Tree.

[1]
[2] = ["A"] ->
[3]
[4] = ["B"] -> ["C"] -> ["D"] -> // collisions happened, so these 3 values are in the same linked list

Implementation

Here is an implementation of a Hash Table in TypeScript

class HashTable {
  private size: number;
  private data: LinkedList<string>[] = [];

  constructor(size: number) {
    this.size = size;
  }

  hash(value: string): number {
    const sum = value
      .split("")
      .reduce((acc: number, char: string) => acc + char.charCodeAt(0), 0);

    // force sum into the hash table size
    return sum % this.size;
  }

  insert(value: string): void {
    const index = this.hash(value);

    if (!this.data[index]) {
      this.data[index] = new LinkedList<string>(
        (a: string, b: string) => a === b
      );
    }

    this.data[index].append(value);
  }

  search(value: string): string | null {
    const index = this.hash(value);

    if (this.data[index]) {
      return this.data[index].search(value)!.data;
    }

    return null;
  }
}

const hashTable = new HashTable(10);

hashTable.insert("aabb");
hashTable.insert("bbcc");
hashTable.insert("abcd");

console.log(hashTable.search("abcd"));

Starting with search algorithms

Ricardo Borges — Thu, 26 Aug 2021 18:18:28 +0000

Search algorithms that are used to retrieve information from a data structure, in this post I'll describe 3 search algorithms to find an element in lists.

Linear Search

Linear search is the most basic and easier to understand search algorithm, it simply starts from the first element in the list, and check each element to see if it is the element we are searching for, if the element is found returns its position in the list, else returns -1, null or undefined. Since it goes through the entire list, its time complexity is O(n).

function linearSearch(list:number[], n:number): number {
  for(let i=0; i< list.length; i++) {
    if(list[i] === n) return i
  }
}

const list = [2,6,4,8,9,0,1,5]
console.log(linearSearch(list, 1)) // 6

What if we are given a sorted list? The next two algorithms work on sorted lists and are faster than the Linear Search algorithm.

Jump Search

Instead of check element-by-element, This algorithm search block-by-block, so it checks fewer elements.

We start defining a block size
Starting from the beginning of the list, we check the last element of each block, if the element is smaller than the value we are looking for, we jump to the next block.
But, if the last element of the current block is greater than the value we are looking for, we do a linear search in that block.

Jump Search time complexity in the average and worst cases is O(√ n).

function jumpSearch(list:number[], n:number): number {
  const blockSize = Math.floor(Math.sqrt(list.length))
  const start = 0

  while(list[start+blockSize-1] < n) {      
    if(start + blockSize >= list.length) {
        start += list.length - 1 - start
    }else {
        start += blockSize
    }
  }

  for(let i=start; i < start+blockSize-1; i++) {
    if(list[i] === n) return i
  }
}

const sortedList = [1,2,3,4,5,6,7,8,9,10]
console.log(jumpSearch(sortedList, 5)) // 4

Binary Search

This algorithm is also meant for sorted lists, it uses a divide-and-conquer technique, which means it divides the problem into smaller parts that are easier to solve.

Start by checking the element in the middle of the lists, if this element is the element we are searching for returns its position.
If that middle element is greater than the element we are searching for, repeat the first step for the right half.
But, if that middle element is smaller, repeat the first step for the left half.

Notice that this algorithm keeps dividing the sublists into even smaller ones checking only the element in the middle of each sublist, and it might, eventually, wind up with a sublist that contains a single element. Since this algorithm is halving the list at each iteration its time complexity is O(log n).

Worth mentioning that this algorithm is also implemented for a Binary Search Tree.

Here's an recursive implementation of Binary Search without any auxiliary data structures:

function binarySearch(list:number[], n:number, low:number, high:number): number {
  // base case
  if(low > high) return

  let middle = Math.floor((low + high) / 2)

  if(list[middle] === n) return middle

  if(n < list[middle]) return binarySearch(list, n, low, middle-1)

  if(n > list[middle]) return binarySearch(list, n, middle+1, high)
}

const sortedList = [1,2,3,4,5,6,7,8,9,10]
console.log(binarySearch(sortedList, 3, 0, sortedList.length - 1))

Quick Sort

Ricardo Borges — Thu, 19 Aug 2021 16:57:52 +0000

Quick Sort is an in-place sorting algorithm that uses a divide-and-conquer technique to sort a given list, which means it breaks down a problem into smaller parts in order to be simpler to solve and doesn't uses auxiliary data structures.

Quick Sort starts by selecting an element from the list to be the pivot, usually is the first or last element.

Next, rearrange the other elements, so all elements smaller than the pivot go to its left and all elements greater than the pivot goes to its right.

This process is repeated for the right and left sides of the pivot.

Implementation

Here is a recursive implementation of Quick Sort in TypeScript.

/**
 * swap function
 */
function swap(arr: number[], i: number, j: number) {
  [arr[i], arr[j]] = [arr[j], arr[i]];
}

/**
 * recursive function
 */
function quickSort(arr: number[], start: number, end: number) {
  // base case
  if (start >= end) return;

  // rearrange the entire array based on a pivot
  // this pointer is the middle of the array, it will be explained in the next function
  const pointer = rearrange(arr, start, end);

  // rearrange the left and right side of the pivot
  quickSort(arr, start, pointer - 1);
  quickSort(arr, pointer + 1, end);
}

/**
 * function to rearrange the array based on a pivot
 */
function rearrange(arr: number[], start: number, end: number) {
  // choose last element to be the pivot
  const pivot = arr[end];

  // this pointer works like a placeholder for the pivot, at the end, it will be in the middle of the array, and will swap with the pivot that is in the end
  let pointer = start;

  for (let i = start; i < end; i++) {
    if (arr[i] < pivot) {
      swap(arr, pointer, i);

      // increment pointer, so it stays ahead of the elements that are smaller than the pivot
      pointer++;
    }
  }

  // put the pivot in the middle
  swap(arr, pointer, end);
  return pointer;
}

const arr = [3, 7, 2, 6, 5];
quickSort(arr, 0, arr.length - 1);
console.log(arr); // 2, 3, 5, 6, 7

The important part of Quick Sort is the choice of the pivot, since a bad choice leads to the worst-case time complexity, speaking of which, the average case time complexity of this algorithm is O(n log n), while in the worst case is O(n²), however, the worst-case can be avoided using a randomized version of this algorithm. Also, unlike Merge Sort, Quick Sort is an in-place algorithm, which gives it the advantage of having a constant space complexity O(1).

Merge Sort

Ricardo Borges — Thu, 12 Aug 2021 16:55:45 +0000

Merge sort is a sorting algorithm that uses a divide-and-conquer technique to sort a given list, which means it breaks down a problem into smaller parts in order to be simpler to solve.

Merge Sort starts by splitting the list into halves, and continues to split those sublists until only sublists with a single element are left. Then merge those sublists into sorted sublists, and continue doing so until end up with a single sorted list.

                [4, 3, 2, 1];
                |           |
               |             |
Divide      [4,3]           [2,1]
            |   |           |   |
           |     |         |     |
         [4]     [2]     [2]     [1]
           |     |         |     |
            |   |           |   |
Conquer     [2,4]           [1,2]
                |           |
                 |         |
                 [1, 2, 3, 4]

Implementation

This algorithm can be implemented with two functions, one to divide and another to merge :

/**
 * Function to merge
 **/
function merge(left: number[], right: number[]): number[] {
  const sorted = [];

  // until one of the sublists has a element, insert them into the sorted list
  while (left.length && right.length) {
    if (left[0] < right[0]) {
      sorted.push(left.shift());
    } else {
      sorted.push(right.shift());
    }
  }

  // one of the sublists can still have leftover elements, so we need to merge them
  return [...sorted, ...left, ...right];
}

/**
 * Function to divide
 **/
function mergeSort(list: number[]): number[] {
  // base case
  if (list.length <= 1) return list;

  // split the list into two halves
  let left = list.slice(0, list.length / 2);
  let right = list.slice(list.length / 2, list.length);

  left = mergeSort(left);
  right = mergeSort(right);

  // merge the sublists
  return merge(left, right);
}

const unsorted = [5, 4, 3, 2, 1];
const sorted = mergeSort(unsorted);
console.log(sorted); // [1, 2, 3, 4, 5]

Merge Sort performs in O(n log n) in terms of time complexity, its space complexity is O(n) since it uses auxiliary arrays to store the sublists.
Also, we can leverage multi-threading to implement Merge Sort, sorting each half in separated threads, for example. Moreover, we can combine Merge Sort with other sorting algorithms, for example, instead of splitting the list into single element sublists, we could split into small sublists with a few elements, and apply Insertion Sort to sort them.

Starting with sorting algorithms

Ricardo Borges — Thu, 05 Aug 2021 18:27:05 +0000

A sorting algorithm is an algorithm that sorts elements in a list into an order, among other uses, sorting can be applied to prepare a set of data for another algorithm, for example, Binary Search.

In this post, I'll describe three sorting algorithms that, although not the most efficient, are easy to understand and are in-place algorithms, meaning that they don't require auxiliary data structures.

Bubble Sort

Bubble sort starts at the beginning of the list, comparing each pair of adjacent elements, if the first is greater than the second, it swaps them. Then it starts again at the beginning of the list and repeats this process until no swap occurred on the last pass.

function swap(arr: number[], i: number, j: number) {
  [arr[i], arr[j]] = [arr[j], arr[i]];
}

function bubbleSort(arr: number[]) {
  for (let i = 0; i < arr.length - 1; i++) {
    let swapped = false;

    for (let j = 0; j < arr.length - 1; j++) {
      if (arr[j] > arr[j + 1]) {
        swap(arr, j, j + 1);
        swapped = true;
      }
    }

    if (!swapped) break;
  }
}

const arr = [5, 3, 1, 2, 4];
bubbleSort(arr);
console.log(arr);

Since its time complexity is Ο(n^2) on average and worst cases, this algorithm is more suitable for small or nearly ordered data sets.

Selection Sort

The list is divided into a sorted part at the left and an unsorted part at the right in this algorithm. Initially, the sorted sublist is empty and the unsorted one is all the list. Then it searches for the smallest element in the unsorted sublist and swaps it with the leftmost unsorted element, moving the sublist boundaries one element to the right.

function selectionSort(arr: number[]) {
  for (let i = 0; i < arr.length - 1; i++) {
    let min = i;

    for (let j = i + 1; j < arr.length; j++) {
      if (arr[j] < arr[min]) {
        min = j;
      }
    }

    swap(arr, min, i);
  }
}

Like Bubble Sort, this algorithm has a quadratic time complexity Ο(n^2), so it is also more suitable for small or nearly ordered data sets. However, Selection Sort performs fewer swaps than Bubble Sort.

Insertion Sort

Insertion Sort keeps a sorted sublist at the beginning of the list, and for each element from the list, it searches for the right position in that sublist to insert that element.

function insertionSort(arr: number[]) {
  for (let i = 1; i < arr.length; i++) {
    let value = arr[i];
    let j = i - 1;

    while (j >= 0 && arr[j] > value) {
      arr[j + 1] = arr[j];
      j = j - 1;
    }
    arr[j + 1] = value;
  }
}

Insertion sort has a quadratic time complexity for average and worst cases too, however, it's the fastest sorting algorithm for small lists.

How to check if a Binary Tree is a BST

Ricardo Borges — Thu, 29 Jul 2021 11:22:13 +0000

This is one of those problems that have properties that, given an example, we can identify them right away, like "check if this array is ordered", if it contains only a few elements we just have to look at it and we will know.

Before we continue, if necessary, take some time to understand what is a BST reading this post.

For example, look at this Binary tree:

You know this is a BST because it satisfy the definition: left.data <= current.data < right.data.

So far, we understand the problem and we can identify a BST just looking at it, what is pending now, is the algorithm. Basically, all we have to do is check if every subtree satisfies the definition of the BST, let's see how we would do that.

Starting with the root node, well that node can have any value, in this case, 5;
Moving on to the left child node 2, now this node can't be greater than its parent (5);
Node 2's left child 1 also has a limit (2);
Node 2's right child 3 must have a value that is greater than its parent (2) but less than 5.

Up until now, we have noticed that some node has to be between a minimum and maximum value. Left nodes don't have a minimum constraint, and the root node doesn't have any constraints at all.

Now moving to the right subtree, the root node's right child 7, has to be greater than its parent;
Node 7's right child 8 must be greater than 7;
Node 7's left child 6 must be between 5 and 7.

Now we know that both subtrees have similar constraints, with this information, we know that our algorithm will start with the root node and will check if some nodes are between some min and max values, while other nodes don't have a min or max limit:

function isBST(node: BinarySearchTreeNode<number>, min: number, max: number) {}

We can do this recursively, so we need a base case:

function isBST(node: BinarySearchTreeNode<number>, min: number, max: number) {
  if (!node) return true; // base case
}

Next step is to check if the current node, is between those min and max values, we also have to consider that some nodes don't have those constraints, so we can expect that min and max can be null:

function isBST(node: BinarySearchTreeNode<number>, min: number, max: number) {
  if (!node) return true; // base case

  if ((min && node.data <= min) || (max && node.data > max)) {
    return false;
  }
}

Finally, we have to do the same for left and right subtrees, if any of them don't satisfy the BST definition we simply return false

function isBST(node: BinarySearchTreeNode<number>, min: number, max: number) {
  if (!node) return true; // base case

  if ((min && node.data <= min) || (max && node.data > max)) {
    return false;
  }

  // if the right or the left subtree is not a BST, return false
  if (
    !isBST(node.leftNode, min, node.data) ||
    !isBST(node.rightNode, node.data, max)
  ) {
    return false;
  }

  // finally, if all subtrees are under those constraints, return true
  return true;
}

That's it, I tried to explain step by step this algorithm, I hope I succeed.

Data Structures in Typescript - Binary Search Tree

Ricardo Borges — Thu, 22 Jul 2021 14:39:38 +0000

What is a Tree data structure

Before we talk BST, we have to understand that a tree is a kind of Graph with a root node and no cycles, each node can have zero or more child nodes, nodes can store any type of data, also those nodes may or may not be in a particular order, nodes that have no children are called leaves.

Binary Tree

A Binary tree is a tree that each node has up to two nodes:

Binary Search Tree

A BST is a Binary tree that follows these properties:

All left descendants nodes are less or equal to their parent node
All right descendants nodes are greater than their parent node

BST definitions can slightly vary, you may find a BSTs that the left subtree is less than the parent node (left subtree < parent <= right subtree).

Also, some BSTs may or may not allow duplicated nodes.

BST is useful when you need to insert, delete and search comparable elements. You can use an array for those operations, but, although access an element in an array is done in a constant time, whenever you insert or delete an element, the other elements have to be shifted, in a BST, on the other hand, you only need to adjust the pointers.

Searching in the BST

The search starts from the root node, if the element you are searching for is greater than the current node value, then search for it in the right subtree, otherwise search in the left subtree, repeat this until the current node value is equal to the element you are searching for or until you reach a leaf node and there is nowhere to go:

search(data) {
    // empty tree
    if (!root) return;

    // start from root node
    let current = root;

    while (current.data !== data) {
        // data greater than current element
        if (data > current.data) {

        // you are on a leaf node, nowhere to go
        if (!current.rightNode) return;

        // go to the right subtree
        current = current.rightNode;
        } else {

        // you are on a leaf node, nowhere to go
        if (!current.leftNode) return;

        // go to the left subtree
        current = current.leftNode;
        }
    }

    return current;
}

Inserting in the BST

When inserting a new element in BST you have to keep its properties, so start from the root node, if the new element value is greater than the root node value, search for an empty position in the right subtree, otherwise search for an empty position in the left subtree:

insert(data) {
  // empty tree, insert the first node (the root node)
  if (!root) {
    root = new Node(data);
    return root;
  }

  // start from the root node
  let current = root;

  while (true) {
    if (data > current.data) {
      // search for an empty position in the right subtree
      if (current.rightNode) {
        current = current.rightNode;
      } else {
        // insert node
        current.rightNode = new Node(data);
        return current.rightNode;
      }
    } else {
      // search for an empty position in the left subtree
      if (current.leftNode) {
        current = current.leftNode;
      } else {
        // insert node
        current.leftNode = new Node(data);
        return current.leftNode;
      }
    }
  }
}

Binary Search Tree traversal

There are three ways to traverse a BST, they differ on which order the nodes are visited (often, printed):

In-Order traversal

First visit left branch, then the current node, and finally the right branch, because of how elements are distributed in the BST, they will be visited in the ascending order:

inOrderTraversal(node) {
  if (node) {
    inOrderTraversal(node.leftNode);
    console.log(node.data);
    inOrderTraversal(node.rightNode);
  }
}

Pre-Order traversal

Visit the current node before its children:

preOrderTraversal(node) {
  if (node) {
    console.log(node.data);
    this.preOrderTraversal(node.leftNode);
    this.preOrderTraversal(node.rightNode);
  }
}

Post-Order traversal

Visit the current node's children first, then the current node:

postOrderTraversal(node) {
  if (node) {
    this.postOrderTraversal(node.leftNode);
    this.postOrderTraversal(node.rightNode);
    console.log(node.data);
  }
}

Here's an implementation of a BST in typescript:

export class BinarySearchTreeNode<T> {
  data: T;
  leftNode?: BinarySearchTreeNode<T>;
  rightNode?: BinarySearchTreeNode<T>;

  constructor(data: T) {
    this.data = data;
  }
}

export class BinarySearchTree<T> {
  root?: BinarySearchTreeNode<T>;
  comparator: (a: T, b: T) => number;

  constructor(comparator: (a: T, b: T) => number) {
    this.comparator = comparator;
  }

  insert(data: T): BinarySearchTreeNode<T> | undefined {
    if (!this.root) {
      this.root = new BinarySearchTreeNode(data);
      return this.root;
    }

    let current = this.root;

    while (true) {
      if (this.comparator(data, current.data) === 1) {
        if (current.rightNode) {
          current = current.rightNode;
        } else {
          current.rightNode = new BinarySearchTreeNode(data);
          return current.rightNode;
        }
      } else {
        if (current.leftNode) {
          current = current.leftNode;
        } else {
          current.leftNode = new BinarySearchTreeNode(data);
          return current.leftNode;
        }
      }
    }
  }

  search(data: T): BinarySearchTreeNode<T> | undefined {
    if (!this.root) return undefined;

    let current = this.root;

    while (this.comparator(data, current.data) !== 0) {
      if (this.comparator(data, current.data) === 1) {
        if (!current.rightNode) return;

        current = current.rightNode;
      } else {
        if (!current.leftNode) return;

        current = current.leftNode;
      }
    }

    return current;
  }

  inOrderTraversal(node: BinarySearchTreeNode<T> | undefined): void {
    if (node) {
      this.inOrderTraversal(node.leftNode);
      console.log(node.data);
      this.inOrderTraversal(node.rightNode);
    }
  }

  preOrderTraversal(node: BinarySearchTreeNode<T> | undefined): void {
    if (node) {
      console.log(node.data);
      this.preOrderTraversal(node.leftNode);
      this.preOrderTraversal(node.rightNode);
    }
  }

  postOrderTraversal(node: BinarySearchTreeNode<T> | undefined): void {
    if (node) {
      this.postOrderTraversal(node.leftNode);
      this.postOrderTraversal(node.rightNode);
      console.log(node.data);
    }
  }
}

function comparator(a: number, b: number) {
  if (a < b) return -1;

  if (a > b) return 1;

  return 0;
}

const bst = new BinarySearchTree(comparator);

bst.insert(5);

bst.insert(2);
bst.insert(3);
bst.insert(1);

bst.insert(7);
bst.insert(6);
bst.insert(8);

bst.inOrderTraversal(bst.root);

Unlike Graphs, a tree doesn't really need a Tree class, just a Node class would usually suffice.

How to reverse a Singly Linked List

Ricardo Borges — Fri, 16 Jul 2021 02:19:12 +0000

In a Singly Linked List, each node has only a pointer to the next node, and there are some ways to reverse it, the one that I want to show here doesn't require extra space.

In this algorithm, we start from the list's head, and we use three pointers, each one for previous node, current node and next node.
In the beginning, The current and the next points to the list's head, and the previous points to null. While the current are pointing to a node we do the following:

next point to its next node
current.next points to previous node
previous node points to the current node
current node points to next node

This loop continues until the current points to null, which will mean that we reached the end of the list. Like this:

prev = null;
current = head;
next = head;

while (current !== null) {
  next = next.next;
  current.next = prev;
  prev = current;
  current = next;
}

A single iteration works like this:

This algorithm may vary according to the Linked List implementation, using this implementation, looks like this:

function reverse(linkedList: LinkedList<number>) {
  let prev = null;
  let current = linkedList.head;
  let next = linkedList.head;

  while (current !== null) {
    next = next.next;
    current.next = prev;
    prev = current;
    current = next;
  }

  linkedList.head = prev;
}

const linkedList = new LinkedList((a: number, b: number) => a === b);

linkedList.append(1);
linkedList.append(2);
linkedList.append(3);
linkedList.append(4);
linkedList.append(5);

reverse(linkedList);

linkedList.traverse();

Topological sort

Ricardo Borges — Thu, 08 Jul 2021 18:52:01 +0000

Topological sort is an ordering of the vertices of a directed acyclic graph, in a way that if there is an edge from a vertex A to B, then A comes before B. For example, let's say there is a set of projects and some of them depend on other projects:

In this example project B and C depends on project A, and project D depends on projects B and C. Therefore, project A must be executed first, then projects B and C, and finally project D. Resulting in this order: [A, B, C, D] or [A, C, B, D].

Note that we start from node A because it doesn't have dependencies and repeat it, that is after A is done, B and C haven't dependencies anymore, so we can choose either one to be the next. That's why this algorithm works only on acyclic graphs.

We can use a modified depth-first search for this algorithm, here I talk more about DPS. The steps are the following:

1 - For every unvisited node visit it and its adjacent nodes (DPS)
2 - After visiting a node and its adjacent add it at the beginning of a list (you can use a stack instead), this list will be in the topological order.

Here's an implementation in TypeScript, I'm using this implementation of a graph:

function topSort(
  node: Node<number>,
  visited: Map<number, boolean>,
  order: number[]
) {
  if (!node) return;

  // set node as visited
  visited.set(node.data, true);

  // for each of node's unvisited adjacent call topSort
  node.adjacent.forEach((item) => {
    if (!visited.has(item.data)) {
      topSort(item, visited, order);
    }
  });

  // add node at the beginning of the order list
  order.unshift(node.data);
}

// topological order list
const order = [];
// map to keep track of visited nodes
const visited = new Map();

// For every unvisited node visit it and its adjacent nodes
for (const entry of graph.nodes.entries()) {
  const node = entry[1];
  if (!visited.has(node.data)) {
    topSort(node, visited, order);
  }
}

There are other problems that topological sorting can resolve, like the order that courses have to be selected during college, since they may have other courses as a prerequisite. Or even the order of steps of a recipe, in which some must be taken before others.

There are a lot of explanations for this algorithm on the internet, here I tried to explain it in a little different way, I hope this helped you to make sense of it or if you haven't heard about topological sorting before, at least this may be an introduction of it.