loading...
Cover image for Top Data Structures and Algorithms every developer must know
Educative

Top Data Structures and Algorithms every developer must know

amandaeducative profile image Amanda Fawcett Originally published at educative.io ・18 min read

This article was written by Aaron Xie and was originally published at Educative, Inc.

Many shudder at the thought of a coding interview. It can be stressful, grueling, and challenging. Oftentimes, it can be a struggle simply to know what topics to prepare. However today, you will be introduced to the primary data structures and algorithms that are tested in a coding interview. After reading this article, you should have a good idea of what you need to prepare for to land your dream job.

We will cover the following:

Why should you learn data structures and algorithms?

The coding interview tests for your problem-solving abilities and understanding of computer science concepts. Usually, you are given about 30 - 45 minutes to solve one complex problem, but sometimes you will be given a few easier technical problems to solve.

This is where data structures and algorithms come in. These interviews will test you on topics such as linked lists, queues, sorting, searching, and much more, so it’s crucial to prepare. Not only do companies want to test your technical knowledge, but they also want to evaluate your problem-solving skills. If you get the job, you will often face bugs that you need to fix, and companies want to make sure that you can overcome these obstacles. Furthermore, you will often use specific data structures and algorithms to optimize your code so that it runs as efficiently as possible.

Understanding Big O notation

Big O notation is an asymptotic analysis that describes how long an algorithm takes to perform. In other words, it's used to talk about how efficient or complex an algorithm is.

Big O describes the execution time, or run time, of an algorithm relative to its input $N$ as the input increases. Though we can analyze an algorithm's efficiency using average-case and best-case, we typically use worst-case with Big O notation.

Today, you will learn about time complexity, but take note that space complexity is also an important concept to understand. Runtime complexity can be a difficult concept to grasp at first, so let's look at some examples

$O(1)$

public int findInt(int[] arr) {
    return arr[0];
}

$O(1)$ describes an algorithm that always runs at a constant time no matter its input. The function will execute at the same time no matter if the array holds a thousand integers or one integer because it only takes one "step".

$O(N)$

public int func(int[] arr) {
    for (int i = 1; i <= arr.length; i++) {
        System.out.println(i);
    }
}

$O(N)$ describes an algorithm whose runtime will increase linearly relative to the input $N$. The function above will take $N$ steps for $N$ values stored in the array. For example, if the array length is 1, the function will take 1 "step" to run, whereas if the array length is 1000, the function will take 1000 "steps" to run.

In the example provided, the array length is the input size, and the number of iterations is the runtime.

$O(N^2)$

public int func(int[] arr) {
    for (int i = 1; i <= arr.length; i++) {
        for (int i = 1; i <= arr.length; i++) {
        System.out.println(i);
        }
    }
}

$O(N^2)$ describes a function whose runtime is proportional to the square of the input size. This runtime occurs when there is a nested loop such that the outer loop runs $N$ times, and the inner loop runs $N$ times for each iteration by the outer loop such that the function takes $N^2$ steps.

Some rules to remember

  • Ignore constants: When using Big O notation, you always drop the constants. So, even if the runtime complexity is $O(2N)$, we call it $O(N)$.

  • Drop less dominant terms: You only keep the most dominant term when talking Big O. For example, $O(N^3 + 50N +1 7)$ is simply $O(N^3)$. Here's the rule of thumb: $O(1)$ < $O(logN)$ < $O(N)$ < $O(NlogN)$ < $O(N^2)$ < $O(2^N)$ < $O(N!)$.

Want to read more about Big O notation? Check out our What is Big-O Notation article.

Alt Text

Important data structures to learn

In simplest terms, data structures are ways to organize and store data in a computer so that it be accessed and modified. You will learn the basics of the important data structures that are tested in the coding interview.

Arrays

An array is a collection of items of the same variable type that are stored sequentially in memory. It's one of the most popular and simple data structures and often used to implement other data structures.

Each item in an array is indexed starting with 0, and each item is known as an element. It's also important to note that in Java, you cannot change the size of an array. For dynamic sizes, it's recommended to use a List.

Alt Text

In the example above:

  • The length of the array is 5

  • The value at index 3 is 1

  • In Java, all values in this array must be an integer type

Initializing an array in Java:

int[] intArray = new int[14];

intArray[3] = 5;
intArray[4] = 3;
intArray[13] = 14;

// Indexes with no value are null

