When starting off programming there are a lot of themes introduced. One of these are "algorithms". This might be broad to understand, and it almost felt like a buzzword thrown around without anyone really ever explaining it. For senior developers it might be something so commonly used it is seen as so native that it doesn't require any more proper ellaboration. But getting to know what algorithms is about can unlock a lot of "aha moments" when further learning about software engineering in my opinion.

What is an Algorithm?

Algorithms are fundamental to all aspects of software development, acting as a set of instructions that solves specific problems or perform tasks. It can be for example sorting data or optimizing routes in navigation systems, algorithms enable not just functionality but also efficiency and effectiveness in software applications.

More often than not, algorithms and data structures are implemented into commonly used tools, even into programming languages built in methods. It is rare for Software Engineers today to write algorithms for sorting from scratch, because there already so many implemented in the popular libraries and languages that are efficient.

Glossary

Here I will err out the key concepts of algorithms.

Input - Algorithms take input data, which can be in various formats, such as ints (numbers), strings (text), boolean (true/false) and of course other sources such as images, videos, audio etc.

Output - The outcome or result of the program is referred to as the output.

Processing - Algorithms processes the input data thorugh a series of mathematical and logical operations. Manipulating and adapting it as stated in the code.

Definiteness - The steps in the algorithm are very clear and detailed. There is no ambiguousness in the steps. 

Why should we care about Algorithms?

There are many reasons to why algorithms are widely used. For scalability reasons a team can automate their way of handling data. Breaking down a real-world problem into smaller steps can really simplify large requirements into smaller parts. It is sort of like biking, once we have fallen 100 times and scraped our knees we implement a script of "how to not fall over whilst biking" in our brain 🧠

"Because studying and knowing algorithms and data structures helps in problem solving and programming better" - on Medium.

Also if getting that dream job, it is not uncommon for the company to have code tests or getting questions on algorithms during technical job interviews. It seems apparent that algorithmic experience is key for not only data scientists, machine learning but to any developer looking to create efficient solutions.

Common use cases for algorithms

Brute Force Algorithms - These type of algorithms are designed to look for all possible patterns. It is best suited for small input and problems. For large scale data it can require too much computing power.

Sorting Algorithms - A fundamental concept in programming. Sorting are done in data processing and statistics. Sorting is, as it name implies, arranging data in a meaningful way. It could be converting a list of elements into ascending or descending order.

Recursive Algorithms - A method that is subsetting a problem into smaller chunks, similar subproblems and repeatedly applies itself to solve them until reaching a base case. A base case is the models expected case, a pattern expected to occur.

Hashing - Converts data into fixed-size hash value. It enables for quick access to data and retrieval in hash tables. It is common for database and password storage. It is also often used in blockchain technology and crypto applications.

Backtracking - Can be explained as a trial-and-error technique, where the code builds candidates to the solutions, and abandon a candidate ("backtrack") as soon as it is determined that the candidate cannot possibly be completed to a valid solution. Very handy if you were to end up in a coding test while in a job hunt.

Encryption - Ever seen Criminal minds? I love Penelope Garcia, but Reid says "Encryption is a highly specialized skill set but it is fundamentally a mathemical process". Utilized to manipulate data into a secure, unreadable form using cryptographic techniques, ensuring confidentiality and privacy in digital communications and transactions. It can be anything from hashing a password.

Divide and Conquer Algorithm - Divides a large problem in to smaller ones, solves them independently and then combines their solutions to address the original problem effectively.

Dynamic Algorithm - Stores and reuses intermediate results to avoid redudant computations, it enhances the efficiency of solving complex problems.

Sorting algorithms

I bet you will do sorting algorithms a bunch of time while being a software engineer.

Creating efficient algorithms can save performance, scalability and overall efficiency of an application. A binary search acts on the "Divide and conquer" principle. It is much faster than the linear search if searching in sorted arrays. It can find an element or determine its absence in logarithmic time, O(log n), where n is the number of elements in the array. This

Binary search works by repeatedly dividing in half the portion of, for example, a list that could contain the item, until you've narrowed the possible locations to just one.

function binarySearch(sortedArray, target) {
    let left = 0;
    let right = sortedArray.length - 1;

    while (left <= right) {
        const mid = Math.floor((left + right) / 2);
        const midValue = sortedArray[mid];

        if (midValue === target) {
            return mid; // target found, return its index
        } else if (midValue < target) {
            left = mid + 1; // focus on the right half
        } else {
            right = mid - 1; // focus on the left half
        }
    }
    return -1; // target not found
}

// example of input to use:
const array = [1, 3, 5, 7, 9, 11, 13, 15, 17, 19];
const target = 9;

const result = binarySearch(array, target);
if (result !== -1) {
    console.log(`Target found at index ${result}`);
} else {
    console.log("Target not found in the array");
}

The code explained: Here we have sortedArray and target as input. We initiate left as 0. The right is the input sortedArray's length - 1. These pointers are set to the start and end of the array.

The while loop continues as long as left is less than or equal to right.

The midpoint of the current left and right is calculated. This is where we check if the target value matches the midpoint value. It moves the pointers if the target value is greater than the value of mid. If the target is less, the search shifts to the left half by setting right to mid - 1. If the loop ends without finding the target, -1 is returned which means that the target is not in the array.

