15 Data Structures in Java Interview Questions and Answers

Data structures are fundamental to efficient algorithm design and are a core component of computer science. In Java, understanding data structures is crucial for developing robust and high-performance applications. Java provides a rich set of built-in data structures, such as arrays, linked lists, stacks, queues, and hash maps, which are essential for solving complex problems and optimizing code.

This article offers a curated selection of interview questions focused on data structures in Java. By working through these questions and their detailed answers, you will gain a deeper understanding of how to implement and manipulate various data structures, enhancing your problem-solving skills and preparing you for technical interviews.

Data Structures in Java Interview Questions and Answers

1. Compare the performance characteristics and use cases of ArrayList and LinkedList.

ArrayList:

• Time Complexity: Provides O(1) time complexity for accessing elements via the get() method. Adding or removing elements, especially in the middle, can be costly with O(n) time complexity due to shifting elements.
• Memory Usage: Requires contiguous memory allocation, leading to memory overhead if resized frequently.
• Use Cases: Ideal for scenarios requiring fast access to elements, such as in read-heavy applications.

LinkedList:

• Time Complexity: Offers O(1) time complexity for adding or removing elements at the beginning or end. Accessing elements via the get() method has O(n) time complexity due to traversal requirements.
• Memory Usage: Requires additional memory for storing pointers, leading to higher memory consumption compared to ArrayList.
• Use Cases: Suitable for scenarios with frequent insertions and deletions, especially at the beginning or end.

2. Explain how HashMap works internally, including hashing, collision resolution, and load factor.

HashMap in Java is used to store key-value pairs. Internally, it uses an array of buckets to store entries. Each bucket is a linked list holding entries that hash to the same index.

• Hashing: A key’s hashCode() method computes an integer hash code, transformed into an index in the array of buckets using index = hashCode % array.length.
• Collision Resolution: Uses chaining to resolve collisions, where each bucket contains a linked list of entries with the same index.
• Load Factor: Measures how full the HashMap can get before its capacity increases. The default load factor is 0.75, meaning resizing occurs when 75% full.

3. Write a function to find the middle element of a singly linked list.

To find the middle element of a singly linked list, use the two-pointer technique. A slow pointer moves one step at a time, while a fast pointer moves two steps. When the fast pointer reaches the end, the slow pointer will be at the middle element.

Example:

class ListNode {
    int val;
    ListNode next;
    ListNode(int x) {
        val = x;
        next = null;
    }
}

public class LinkedList {
    public ListNode findMiddle(ListNode head) {
        if (head == null) return null;

        ListNode slow = head;
        ListNode fast = head;

        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }

        return slow;
    }
}

4. Write a function to check if a string has balanced parentheses using a stack.

To check if a string has balanced parentheses using a stack, utilize the Last In, First Out (LIFO) property. Traverse the string and use the stack to track opening parentheses. When a closing parenthesis is encountered, check if it matches the top of the stack. If it does, pop the stack; otherwise, the parentheses are not balanced.

Example:

import java.util.Stack;

public class BalancedParentheses {
    public static boolean isBalanced(String s) {
        Stack<Character> stack = new Stack<>();
        for (char c : s.toCharArray()) {
            if (c == '(') {
                stack.push(c);
            } else if (c == ')') {
                if (stack.isEmpty() || stack.pop() != '(') {
                    return false;
                }
            }
        }
        return stack.isEmpty();
    }

    public static void main(String[] args) {
        System.out.println(isBalanced("(())")); // true
        System.out.println(isBalanced("(()"));  // false
    }
}

5. Write a function to detect a cycle in a directed graph using Depth-First Search (DFS).

Cycle detection in a directed graph can be performed using Depth-First Search (DFS). Traverse the graph using DFS and track nodes in the recursion stack. If a node is already in the stack, a cycle is detected.

Here is an implementation in Java:

import java.util.*;

public class Graph {
    private final int V;
    private final List<List<Integer>> adj;

    public Graph(int V) {
        this.V = V;
        adj = new ArrayList<>(V);
        for (int i = 0; i < V; i++) {
            adj.add(new LinkedList<>());
        }
    }