Common interview questions:

  • Find first non-repeating integer in an array

  • Rearrange array in decreasing order

  • Right rotate the array by one index

  • Maximum sum subarray using divide and conquer


Linked lists

A linked list is a linear sequence of nodes that are linked together. Each node contains a value and a pointer to the next node in the list. Unlike arrays, linked lists do not have indexes, so you must start at the first node and traverse through each node until you get to the $n$th node. At the end, the last node will point to a null value.

The first node is called the head, and the last node is called the tail. Below visualizes a singly linked list.

Alt Text

A linked list has a number of useful applications:

  • Implement stacks, queues, and hash tables

  • Create directories

  • Polynomial representation and arithmetic operations

  • Dynamic memory allocation

Basic implementation of a linked list in Java:


import java.io.*; 

// Java program to implement 
// a Singly Linked List 
public class LinkedList { 

    Node head; // head of list 

    // Linked list Node. 
    // This inner class is made static 
    // so that main() can access it 
    static class Node { 

        int data; 
        Node next; 

        // Constructor 
        Node(int d) 
        { 
            data = d; 
            next = null; 
        } 
    } 

    // Method to insert a new node 
    public static LinkedList insert(LinkedList list, int data) 
    { 
        // Create a new node with given data 
        Node new_node = new Node(data); 
        new_node.next = null; 

        // If the Linked List is empty, 
        // then make the new node as head 
        if (list.head == null) { 
            list.head = new_node; 
        } 
        else { 
            // Else traverse till the last node 
            // and insert the new_node there 
            Node last = list.head; 
            while (last.next != null) { 
                last = last.next; 
            } 

            // Insert the new_node at last node 
            last.next = new_node; 
        } 

        // Return the list by head 
        return list; 
    } 

    // Method to print the LinkedList. 
    public static void printList(LinkedList list) 
    { 
        Node currNode = list.head; 

        System.out.print("LinkedList: "); 

        // Traverse through the LinkedList 
        while (currNode != null) { 
            // Print the data at current node 
            System.out.print(currNode.data + " "); 

            // Go to next node 
            currNode = currNode.next; 
        } 
    } 

    // Driver code 
    public static void main(String[] args) 
    { 
        /* Start with the empty list. */
        LinkedList list = new LinkedList(); 

        // 
        // ******INSERTION****** 
        // 

        // Insert the values 
        list = insert(list, 1); 
        list = insert(list, 2); 
        list = insert(list, 3); 
        list = insert(list, 4); 
        list = insert(list, 5); 
        list = insert(list, 6); 
        list = insert(list, 7); 
        list = insert(list, 8); 

        // Print the LinkedList 
        printList(list); 
    } 
} 

Common interview questions:

  • Reverse a linked list

  • Find the middle value in a linked list

  • Remove loop in a linked list


Stacks

Stacks are linear data structures in a LIFO (last-in, first-out) order. Now, what does that mean? Imagine a stack of plates. The last plate that you put on top of the stack is the first one you take out. Stacks work that way: the last value you add is the first one you remove.

Think of a stack like a collection of items that we can add to and remove from. The most common functions in a stack are push, pop, isEmpty, and peek.

Alt Text

A stack has a number of useful applications:

  • Backtracking to a previous state

  • Expression evaluation and conversion

Common interview questions:

  • Use stack to check for balanced parenthesis

  • Implement two stacks in an array

  • Next greater element using a stack


Queues

Queues are very similar to stacks in that they both are linear data structures with dynamic size. However, queues are FIFO (first-in, first-out) data structures. To visualize this data structure, imagine you are lining up for a roller coaster. The first people that line up get to leave the line for the ride.

In this data structure, elements enter from the "back" and leave from the "front." The standard functions in a queue are enqueue, dequeue, rear, front, and isFull.

Alt Text

A queue has a number of useful applications:

  • When a resource is shared by multiple consumers

  • Create directories

  • When data is transferring asynchronously between two resources

Common interview questions:

  • Reverse first kth elements of a queue

  • Generate binary numbers from 1 to n using a queue


Graphs

A graph is a collection of vertices (nodes) that are connected by edges, creating a network.

Alt Text

In the example above, the set of vertices are (12, 2, 4, 18, 23) and the edges are (12-2, 12-4, 2-4, 4-18, 4-23, 18-23, 2-18).

Graphs are very versatile data structures that can solve a plethora of real-world problems. Graphs are often used in social networks like LinkedIn or Facebook. With GraphQL on the rise, data is being organized as graphs, or networks.