Use cases for Binary search

These types of problem solving are common when your application are doing frequent search operation on sorted datasets, such as lookup operations in databases, searching in embedded systems or operations in large in-memory data arrays. However it requires the dataset to be sorted and is not optimal for data structures such as linked lists.

Binary search can be used effectively in any scenario requiring frequent search operations on sorted datasets, such as lookup operations in databases, searching in embedded systems with limited resources, or operations on large in-memory data arrays. However, it requires that the dataset be sorted and supports random access for optimal performance, limiting its use in data structures like linked lists.

Solving a sudoku puzzle by Validation algorithm

I once had to solve a "is this sudoku board correct or not" while getting a job. The input was a 9x9 grid, where each cell held a number of 1 to 9. Each of the nine 3x3 grids contain all of the numbers from 1 to 9. It was up to my algorithm to decide if the board was valid or not by returning 1 if it was correct or 0 if incorrect. Did I get the job? Na I did not do great explaining my first solution. But I did find the sudoku part quite fun.

I chose to use, in Javascript Set allows us to store unique values of any type, in our case ints. This function takes in a 2D array board as input.

function isValidSudoku(board) {
    let rows = Array.from({ length: 9 }, () => new Set());
    let cols = Array.from({ length: 9 }, () => new Set());
    let boxes = Array.from({ length: 9 }, () => new Set());

    for (let i = 0; i < 9; i++) {
        for (let j = 0; j < 9; j++) {
            const num = board[i][j];
            if (num === 0) continue; 

            const boxIndex = 3 * Math.floor(i / 3) + Math.floor(j / 3);
            
            let rowSet = rows[i], colSet = cols[j], boxSet = boxes[boxIndex];
            
            if (rowSet.has(num) || colSet.has(num) || boxSet.has(num)) {
                return false;
            }
            
            rowSet.add(num);
            colSet.add(num);
            boxSet.add(num);
        }
    }
    return 1;
}

At row 3 we use to instantiated three Sets containing rows, column and 3x3 subgrid (boxes) of the sudoku board. We create an array with the length of 9.

for (let i = 0; i < 9; i++) {
    for (let j = 0; j < 9; j++) {
        const num = board[i][j];

Next we do two nested for loops iterate over each row (i) and each column (j) in the 9x9 Sudoku grid. num is the value of the current cell at position [i][j] on the board.

const boxIndex = 3 * Math.floor(i / 3) + Math.floor(j / 3);

Above we decide which of the nine 3x3 boxes the current cell belongs to. The grid is divided into 3-rows by 3-column boxes, so Math.floor(i / 3) and Math.floor(j / 3) help group rows and columns into sets of threes.

let rowSet = rows[i], colSet = cols[j], boxSet = boxes[boxIndex];

We store rowSet, colSet and boxSet to keep track of current rows, columns and boxes (3x3 grid)

if (rowSet.has(num) || colSet.has(num) || boxSet.has(num)) {
    console.log("No bueno 🥺");
    return 0;
}

Before placing the number in the respective sets, we check if it already exists in any of them. If the number is found in any set (rowSet, colSet, boxSet), it means there's an incorrect Sudoku board . The rules are: no duplicates in a row, column, or box), and the function returns 0.

rowSet.add(num);
colSet.add(num);
boxSet.add(num);

If no duplicates were found the numbers are added to the different sets. Finally we return 1 for a valid sudoku board.

Solving problems with data structures with linked lists

Unlike arrays, linked lists are dynamic datasets with nodes that do not support direct access to indexing. Common approaches to these problem solving using algorithms are:

Traversal

It sequentially accessing each node by starting from the head until reaching the end of the list.

It involves sequentially accessing each node starting from the head until you reach the end (null) of the list. This is used in nearly every algorithm that manipulates linked lists, such as searching, modifying, or printing all elements. Elements are accessed in a FIFO - "First in First out" mechanism.

Searching

To find a value in a linked list, you need to traverse the nodes from the head, checking each node’s value against the target value.

Examples of solutions of linked list I have found to be quite complex in it's ways. A common use in my opinion is traversing through Reacts useRef(). By using useRef(), we can move the focus between these inputs, similar to traversing through nodes

This React component has three input fields. We create three refs corresponding to three input elements. Each button click calls a function that sets the focus to the specific input connected to the next ref. The current property of each ref is attached to an input element, and it’s used to call the focus method on that DOM element directly.

import React, { useRef } from 'react';

function FocusManager() {
    const firstInputRef = useRef('');
    const secondInputRef = useRef('');
    const thirdInputRef = useRef('');

    const focusSecondInput = () => secondInputRef.current.focus();
    const focusThirdInput = () => thirdInputRef.current.focus();
    const focusFirstInput = () => firstInputRef.current.focus();

    return (
        <div>
            <input ref={firstInputRef} placeholder="First Input" />
            <button onClick={focusSecondInput}>Go to Second Input</button>
            <input ref={secondInputRef} placeholder="Second Input" />
            <button onClick={focusThirdInput}>Go to Third Input</button>
            <input ref={thirdInputRef} placeholder="Third Input" />
            <button onClick={focusFirstInput}>Back to First Input</button>
        </div>
    );
}

export default FocusManager;

.