    public void addEdge(int source, int dest) {
        adj.get(source).add(dest);
    }

    private boolean isCyclicUtil(int i, boolean[] visited, boolean[] recStack) {
        if (recStack[i]) {
            return true;
        }
        if (visited[i]) {
            return false;
        }
        visited[i] = true;
        recStack[i] = true;
        List<Integer> children = adj.get(i);
        for (Integer c : children) {
            if (isCyclicUtil(c, visited, recStack)) {
                return true;
            }
        }
        recStack[i] = false;
        return false;
    }

    public boolean isCyclic() {
        boolean[] visited = new boolean[V];
        boolean[] recStack = new boolean[V];
        for (int i = 0; i < V; i++) {
            if (isCyclicUtil(i, visited, recStack)) {
                return true;
            }
        }
        return false;
    }

    public static void main(String[] args) {
        Graph graph = new Graph(4);
        graph.addEdge(0, 1);
        graph.addEdge(1, 2);
        graph.addEdge(2, 0);
        graph.addEdge(2, 3);
        System.out.println("Graph contains cycle: " + graph.isCyclic());
    }
}

6. Implement an LRU (Least Recently Used) cache.

An LRU (Least Recently Used) cache removes the least recently accessed items first. It can be implemented using a combination of a HashMap and a doubly linked list. The HashMap provides O(1) access time for cache hits, while the doubly linked list maintains the order of access.

Here is an implementation of an LRU cache in Java:

import java.util.*;

class LRUCache<K, V> {
    private final int capacity;
    private final Map<K, V> map;
    private final LinkedList<K> list;

    public LRUCache(int capacity) {
        this.capacity = capacity;
        this.map = new HashMap<>();
        this.list = new LinkedList<>();
    }

    public V get(K key) {
        if (!map.containsKey(key)) {
            return null;
        }
        list.remove(key);
        list.addFirst(key);
        return map.get(key);
    }

    public void put(K key, V value) {
        if (map.containsKey(key)) {
            list.remove(key);
        } else if (map.size() == capacity) {
            K leastUsedKey = list.removeLast();
            map.remove(leastUsedKey);
        }
        list.addFirst(key);
        map.put(key, value);
    }
}

7. Write a function to find the Kth smallest element in a Binary Search Tree (BST).

To find the Kth smallest element in a Binary Search Tree (BST), perform an in-order traversal, which visits nodes in ascending order. By keeping a counter, determine when the Kth smallest element is reached.

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode(int x) { val = x; }
}

public class KthSmallestElement {
    private int count = 0;
    private int result = -1;

    public int kthSmallest(TreeNode root, int k) {
        inOrderTraversal(root, k);
        return result;
    }

    private void inOrderTraversal(TreeNode node, int k) {
        if (node == null) {
            return;
        }
        inOrderTraversal(node.left, k);
        count++;
        if (count == k) {
            result = node.val;
            return;
        }
        inOrderTraversal(node.right, k);
    }
}

8. Explain the Union-Find algorithm and its applications.

The Union-Find algorithm consists of two primary operations: find and union. The find operation determines the root of the set containing a particular element, while the union operation merges two sets into one.

Example:

class UnionFind {
    private int[] parent;
    private int[] rank;

    public UnionFind(int size) {
        parent = new int[size];
        rank = new int[size];
        for (int i = 0; i < size; i++) {
            parent[i] = i;
            rank[i] = 0;
        }
    }

    public int find(int x) {
        if (parent[x] != x) {
            parent[x] = find(parent[x]); // Path compression
        }
        return parent[x];
    }

    public void union(int x, int y) {
        int rootX = find(x);
        int rootY = find(y);

        if (rootX != rootY) {
            if (rank[rootX] > rank[rootY]) {
                parent[rootY] = rootX;
            } else if (rank[rootX] < rank[rootY]) {
                parent[rootX] = rootY;
            } else {
                parent[rootY] = rootX;
                rank[rootX]++;
            }
        }
    }
}

9. Write functions to serialize and deserialize a binary tree.

Serialization and deserialization of a binary tree are operations for storing and reconstructing the tree structure. Serialization converts the tree into a string format, which can be easily stored or transmitted. Deserialization reconstructs the tree from the string format.