Basic implementation of a graph:

import java.util.*; 

class Graph { 

    // A utility function to add an edge in an 
    // undirected graph 
    static void addEdge(ArrayList<ArrayList<Integer> > adj, 
                        int u, int v) 
    { 
        adj.get(u).add(v); 
        adj.get(v).add(u); 
    } 

    // A utility function to print the adjacency list 
    // representation of graph 
    static void printGraph(ArrayList<ArrayList<Integer> > adj) 
    { 
        for (int i = 0; i < adj.size(); i++) { 
            System.out.println("\nAdjacency list of vertex" + i); 
            for (int j = 0; j < adj.get(i).size(); j++) { 
                System.out.print(" -> "+adj.get(i).get(j)); 
            } 
            System.out.println(); 
        } 
    } 

    // Driver Code 
    public static void main(String[] args) 
    { 
        // Creating a graph with 5 vertices 
        int V = 5; 
        ArrayList<ArrayList<Integer> > adj  
                    = new ArrayList<ArrayList<Integer> >(V); 

        for (int i = 0; i < V; i++) 
            adj.add(new ArrayList<Integer>()); 

        // Adding edges one by one 
        addEdge(adj, 0, 1); 
        addEdge(adj, 0, 4); 
        addEdge(adj, 1, 2); 
        addEdge(adj, 1, 3); 
        addEdge(adj, 1, 4); 
        addEdge(adj, 2, 3); 
        addEdge(adj, 3, 4); 

        printGraph(adj); 
    } 
} 

Common interview questions:

  • Find shortest path between two vertices

  • Check if a path exists between two vertices

  • Find "mother vertex" in a graph


Hash tables

What's hashing?
Before we dive into hash tables, it's essential to understand what hashing is.

Hashing is the process of assigning an object into a unique index, known as a key. Each object is identified using a key-value pair, and the collection of objects is known as a dictionary.

A hash table is implemented by storing elements in an array and identifying them through a key. A hash function takes in a key and returns an index for which the value is stored.

So, whenever you input the key into the hash function, it will always return the same index, which will identify the associated element. Furthermore, if the hash function ever receives a unique key that returns an already used index, you can create a chain of elements with a linked list.

Alt Text

A hash table has a number of useful applications:

  • When a resource is shared by multiple consumers

  • Password verification

  • Linking file name and path

Common interview questions:

  • Find symmetric pairs in an array

  • Union and intersection of lists using hashing


Binary search tree

A binary search tree is a binary tree data structure made up of nodes. The nodes are arranged with the following properties:

  • The left subnode always contains values less than the parent node.

  • The right subnode always contains values greater than the parent node.

  • Both subnodes will also be binary search trees.

Binary search trees are used in many search applications and also used to determine objects that need to be rendered in a 3D game. This data structure is widely used in engineer projects because hierarchical data is so common.

Alt Text

Common operations:

  • Search - searches for an element

  • Insert - inserts an element in the tree

  • Pre-order traversal - traverses the tree in a pre-order way

  • In-order traversal - traverses the tree in an in-order way

  • Post-order traversal - traverses the tree in a post-order way

Common interview questions:

  • Find kth maximum value in a binary search tree

  • Find the minimum value in a binary search tree

  • Traverse a given directory using breadth first search

Keep the learning going.

Learn the most asked interview questions without scrubbing through videos or grinding through hundreds of questions. Educative's text-based courses are easy to skim and feature live coding environments - making learning quick and efficient.

Grokking the Coding Interview: Patterns for Coding Questions

Alt Text

Important algorithms to learn

Recursion

Recursion is the practice in which a function calls itself directly or indirectly. The corresponding function that is called is known as the recursive function. While recursion is often associated as an algorithm, it may help to understand it as a way or methodology to solve a problem.

So why is recursion useful? Or what even is it? Let's look at how we can use recursion to calculate factorials as an example.

public static long factorial(int number){        
        //base case - factorial of 0 or 1 is 1
        if(number <=1){
            return 1;
        }        
        return number*factorial(number - 1);
    }

In the example above, the function starts at a number $n$. When the function is called, it will call $factorial(n - 1)$. Say the $n$ value is 4; the function will return

$4 * factorial(3) -> 4 * 3 * factorial(2) -> 4 * 3 * 2 * factorial(1)$

