Popular Data Structures Asked in Java Interviews

Arrays

In Java, an array is a fixed-size collection of elements of the same data type. It allows you to store multiple values in a single variable. Each element in the array is accessed by its index, starting from 0. Arrays can be one-dimensional or multi-dimensional.

Here is an example of declaring and initializing a one-dimensional array in Java:

int[] numbers = {1, 2, 3, 4, 5};

And here is an example of declaring and initializing a two-dimensional array in Java:

int[][] matrix = {{1, 2, 3}, {4, 5, 6}, {7, 8, 9}};

Arrays are commonly used in Java interviews to solve various algorithmic problems. For example, you might be asked to find the maximum or minimum value in an array, reverse an array, or find the sum of all elements in an array.

Here is an example of finding the maximum value in an array:

public static int findMax(int[] array) {
    int max = array[0];
    for (int i = 1; i < array.length; i++) {
        if (array[i] > max) {
            max = array[i];
        }
    }
    return max;
}

And here is an example of reversing an array:

public static void reverseArray(int[] array) {
    int start = 0;
    int end = array.length - 1;
    while (start < end) {
        int temp = array[start];
        array[start] = array[end];
        array[end] = temp;
        start++;
        end--;
    }
}

Related Article: How To Parse JSON In Java

Linked Lists

A linked list is a data structure that consists of a sequence of nodes, where each node contains a value and a reference (or link) to the next node in the sequence. Unlike arrays, linked lists do not have a fixed size and can grow or shrink dynamically.

In Java, linked lists are commonly implemented using the LinkedList class from the java.util package. This class provides methods to add, remove, and access elements in the linked list.

Here is an example of creating a linked list in Java:

import java.util.LinkedList;

LinkedList<String> linkedList = new LinkedList<>();
linkedList.add("Apple");
linkedList.add("Banana");
linkedList.add("Orange");

Linked lists are useful in Java interviews for solving problems related to data manipulation and traversal. For example, you might be asked to reverse a linked list, find the middle element in a linked list, or detect if a linked list has a cycle.

Here is an example of reversing a linked list:

public static void reverseLinkedList(LinkedList<Node> linkedList) {
    Node previous = null;
    Node current = linkedList.getFirst();
    while (current != null) {
        Node next = current.next;
        current.next = previous;
        previous = current;
        current = next;
    }
    linkedList.setFirst(previous);
}

And here is an example of finding the middle element in a linked list:

public static Node findMiddleElement(LinkedList<Node> linkedList) {
    Node slow = linkedList.getFirst();
    Node fast = linkedList.getFirst();
    while (fast != null && fast.next != null) {
        slow = slow.next;
        fast = fast.next.next;
    }
    return slow;
}

Stacks

In Java, a stack is a data structure that follows the Last-In-First-Out (LIFO) principle. Elements are added and removed from the top of the stack. The java.util package provides the Stack class for implementing stacks in Java.

Here is an example of using a stack in Java:

import java.util.Stack;

Stack<Integer> stack = new Stack<>();
stack.push(1);
stack.push(2);
stack.push(3);

int top = stack.peek(); // Returns the top element (3)
int popped = stack.pop(); // Removes and returns the top element (3)

Stacks are commonly used in Java interviews for solving problems that involve nested structures or backtracking. For example, you might be asked to check if parentheses are balanced, evaluate a postfix expression, or implement depth-first search in a graph.

Here is an example of checking if parentheses are balanced using a stack:

public static boolean isBalanced(String input) {
    Stack<Character> stack = new Stack<>();
    for (int i = 0; i < input.length(); i++) {
        char c = input.charAt(i);
        if (c == '(' || c == '[' || c == '{') {
            stack.push(c);
        } else if (c == ')' || c == ']' || c == '}') {
            if (stack.isEmpty()) {
                return false;
            }
            char top = stack.pop();
            if ((c == ')' && top != '(') || (c == ']' && top != '[') || (c == '}' && top != '{')) {
                return false;
            }
        }
    }
    return stack.isEmpty();
}

Queues