Here is an example in Java:

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

public class Codec {

    // Encodes a tree to a single string.
    public String serialize(TreeNode root) {
        if (root == null) return "null,";
        return root.val + "," + serialize(root.left) + serialize(root.right);
    }

    // Decodes your encoded data to tree.
    public TreeNode deserialize(String data) {
        Queue<String> nodes = new LinkedList<>(Arrays.asList(data.split(",")));
        return deserializeHelper(nodes);
    }

    private TreeNode deserializeHelper(Queue<String> nodes) {
        String val = nodes.poll();
        if (val.equals("null")) return null;
        TreeNode node = new TreeNode(Integer.parseInt(val));
        node.left = deserializeHelper(nodes);
        node.right = deserializeHelper(nodes);
        return node;
    }
}

10. Write a function to perform Topological Sort on a Directed Acyclic Graph (DAG).

Topological Sort is a linear ordering of vertices in a Directed Acyclic Graph (DAG) such that for every directed edge u -> v, vertex u comes before vertex v in the ordering. This is useful in scenarios like task scheduling and course prerequisite ordering.

To perform a Topological Sort, use Depth-First Search (DFS).

import java.util.*;

public class TopologicalSort {
    private int vertices;
    private LinkedList<Integer> adj[];

    TopologicalSort(int v) {
        vertices = v;
        adj = new LinkedList[v];
        for (int i = 0; i < v; ++i)
            adj[i] = new LinkedList();
    }

    void addEdge(int v, int w) {
        adj[v].add(w);
    }

    void topologicalSortUtil(int v, boolean visited[], Stack<Integer> stack) {
        visited[v] = true;
        Integer i;

        for (Integer neighbor : adj[v]) {
            if (!visited[neighbor])
                topologicalSortUtil(neighbor, visited, stack);
        }

        stack.push(v);
    }

    void topologicalSort() {
        Stack<Integer> stack = new Stack<>();
        boolean visited[] = new boolean[vertices];

        for (int i = 0; i < vertices; i++) {
            if (!visited[i])
                topologicalSortUtil(i, visited, stack);
        }

        while (!stack.isEmpty())
            System.out.print(stack.pop() + " ");
    }

    public static void main(String args[]) {
        TopologicalSort g = new TopologicalSort(6);
        g.addEdge(5, 2);
        g.addEdge(5, 0);
        g.addEdge(4, 0);
        g.addEdge(4, 1);
        g.addEdge(2, 3);
        g.addEdge(3, 1);

        System.out.println("Topological Sort of the given graph:");
        g.topologicalSort();
    }
}

11. Implement a Priority Queue using a heap.

A priority queue allows for the efficient retrieval of the highest (or lowest) priority element. It can be implemented using a binary heap, which is a complete binary tree where each node is smaller (in a min-heap) or larger (in a max-heap) than its children.

Here is an implementation of a priority queue using a min-heap in Java:

import java.util.ArrayList;
import java.util.List;

public class PriorityQueue {
    private List<Integer> heap = new ArrayList<>();

    public void insert(int value) {
        heap.add(value);
        heapifyUp(heap.size() - 1);
    }

    public int extractMin() {
        if (heap.isEmpty()) {
            throw new IllegalStateException("Heap is empty");
        }
        int min = heap.get(0);
        int last = heap.remove(heap.size() - 1);
        if (!heap.isEmpty()) {
            heap.set(0, last);
            heapifyDown(0);
        }
        return min;
    }

    private void heapifyUp(int index) {
        while (index > 0) {
            int parentIndex = (index - 1) / 2;
            if (heap.get(index) >= heap.get(parentIndex)) {
                break;
            }
            swap(index, parentIndex);
            index = parentIndex;
        }
    }

    private void heapifyDown(int index) {
        int size = heap.size();
        while (index < size) {
            int leftChild = 2 * index + 1;
            int rightChild = 2 * index + 2;
            int smallest = index;

            if (leftChild < size && heap.get(leftChild) < heap.get(smallest)) {
                smallest = leftChild;
            }
            if (rightChild < size && heap.get(rightChild) < heap.get(smallest)) {
                smallest = rightChild;
            }
            if (smallest == index) {
                break;
            }
            swap(index, smallest);
            index = smallest;
        }
    }

