Most Popular Data Structures Interview Questions For Software Developers in 2023 (and Answers) — Part 1

Data Structures Are a Fundamental Topic in Computer Science And Are Frequently Asked About in Interviews, Regardless Of The Specific Tech Role.

Nat Misic

8 min readOct 23, 2023

Here are the most common, most popular data structures interview questions that were relevant for software developers in 2023:

Arrays and Strings

Explain the difference between an array and a linked list.
How do you reverse a string in place?
Implement an algorithm to determine if a string has all unique characters.

Linked Lists

How do you find the middle of a linked list in one pass?
How do you detect a cycle in a linked list?
How do you reverse a linked list?

Stacks and Queues

Implement a stack using arrays/linked list.
Implement a queue using stacks.
How would you design a stack that, in addition to push and pop, also has a function min which returns the minimum element?

Trees and Graphs

Explain the difference between a binary tree and a binary search tree.
Implement an algorithm for a depth-first search (DFS) on a graph.
Implement an algorithm for a breadth-first search (BFS) on a graph.
How do you find the lowest common ancestor of two nodes in a binary tree?

Hashing

Describe how a hash table works.
How do you handle collisions in a hash table?
Implement an LRU (Least Recently Used) cache.

Recursion and Dynamic Programming

Implement the Fibonacci series using recursion and dynamic programming.
How do you find the nth stair using step 1, 2, or 3 in a staircase problem?
Explain the concept of memoization.

Sorting and Searching

Implement the binary search algorithm.
Explain the quicksort algorithm.
How do you find the first non-repeated character in a string?

Miscellaneous

How would you design a data structure that supports insert, delete, get_random_element, all in constant time?
Explain the difference between a stack and a heap in memory.
How do you find the shortest path in a maze?
Describe the difference between “pass by value” and “pass by reference”.
How would you determine the number of set bits in an integer?
Explain the concept of a trie.

Mobile-Specific (For Mobile Developers)

How do data structures impact the performance of mobile applications?
Which data structures are more memory-efficient for mobile devices?

Hey! No worries at all. Let’s check the answers together! Here are the Part 1 solutions, I will try to cover as much as possible from the list above:

Arrays and Strings

Difference between an array and a linked list

An array is a collection of elements where each element is of the same type and can be accessed by its index. The size of an array is fixed upon creation. A linked list is a collection of objects known as a node where the node contains a value and references to the next (and previous — in doubly linked list) nodes. The size of a linked list can change dynamically.

Arrays are stored in a contiguous location. Linked lists are not stored in a contiguous location.
Arrays are Fixed in size. LinkedList is dynamic in size.
The array’s memory is allocated at compile time. LinkedList’s memory is allocated at run time.
Arrays use less memory than linked lists. LinkedList uses more memory because it stores both data and the address of the next node.

//Array:
int[] arr = new int[3]; //One Dimensional Array
int[] arr = {1, 2, 3};
int[] arr = new int[]{1, 2, 3};
int[][] num = new int[1][2]; //Multidimensional array

//LinkedList:
LinkedList<Integer> list = new LinkedList<>();
list.add(1);
list.add(2);

2. Reverse a string in place

In Java, strings (String class) are immutable, meaning that once created, their values cannot be changed. However, we can convert the string to a character array (char[]), reverse that in place, and then convert it back to a string.

public String reverseString(String input) {
        char[] chars = input.toCharArray();
        int left, right = 0;
        right = chars.length - 1;
 
        for (left = 0; left < right; left++, right--) {
            // Swap values of left and right
            char temp = chars[left];
            chars[left] = chars[right];
            chars[right] = temp;
        }
            System.out.println(String.valueOf(chars));
       
    }

3. Implement an algorithm to determine if a string has all unique characters

We can use a Set to keep track of characters we've seen. HashSet stores unique elements and permits nulls.

public boolean hasUniqueCharacters(String input) {
    Set<Character> seen = new HashSet<>();
    for (char c : input.toCharArray()) {
        if (seen.contains(c)) {
            return false;
        }
        seen.add(c);
    }
    return true;
}

Linked Lists

Find the middle of a linked list

The hint — Use two pointers(slow and fast). One moves one step at a time and the other moves two steps. When the faster pointer reaches the end, the slower pointer will be at the middle of the list. This is the simplest way to find the middle of a linked list.

...

public Node findMiddleNode() {
    Node slow = head;
   Node fast = head;
  
  while(fast !=null && fast.next!=null){
   slow = slow.next;
   fast = fast.next.next;
   
   }
    return slow;
  
}

2. Detect a cycle in a linked list:

The hint — Use Floyd’s cycle-finding algorithm (two pointers — slow and fast: one moves one step, the other moves two steps). Similar to finding a middle node just on each step comparing slow and fast nodes.

public class LinkedList {

    private Node head;
    private Node tail;
    private int length;

    class Node {
        int value;
        Node next;

        Node(int value) {
            this.value = value;
        }
    }

...

//the Method:
public boolean hasALoop() {
  Node slow = head;
  Node fast = head;

  while(fast !=null && fast.next !=null){
    slow = slow.next;
    fast = fast.next.next;
    if(slow == fast){
      return true;
       }
    }
    return false;
  }
}

3. Reverse the Linked List