In Java, a queue is a data structure that follows the First-In-First-Out (FIFO) principle. Elements are added to the rear (end) of the queue and removed from the front. The java.util package provides the Queue interface and the LinkedList class for implementing queues in Java.

Here is an example of using a queue in Java:

import java.util.Queue;
import java.util.LinkedList;

Queue<String> queue = new LinkedList<>();
queue.add("Apple");
queue.add("Banana");
queue.add("Orange");

String front = queue.peek(); // Returns the front element (Apple)
String dequeued = queue.poll(); // Removes and returns the front element (Apple)

Queues are commonly used in Java interviews for solving problems related to scheduling, resource allocation, and breadth-first search. For example, you might be asked to implement a queue using stacks, find the smallest window containing all elements of a list, or serialize and deserialize a binary tree.

Here is an example of finding the smallest window containing all elements of a list using a queue:

public static int findSmallestWindow(List<Integer> list, List<Integer> elements) {
    Map<Integer, Integer> elementCounts = new HashMap<>();
    for (int element : elements) {
        elementCounts.put(element, 0);
    }
    
    int left = 0;
    int right = 0;
    int minWindow = Integer.MAX_VALUE;
    int count = 0;
    
    while (right < list.size()) {
        int element = list.get(right);
        if (elementCounts.containsKey(element)) {
            int elementCount = elementCounts.get(element);
            if (elementCount == 0) {
                count++;
            }
            elementCounts.put(element, elementCount + 1);
        }
        
        while (count == elements.size()) {
            int windowSize = right - left + 1;
            if (windowSize < minWindow) {
                minWindow = windowSize;
            }
            
            int leftElement = list.get(left);
            if (elementCounts.containsKey(leftElement)) {
                int leftElementCount = elementCounts.get(leftElement);
                if (leftElementCount == 1) {
                    count--;
                }
                elementCounts.put(leftElement, leftElementCount - 1);
            }
            
            left++;
        }
        
        right++;
    }
    
    return minWindow;
}

Related Article: How To Convert Array To List In Java

Binary Trees

In Java, a binary tree is a hierarchical data structure where each node has at most two children, referred to as the left child and the right child. The java.util package does not provide a built-in implementation of binary trees, so you need to define your own class to represent a binary tree.

Here is an example of defining a binary tree class in Java:

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    
    public TreeNode(int val) {
        this.val = val;
    }
}

Binary trees are commonly used in Java interviews for solving problems related to searching, sorting, and traversing hierarchical data. For example, you might be asked to find the height of a binary tree, check if a binary tree is symmetric, or serialize and deserialize a binary tree.

Here is an example of finding the height of a binary tree:

public static int getHeight(TreeNode root) {
    if (root == null) {
        return 0;
    }
    
    int leftHeight = getHeight(root.left);
    int rightHeight = getHeight(root.right);
    
    return 1 + Math.max(leftHeight, rightHeight);
}

And here is an example of checking if a binary tree is symmetric:

public static boolean isSymmetric(TreeNode root) {
    if (root == null) {
        return true;
    }
    
    return isSymmetricHelper(root.left, root.right);
}

private static boolean isSymmetricHelper(TreeNode left, TreeNode right) {
    if (left == null && right == null) {
        return true;
    }
    
    if (left == null || right == null || left.val != right.val) {
        return false;
    }
    
    return isSymmetricHelper(left.left, right.right) && isSymmetricHelper(left.right, right.left);
}

Hash Tables

In Java, a hash table (also known as a hash map) is a data structure that allows you to store and retrieve key-value pairs efficiently. It uses a hash function to compute an index (or hash code) for each key, which is used to store and retrieve the corresponding value. The java.util package provides the HashMap class for implementing hash tables in Java.

Here is an example of using a hash table in Java:

import java.util.HashMap;

HashMap<String, Integer> hashMap = new HashMap<>();
hashMap.put("Apple", 1);
hashMap.put("Banana", 2);
hashMap.put("Orange", 3);

int value = hashMap.get("Apple"); // Returns the value associated with the key "Apple" (1)

