Top data structures and algorithms every developer must know

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.

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?
Understanding Big O notation
Important data structures to learn
Important algorithms to learn
What to learn next

Get hands-on with coding interviews.

Grokking the Coding Interview Patterns

With thousands of potential questions to account for, preparing for the coding interview can feel like an impossible challenge. Yet with a strategic approach, coding interview prep doesn’t have to take more than a few weeks. Stop drilling endless sets of practice problems, and prepare more efficiently by learning coding interview patterns. This course teaches you the underlying patterns behind common coding interview questions. By learning these essential patterns, you will be able to unpack and answer any problem the right way — just by assessing the problem statement. This approach was created by FAANG hiring managers to help you prepare for the typical rounds of interviews at major tech companies like Apple, Google, Meta, Microsoft, and Amazon. Before long, you will have the skills you need to unlock even the most challenging questions, grok the coding interview, and level up your career with confidence. This course is also available in JavaScript, Python, Go, and C++ — with more coming soon!

85hrs

Intermediate

269 Challenges

270 Quizzes

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.

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.

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!)$ .

Since each popular algorithm or structure has consistent complexity, its helpful to keep a Big-O Cheat Sheet for ease of access.


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); 
    } 
}

Stack.java

Main.java

class Stack { 
    static final int MAX = 1000; 
    int top; 
    int a[] = new int[MAX]; // Maximum size of Stack 
  
    boolean isEmpty() 
    { 
        return (top < 0); 
    } 
    Stack() 
    { 
        top = -1; 
    } 
  
    boolean push(int x) 
    { 
        if (top >= (MAX - 1)) { 
            System.out.println("Stack Overflow"); 
            return false; 
        } 
        else { 
            a[++top] = x; 
            System.out.println(x + " pushed into stack"); 
            return true; 
        } 
    } 
  
    int pop() 
    { 
        if (top < 0) { 
            System.out.println("Stack Underflow"); 
            return 0; 
        } 
        else { 
            int x = a[top--]; 
            return x; 
        } 
    } 
  
    int peek() 
    { 
        if (top < 0) { 
            System.out.println("Stack Underflow"); 
            return 0; 
        } 
        else { 
            int x = a[top]; 
            return x; 
        } 
    } 
}

Queue.java

Main.java

class Queue 
{ 
    int front, rear, size; 
    int  capacity; 
    int array[]; 
       
    public Queue(int capacity) { 
         this.capacity = capacity; 
         front = this.size = 0;  
         rear = capacity - 1; 
         array = new int[this.capacity]; 
            
    } 
       
    // Queue is full when size becomes equal to  
    // the capacity  
    boolean isFull(Queue queue) 
    {  return (queue.size == queue.capacity); 
    } 
       
    // Queue is empty when size is 0 
    boolean isEmpty(Queue queue) 
    {  return (queue.size == 0); } 
       
    // Method to add an item to the queue.  
    // It changes rear and size 
    void enqueue( int item) 
    { 
        if (isFull(this)) 
            return; 
        this.rear = (this.rear + 1)%this.capacity; 
        this.array[this.rear] = item; 
        this.size = this.size + 1; 
        System.out.println(item+ " enqueued to queue"); 
    } 
       
    // Method to remove an item from queue.   
    // It changes front and size 
    int dequeue() 
    { 
        if (isEmpty(this)) 
            return Integer.MIN_VALUE; 
           
        int item = this.array[this.front]; 
        this.front = (this.front + 1)%this.capacity; 
        this.size = this.size - 1; 
        return item; 
    } 
       
    // Method to get front of queue 
    int front() 
    { 
        if (isEmpty(this)) 
            return Integer.MIN_VALUE; 
           
        return this.array[this.front]; 
    } 
        
    // Method to get rear of queue 
    int rear() 
    { 
        if (isEmpty(this)) 
            return Integer.MIN_VALUE; 
           
        return this.array[this.rear]; 
    } 
}

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); 
    } 
}

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.

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.

Get hands-on with coding interviews.

Grokking the Coding Interview Patterns

With thousands of potential questions to account for, preparing for the coding interview can feel like an impossible challenge. Yet with a strategic approach, coding interview prep doesn’t have to take more than a few weeks. Stop drilling endless sets of practice problems, and prepare more efficiently by learning coding interview patterns. This course teaches you the underlying patterns behind common coding interview questions. By learning these essential patterns, you will be able to unpack and answer any problem the right way — just by assessing the problem statement. This approach was created by FAANG hiring managers to help you prepare for the typical rounds of interviews at major tech companies like Apple, Google, Meta, Microsoft, and Amazon. Before long, you will have the skills you need to unlock even the most challenging questions, grok the coding interview, and level up your career with confidence. This course is also available in JavaScript, Python, Go, and C++ — with more coming soon!

85hrs

Intermediate

269 Challenges

270 Quizzes

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.

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.

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; 
    }

What to learn next#

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:

Heap sort
Quick sort
Merge sort
Dynamic programming
AVL tree
Doubly linked list
Dijkstra’s algorithm
Tries

To get practice with these advanced concepts, check out Educative’s beloved course Decode the Coding Interview in Java: Real-World Examples. You’ll get hands-on practice with these concepts by solving real-world problems. By the end, you’ll have the practical experience to confidently answer any question that comes your way in your interviews.

Top data structures and algorithms every developer must know

Why should you learn data structures and algorithms?#

Understanding Big O notation#

O(1)O(1)O(1)#

O(N)O(N)O(N)#

O(N2)O(N^2)O(N2)#

Some rules to remember#

Important data structures to learn#

Arrays#

Linked lists#

Stacks#

Queues#

Graphs#

Hash tables#

Binary search tree#

Important algorithms to learn#

Recursion#

Bubble sort#

Selection sort#

Insertion Sort#

Binary search#

What to learn next#

Continue reading about coding interviews#