    private void swap(int i, int j) {
        int temp = heap.get(i);
        heap.set(i, heap.get(j));
        heap.set(j, temp);
    }
}

12. Write a function to perform Range Sum Query using a Segment Tree.

A Segment Tree allows querying the sum of elements in a given range efficiently. It is useful for scenarios with multiple queries and updates on an array. Each node represents a segment of the array, and the value of the node is the sum of the elements in that segment.

Here is an implementation of a Segment Tree in Java to perform range sum queries:

class SegmentTree {
    private int[] tree;
    private int n;

    public SegmentTree(int[] arr) {
        n = arr.length;
        tree = new int[2 * n];
        buildTree(arr);
    }

    private void buildTree(int[] arr) {
        for (int i = 0; i < n; i++) {
            tree[n + i] = arr[i];
        }
        for (int i = n - 1; i > 0; --i) {
            tree[i] = tree[i * 2] + tree[i * 2 + 1];
        }
    }

    public void update(int pos, int value) {
        pos += n;
        tree[pos] = value;
        while (pos > 1) {
            pos /= 2;
            tree[pos] = tree[2 * pos] + tree[2 * pos + 1];
        }
    }

    public int rangeSum(int left, int right) {
        left += n;
        right += n;
        int sum = 0;
        while (left <= right) {
            if ((left % 2) == 1) sum += tree[left++];
            if ((right % 2) == 0) sum += tree[right--];
            left /= 2;
            right /= 2;
        }
        return sum;
    }
}

13. Explain the concept of persistent data structures and their practical applications.

Persistent data structures preserve their previous versions when modified. Instead of altering the original structure, operations create new versions that share parts of the old structure. This is achieved through structural sharing, ensuring unchanged parts are reused, minimizing memory overhead.

In Java, persistent data structures can be implemented using libraries such as Vavr, which provides immutable collections like lists, maps, and sets. These collections are designed to be efficient in both time and space, leveraging structural sharing to maintain performance.

Practical applications include:

• Version Control Systems: Used to track changes over time, allowing users to revert to previous states.
• Functional Programming: Aligns well with the immutability principle.
• Undo/Redo Functionality: Maintains a history of states.
• Concurrency: Inherently thread-safe, suitable for concurrent programming.

14. Explain the differences between HashMap, TreeMap, and LinkedHashMap.

HashMap, TreeMap, and LinkedHashMap are implementations of the Map interface in Java, each with different characteristics.

• HashMap
  • *Underlying Data Structure*: Hash table
  • *Ordering*: No guaranteed order
  • *Performance*: O(1) time complexity for get and put operations on average
  • *Use Case*: Fast access without caring about order
• TreeMap
  • *Underlying Data Structure*: Red-Black tree
  • *Ordering*: Sorted according to natural ordering or a specified comparator
  • *Performance*: O(log n) time complexity for get and put operations
  • *Use Case*: When sorted order is needed
• LinkedHashMap
  • *Underlying Data Structure*: Hash table and linked list
  • *Ordering*: Maintains insertion or access order
  • *Performance*: O(1) time complexity for get and put operations on average
  • *Use Case*: Maintaining order of elements as inserted or accessed

15. Compare and contrast the performance of different List implementations in Java (ArrayList, LinkedList, CopyOnWriteArrayList).

ArrayList:
Backed by a dynamic array, allowing fast random access (O(1) time complexity). Insertion and deletion can be costly (O(n) time complexity) due to element shifting. Preferred for frequent read operations.

LinkedList:
Implemented as a doubly-linked list, allowing efficient insertion and deletion (O(1) time complexity) if the position is known. Random access is slower (O(n) time complexity) due to traversal. Suitable for frequent insertions and deletions.

CopyOnWriteArrayList:
A thread-safe variant of ArrayList, creating a new copy of the underlying array for each modification. Slower write operations (O(n) time complexity) but fast, thread-safe read operations (O(1) time complexity). Ideal for read-heavy, thread-safe use cases.