Once $n = 1$, the function will return $factorial(1) = 1$, and we get $factorial(4)$ equal to $4 * 3 * 2 * 1$, which is 24.

Here, you can see the power of recursion. It’s a widely used practice of solving a complex problem by breaking it into smaller instances of the problem until we can solve it. Using recursion, you can simplify a lot of complex problems that would be difficult otherwise.

Need more explanation? Read our What is Recursion? Edpresso shot here.


Bubble sort

Bubble sort is a simple sorting algorithm that swaps adjacent elements if they are in an incorrect order. The algorithm will iterate through an array multiple times until the elements are in the correct order.

Say, we have an array as seen below.

Alt Text

As the algorithm scans the array from left to right for the first iteration, starting at index 0, it compares index $i$ with index $i + 1$. At index 1, it will see that 11 is greater than 6 and swap the two.

Alt Text

As the algorithm continues scanning for the first iteration, it will see that 13 is greater than 10 and swap the two.

Alt Text

Next, it will go through the array for its second iteration. It will swap the values in index 2 and 3 when it sees that 11 is greater than 10.

Alt Text

The algorithm will scan the array for the third iteration, and because it does not need to make any more swaps for the third iteration, the algorithm will end.

Alt Text

As you can see, bubble sort can perform poorly when working with a lot more elements, making it primarily used as simply an educational tool. It has a runtime complexity of O($n^2$).

Implementing bubble sort:

public static void bubble_srt(int array[]) {
        int n = array.length;
        int k;
        for (int m = n; m >= 0; m--) {
            for (int i = 0; i < n - 1; i++) {
                k = i + 1;
                if (array[i] > array[k]) {
                    swapNumbers(i, k, array);
                }
            }
            printNumbers(array);
        }
    }

Selection sort

Selection sort is an algorithm that splits a collection of elements into sorted and unsorted. During each iteration, the algorithm finds the smallest element in the unsorted group and moves it to the end of the sorted group.

Let's look at an example:

Alt Text

At first, all elements are unsorted. For the first iteration, the algorithm will go through each element and will identify 4 as the smallest value. The algorithm will swap the 11, the first element in the unsorted group with the lowest element in the unsorted group, 4.

Alt Text

Now, the sorted group is index 0, and the unsorted group is index 1 to index 3. For the second iteration, the algorithm will start at index 1 and scan the array, identifying 6 as the lowest value in the unsorted group. It will swap 11 and 6.

Alt Text

The sorted group is now index 0 to index 1, and the unsorted group is index 2 to index 3. For the third iteration, the algorithm will start at index 2, and find 11 as the lowest value. Because 11 is already in the right index, it will not move. With this, the algorithm ends.

Alt Text

Similar to bubble sort, selection sort is often a slow algorithm. It also has a runtime complexity of O($n^2$).

Implementing selection sort:

public static int[] doSelectionSort(int[] arr){

        for (int i = 0; i < arr.length - 1; i++)
        {
            int index = i;
            for (int j = i + 1; j < arr.length; j++)
                if (arr[j] < arr[index]) 
                    index = j;

            int smallerNumber = arr[index];  
            arr[index] = arr[i];
            arr[i] = smallerNumber;
        }
        return arr;
    }
}

Insertion Sort

Insertion sort is a simple sorting algorithm that builds the final array by sorting an element one at a time. How does it work?

  • Examines each element and compare it to the sorted elements on the left

  • Inserts the item in the correct order for the sorted elements

Let's look at an example.

Alt Text

The algorithm starts at index 0 with the value 11. Because there are no elements to the left of 11, it stays where it is. Now, onto index 1. The value to the left of it is 11, which means we swap 11 and 4.

Alt Text

Again, the algorithm looks to the left of 4. Because there is no element to the left of 4, it stays where it is. Next, onto index 2. The element with the value 6 looks to left. Because it's less than 11, the two switch.

Alt Text

The element 6 looks to the left again, but because 4 is less than 6, it stays where it is. Next, we go to the element at index 4. The algorithm looks to the left, but because 11 is less than 13, it stays where it is. Now, the algorithm is done.

Alt Text

Insertion sort is almost always more efficient than bubble sort and selection sort, so it's used more often when working with a small number of elements. Similar to the two other sorting algorithms, insertion sort also has a quadratic runtime of O($n^2$).

Implementing insertion sort:

public static int[] doInsertionSort(int[] input){

        int temp;
        for (int i = 1; i < input.length; i++) {
            for(int j = i ; j > 0 ; j--){
                if(input[j] < input[j-1]){
                    temp = input[j];
                    input[j] = input[j-1];
                    input[j-1] = temp;
                }
            }
        }
        return input;
    }

Binary search

Binary search is the most efficient searching algorithm to find an element. The algorithm works by comparing the middle element of an array or list to the target element. If the values are the same, the index of the element will be returned. If not, the list will be cut in half.

If the target value were less than the middle value, the new list would be the left half. If the target value were greater than the middle value, the new list would be the right half.

This process continues where you keep splitting a list and searching one of the halves until the search algorithm finds the target value and returns the position. The runtime complexity of this algorithm is $O(log2n)$. It's important to note that binary search only works if the list is already sorted.

To visualize a binary search, let's say that you have a sorted array with ten elements, and you are looking for an index of 33.

Alt Text

The middle value of this array is 16, and the algorithm compares it to 33. 33 is greater than 16, so the algorithm splits the array and searches in the second half.

Alt Text

The new middle value is 28. Because 33 is greater than 28, the algorithm searches in the second half of the array.

Alt Text

After the array is split once again into the right half, the new middle value is 33. The algorithm sees that the middle value and the target value are the same and returns the position of the element.

Implementing binary search:

int binarySearch(int arr[], int l, int r, int x) 
    { 
        if (r >= l) { 
            int mid = l + (r - l) / 2; 

            // If the element is present at the 
            // middle itself 
            if (arr[mid] == x) 
                return mid; 

            // If element is smaller than mid, then 
            // it can only be present in left subarray 
            if (arr[mid] > x) 
                return binarySearch(arr, l, mid - 1, x); 

            // Else the element can only be present 
            // in right subarray 
            return binarySearch(arr, mid + 1, r, x); 
        } 

        // We reach here when element is not present 
        // in array 
        return -1; 
    } 

Other topics to cover

Keep in mind that the concepts we have covered today are simply an introduction. It’s important that you take a deeper dive into the concepts and practice coding questions. Below are other topics we suggest you familiarize yourself with:

How to ace your next coding interview

  • Plan ahead: The first thing you should do before anything is to develop a comprehensive plan to study. Identify the topics you feel that you need more practice on and create a schedule that you can stick to. You should be prepared to study consistently. In general, four to six weeks is an excellent timeline to prepare for your interview.

  • Programming language: Choose a programming language that you feel comfortable using. How easily could you write a solution in 25-or-so minutes using this language? Some popular languages that developers will use are Java, Python, Javascript, or C++.

  • The company: Before going into any interview, you should study the company. Learning about the company culture and values is incredibly important to make sure that you align with the company and so that you are more prepared on the non-technical aspect of the interview. You should also study the common problems that the company tests for. By doing this, you can do targeted practice to prepare for your interview

  • Behavioural interview: As much as you might feel like you are ready to tackle the technical interview, you can't forget the behavioral interview. With the behavioral interview, companies want to make sure that you are a good fit for the role and the company. Check out our behavioral interview guide to adequately prepare for the interview.

Now, you should have a good idea of what you need to do before the day of the interview. You have a lot of learning to do, but no worries. If you want to continue the learning, check out the resources provided by Coding Interview or our Python, Java, or Javascript interview preparation courses under our Programming Language Interview series.

Resources

Here's a list of resources for you regarding the coding interview and general computer science topics.

Articles

Posted on by:

amandaeducative profile

Amanda Fawcett

@amandaeducative

Content Marketing Manager for Educative, Inc. (she/her) Learning web dev from scratch!

Educative

Level up on in-demand tech skills - at your own speed. Text-based courses with embedded coding environments help you learn without the fluff.

Discussion

pic
Editor guide
 

I'll recommend people to review these topics with some frequency during their career, not only juniors. Because of two reasons, it's easy to forget them (it's not a day to day work), and because there are a lot of topics it becomes a huge task to review them in a few days/weeks before an interview.

 

The question I ask myself right now: how many companies ask for algorithms in interviews, and how many companies have developers who actually use these algorithms in their daily jobs? I think the difference is pretty big (my experience, at least), and that's the real problem. Development is complex enough, I wouldn't advise beginner to learn all of that.

It's an impressive article, nonetheless!

 

Such a thorough and well-written article. Thanks for breaking everything down so comprehensively!

 

Glad you found it helpful!