Hash tables are commonly used in Java interviews for solving problems that involve efficient lookup, insert, and delete operations. For example, you might be asked to find the first non-repeating character in a string, find the intersection of two arrays, or implement a cache with a limited capacity.

Here is an example of finding the first non-repeating character in a string using a hash table:

public static char findFirstNonRepeating(String input) {
    HashMap<Character, Integer> charCounts = new HashMap<>();
    
    for (char c : input.toCharArray()) {
        charCounts.put(c, charCounts.getOrDefault(c, 0) + 1);
    }
    
    for (char c : input.toCharArray()) {
        if (charCounts.get(c) == 1) {
            return c;
        }
    }
    
    return '\0';
}

And here is an example of finding the intersection of two arrays using a hash table:

public static int[] findIntersection(int[] nums1, int[] nums2) {
    HashSet<Integer> set1 = new HashSet<>();
    HashSet<Integer> set2 = new HashSet<>();
    
    for (int num : nums1) {
        set1.add(num);
    }
    
    for (int num : nums2) {
        if (set1.contains(num)) {
            set2.add(num);
        }
    }
    
    int[] intersection = new int[set2.size()];
    int index = 0;
    for (int num : set2) {
        intersection[index++] = num;
    }
    
    return intersection;
}

Graphs

In Java, a graph is a data structure that represents a collection of nodes (or vertices) and the connections between them (or edges). The java.util package does not provide a built-in implementation of graphs, so you need to define your own classes to represent graphs and their components.

Here is an example of defining a graph class in Java:

class Graph {
    int V;
    LinkedList<Integer>[] adjacencyList;
    
    public Graph(int V) {
        this.V = V;
        this.adjacencyList = new LinkedList[V];
        for (int i = 0; i < V; i++) {
            this.adjacencyList[i] = new LinkedList<>();
        }
    }
    
    public void addEdge(int u, int v) {
        this.adjacencyList[u].add(v);
        this.adjacencyList[v].add(u);
    }
}

Graphs are commonly used in Java interviews for solving problems related to pathfinding, connectivity, and graph traversal algorithms. For example, you might be asked to find the shortest path between two nodes, check if a graph is bipartite, or perform a topological sort.

Here is an example of finding the shortest path between two nodes using breadth-first search:

public static int shortestPath(Graph graph, int start, int end) {
    if (start == end) {
        return 0;
    }
    
    Queue<Integer> queue = new LinkedList<>();
    boolean[] visited = new boolean[graph.V];
    int[] distance = new int[graph.V];
    
    queue.add(start);
    visited[start] = true;
    
    while (!queue.isEmpty()) {
        int node = queue.poll();
        
        for (int neighbor : graph.adjacencyList[node]) {
            if (!visited[neighbor]) {
                queue.add(neighbor);
                visited[neighbor] = true;
                distance[neighbor] = distance[node] + 1;
                
                if (neighbor == end) {
                    return distance[neighbor];
                }
            }
        }
    }
    
    return -1; // No path found
}

And here is an example of performing a topological sort on a directed acyclic graph:

public static List<Integer> topologicalSort(Graph graph) {
    List<Integer> result = new ArrayList<>();
    boolean[] visited = new boolean[graph.V];
    
    for (int i = 0; i < graph.V; i++) {
        if (!visited[i]) {
            topologicalSortHelper(graph, i, visited, result);
        }
    }
    
    Collections.reverse(result);
    return result;
}

private static void topologicalSortHelper(Graph graph, int node, boolean[] visited, List<Integer> result) {
    visited[node] = true;
    
    for (int neighbor : graph.adjacencyList[node]) {
        if (!visited[neighbor]) {
            topologicalSortHelper(graph, neighbor, visited, result);
        }
    }
    
    result.add(node);
}

Related Article: How To Iterate Over Entries In A Java Map

Heaps

In Java, a heap is a complete binary tree that satisfies the heap property. The heap property states that for any given node, the value of the node is greater than or equal to the values of its children (for a max heap) or less than or equal to the values of its children (for a min heap). The java.util package provides the PriorityQueue class for implementing heaps in Java.

Here is an example of using a heap in Java:

import java.util.PriorityQueue;

PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Collections.reverseOrder());
maxHeap.add(5);
maxHeap.add(3);
maxHeap.add(7);

int max = maxHeap.peek(); // Returns the maximum value (7)
int removed = maxHeap.poll(); // Removes and returns the maximum value (7)

Heaps are commonly used in Java interviews for solving problems that involve finding the kth largest or smallest element, sorting elements in non-decreasing or non-increasing order, or implementing priority queues.

Here is an example of finding the kth largest element using a max heap:

public static int findKthLargest(int[] nums, int k) {
    PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Collections.reverseOrder());
    
    for (int num : nums) {
        maxHeap.add(num);
    }
    
    for (int i = 1; i < k; i++) {
        maxHeap.poll();
    }
    
    return maxHeap.peek();
}

And here is an example of sorting elements in non-decreasing order using a min heap:

public static void sort(int[] nums) {
    PriorityQueue<Integer> minHeap = new PriorityQueue<>();
    
    for (int num : nums) {
        minHeap.add(num);
    }
    
    int index = 0;
    while (!minHeap.isEmpty()) {
        nums[index++] = minHeap.poll();
    }
}

Priority Queues

In Java, a priority queue is a special type of queue where each element has a priority associated with it. Elements with higher priority are dequeued first. The java.util package provides the PriorityQueue class for implementing priority queues in Java.

Here is an example of using a priority queue in Java:

import java.util.PriorityQueue;

PriorityQueue<Integer> priorityQueue = new PriorityQueue<>();
priorityQueue.add(5);
priorityQueue.add(3);
priorityQueue.add(7);

int top = priorityQueue.peek(); // Returns the element with the highest priority (3)
int dequeued = priorityQueue.poll(); // Removes and returns the element with the highest priority (3)

Priority queues are commonly used in Java interviews for solving problems that involve scheduling, task prioritization, and event-driven simulations. For example, you might be asked to merge k sorted lists, find the k closest points to the origin, or implement Dijkstra’s algorithm.

Here is an example of merging k sorted lists using a priority queue:

public static ListNode mergeKLists(ListNode[] lists) {
    PriorityQueue<ListNode> minHeap = new PriorityQueue<>((a, b) -> a.val - b.val);
    
    for (ListNode list : lists) {
        if (list != null) {
            minHeap.add(list);
        }
    }
    
    ListNode dummy = new ListNode(0);
    ListNode current = dummy;
    
    while (!minHeap.isEmpty()) {
        ListNode node = minHeap.poll();
        current.next = node;
        current = current.next;
        
        if (node.next != null) {
            minHeap.add(node.next);
        }
    }
    
    return dummy.next;
}

And here is an example of finding the k closest points to the origin using a priority queue:

public static int[][] kClosest(int[][] points, int k) {
    PriorityQueue<int[]> maxHeap = new PriorityQueue<>((a, b) -> getDistance(b) - getDistance(a));
    
    for (int[] point : points) {
        maxHeap.add(point);
        
        if (maxHeap.size() > k) {
            maxHeap.poll();
        }
    }
    
    int[][] result = new int[k][2];
    int index = 0;
    
    while (!maxHeap.isEmpty()) {
        result[index++] = maxHeap.poll();
    }
    
    return result;
}

private static int getDistance(int[] point) {
    return point[0] * point[0] + point[1] * point[1];
}

Trie

In Java, a trie (also known as a prefix tree) is a tree-like data structure that stores a collection of strings. Each node in the trie represents a prefix or a whole string, and the edges represent the characters that make up the strings. The java.util package does not provide a built-in implementation of tries, so you need to define your own class to represent a trie.

Here is an example of defining a trie class in Java:

class TrieNode {
    boolean isWord;
    TrieNode[] children;
    
    public TrieNode() {
        this.isWord = false;
        this.children = new TrieNode[26];
    }
}

Tries are commonly used in Java interviews for solving problems related to string manipulation, dictionary-based searching, and autocompletion. For example, you might be asked to implement a spell checker, find all words that start with a given prefix, or serialize and deserialize a trie.

Here is an example of implementing a spell checker using a trie:

class Trie {
    TrieNode root;
    
    public Trie() {
        this.root = new TrieNode();
    }
    
    public void insert(String word) {
        TrieNode current = root;
        for (char c : word.toCharArray()) {
            int index = c - 'a';
            if (current.children[index] == null) {
                current.children[index] = new TrieNode();
            }
            current = current.children[index];
        }
        current.isWord = true;
    }
    
    public boolean search(String word) {
        TrieNode current = root;
        for (char c : word.toCharArray()) {
            int index = c - 'a';
            if (current.children[index] == null) {
                return false;
            }
            current = current.children[index];
        }
        return current.isWord;
    }
    
    public boolean startsWith(String prefix) {
        TrieNode current = root;
        for (char c : prefix.toCharArray()) {
            int index = c - 'a';
            if (current.children[index] == null) {
                return false;
            }
            current = current.children[index];
        }
        return true;
    }
}

And here is an example of finding all words that start with a given prefix using a trie:

class Trie {
    // ...

    public List<String> searchPrefix(String prefix) {
        List<String> result = new ArrayList<>();
        TrieNode current = root;
        
        for (char c : prefix.toCharArray()) {
            int index = c - 'a';
            if (current.children[index] == null) {
                return result;
            }
            current = current.children[index];
        }
        
        searchPrefixHelper(current, prefix, result);
        return result;
    }
    
    private void searchPrefixHelper(TrieNode node, String prefix, List<String> result) {
        if (node.isWord) {
            result.add(prefix);
        }
        
        for (int i = 0; i < 26; i++) {
            TrieNode child = node.children[i];
            if (child != null) {
                char c = (char) ('a' + i);
                searchPrefixHelper(child, prefix + c, result);
            }
        }
    }
}

Related Article: How To Split A String In Java

Using Data Structures to Solve Algorithmic Problems in Java

Data structures play a crucial role in solving algorithmic problems in Java interviews. By choosing the right data structure for a given problem, you can optimize your solution for efficiency and readability.

Here are some examples of how data structures can be used to solve algorithmic problems in Java:

– Arrays: Arrays are often used to store and manipulate collections of elements. They are useful for problems that require random access or efficient indexing, such as finding the maximum or minimum value, sorting elements, or searching for a specific value.

– Linked Lists: Linked lists are useful for problems that involve dynamic data structures or frequent insertions and deletions. They can be used to implement stacks, queues, and other data structures. Linked lists are also used in problems that require traversal or manipulation of nodes, such as reversing a linked list or finding the middle element.

– Stacks: Stacks are useful for problems that involve nested structures, backtracking, or depth-first search. They can be used to implement function call stacks, evaluate expressions, or check if parentheses are balanced.

– Queues: Queues are useful for problems that involve scheduling, resource allocation, or breadth-first search. They can be used to implement task queues, simulate process scheduling, or find the shortest path in a graph.

– Binary Trees: Binary trees are useful for problems that involve hierarchical data or binary search. They can be used to implement binary search trees, perform tree traversal, or balance a tree.

– Hash Tables: Hash tables are useful for problems that involve efficient lookup, insert, or delete operations. They can be used to implement dictionaries, caches, or find duplicate elements.

– Graphs: Graphs are useful for problems that involve connectivity, pathfinding, or graph traversal. They can be used to implement graph algorithms, such as depth-first search, breadth-first search, or Dijkstra’s algorithm.

– Heaps: Heaps are useful for problems that involve prioritization or finding the kth largest or smallest element. They can be used to implement priority queues, find the median of a stream of numbers, or sort elements in non-decreasing or non-increasing order.

– Priority Queues: Priority queues are useful for problems that involve scheduling, task prioritization, or event-driven simulations. They can be used to implement event queues, find the k closest points, or merge k sorted lists.

– Tries: Tries are useful for problems that involve string manipulation, dictionary-based searching, or autocompletion. They can be used to implement spell checkers, find all words that start with a given prefix, or serialize and deserialize a trie.

Additional Resources

– Baeldung – Binary Tree Implementation in Java
– Baeldung – Queue in Java