This is a method that reverses the linked list by changing the order of the nodes in the list. The method starts by swapping the head and tail nodes of the list, which effectively reverses the direction of the list.

After swapping the head and tail nodes, the method then uses a loop to iterate through the nodes in the list and reverse the order of the links between the nodes.

public void reverseLinkedList() {
        Node temp = head;
        head = tail;
        tail = temp;
        Node after = temp.next;
        Node before = null;
        for (int i = 0; i < length; i++) {
        // Instead of the for loop you could use: 
        // while (temp != null) {

         // Set after to be the next node after the current node
        after = temp.next; 
        // Set the current node's next pointer to the previous node  
        temp.next = before; 
        // Set before to be the current node, 
        // as it will be the previous node in the next iteration of the loop 
        before = temp;  
        // Set temp to be the next node in the linked list     
        temp = after;   
        }
    }

Stacks and Queues

Implement a stack using arrays/linked list:

Use a dynamic array or a singly linked list with push/pop operations on the front.
Here is the example using the Linked List:

class Node {
    private int data;
    private Node next;

    public Node(int value) {
        data = value;
        next = null;
    }

    public int getData() {
        return data;
    }

    public void setData(int data) {
        this.data = data;
    }

    public Node getNext() {
        return next;
    }

    public void setNext(Node next) {
        this.next = next;
    }

}

class StackList {
    private Node head;
    private int length;

    public StackList() {
        length = 0;
        head = null;
    }

    public void push(int data) {
        Node temp = new Node(data);
        if (head == null) {
            head = temp;
        } else {
            temp.setNext(head);
            head = temp;
        }
        length++;
    }

    public int pop() {
        Node temp = head;
        int data = head.getData();
        head = head.getNext();
        temp = null;
        length--;
        return data;
    }

    public void display() {
        Node temp = head;
        if (isEmpty()) {
            System.out.println("Stack is empty");
        } else {
            while (temp != null) {
                System.out.print(temp.getData() + "=>");
                temp = temp.getNext();
            }
        }
        System.out.println();
    }

    public boolean isEmpty() {
        return (head == null);
    }

}

2. Design a Stack that, in addition to push and pop, also has a function min which returns the minimum element.

To design a stack that can efficiently return the minimum element, we can use an auxiliary stack to keep track of the minimum element seen so far. This stack will hold the minimum elements. Every time we push a new element onto the main stack, we compare it with the top of the min stack. If the new element is smaller, or the min stack is empty, we push the new element onto the min stack. If not, we push the current top of the min stack again. This ensures that the min stack always has the minimum element of the main stack at its top.

public class StackWithMin {
    private Stack<Integer> mainStack = new Stack<>();
    private Stack<Integer> minStack = new Stack<>();

    // Push operation
    public void push(int value) {
        mainStack.push(value);
        if (minStack.isEmpty() || value <= minStack.peek()) {
            minStack.push(value);
        } else {
            minStack.push(minStack.peek());
        }
    }

    // Pop operation
    public int pop() {
        if (mainStack.isEmpty()) {
            throw new RuntimeException("Stack is empty.");
        }
        minStack.pop();
        return mainStack.pop();
    }

    // Min function
    public int min() {
        if (minStack.isEmpty()) {
            throw new RuntimeException("Stack is empty.");
        }
        return minStack.peek();
    }

Trees and Graphs

Difference between a binary tree and a binary search tree

A Binary Tree is a basic structure with a simple rule that no parent must have more than 2 children whereas the Binary Search Tree is a variant of the binary tree following a particular order with which the nodes should be organized. A Binary Search Tree is as mentioned, a kind of binary tree. In a Binary Search Tree, a node can have two children, usually named left and right, where the value stored at left is always smaller (or maybe equal) to the value at right. This implies that all values at the left subtree are smaller or equal to the values on the right subtree.

2. Finding the lowest common ancestor (LCA) of two nodes in a binary tree:

Binary tree Lowest Common Ancestor in Binary Tree — Lowest Common Ancestor in Binary Tree

class Node {
    int data;
    Node left, right;
 
    public Node(int item)
    {
        data = item;
        left = right = null;
    }
}
 
public class BinaryTree {
    // Root of the Binary Tree
    Node root;
 
    Node findLCA(int n1, int n2){
        return findLCA(root, n1, n2);
    }
 
    // This function returns pointer to LCA of two given
    // values n1 and n2. This function assumes that n1 and
    // n2 are present in Binary Tree
    Node findLCA(Node node, int n1, int n2)
    {
        // Base case
        if (node == null)
            return null;
 
        // If either n1 or n2 matches with root's key,
        // report the presence by returning root (Note that
        // if a key is ancestor of other, then the ancestor
        // key becomes LCA
        if (node.data == n1 || node.data == n2)
            return node;
         // Look for keys in left and right subtrees
        Node left_lca = findLCA(node.left, n1, n2);
        Node right_lca = findLCA(node.right, n1, n2);
 
        // If both of the above calls return Non-NULL, then
        // one key is present in once subtree and other is
        // present in other, So this node is the LCA
        if (left_lca != null && right_lca != null)
            return node;
 
        // Otherwise check if left subtree or right subtree
        // is LCA
        return (left_lca != null) ? left_lca : right_lca;
    }