Interview Bite

Preparing for tech interviews? Mastering Data Structures and Algorithms (DSA) in Java is essential to crack interviews at companies like Amazon, Infosys, TCS, Google, and other top product or service-based companies.

In this article, we’ll cover the most commonly asked Java DSA interview questions with simple code examples, explanations, and best practices.

---

🔹 1. What are the key data structures used in Java?

Java provides a wide range of built-in data structures:

• Array
• ArrayList
• LinkedList
• HashMap
• HashSet
• Stack
• Queue
• TreeMap
• PriorityQueue

These are available under the java.util package and form the base of most DSA questions in interviews.

---

🔹 2. Reverse a Linked List in Java (Iterative)

javaCopyEditclass Node {
    int data;
    Node next;
}

public Node reverse(Node head) {
    Node prev = null;
    Node current = head;
    while (current != null) {
        Node next = current.next;
        current.next = prev;
        prev = current;
        current = next;
    }
    return prev;
}

📌 Asked by: Cognizant, Capgemini

---

🔹 3. Implement a Stack using Array in Java

javaCopyEditclass Stack {
    int top = -1;
    int[] stack = new int[100];

    void push(int val) {
        if (top < stack.length - 1) {
            stack[++top] = val;
        }
    }

    int pop() {
        if (top >= 0) {
            return stack[top--];
        }
        return -1;
    }
}

✅ Key Concepts: Array, OOP, Stack operations

---

🔹 4. Find the First Non-Repeating Character in a String

javaCopyEditpublic char firstNonRepeating(String s) {
    int[] freq = new int[256];
    for (char c : s.toCharArray()) freq[c]++;
    for (char c : s.toCharArray()) {
        if (freq[c] == 1) return c;
    }
    return '_';
}

---

🔹 5. What is the difference between ArrayList and LinkedList?

Feature	ArrayList	LinkedList
Access Time	Fast (O(1))	Slow (O(n))
Insertion/Deletion	Slower (O(n))	Faster (O(1) at head)
Memory Usage	Less	More (due to pointers)

✅ Use Case: Use ArrayList for fast access, LinkedList for fast insertions.

---

🔹 6. Java Program to Detect Loop in a Linked List

javaCopyEditpublic boolean hasLoop(Node head) {
    Node slow = head, fast = head;
    while (fast != null && fast.next != null) {
        slow = slow.next;
        fast = fast.next.next;
        if (slow == fast) return true;
    }
    return false;
}

📌 Asked in: Accenture, Infosys, Wipro

---

🔹 7. Explain HashMap and how it works internally.

• HashMap stores key-value pairs.
• Internally uses hashing to locate the bucket.
• Handles collisions using chaining (LinkedList) or open addressing.
• Complexity: O(1) average, O(n) worst-case for get() and put().

---

🔹 8. Java Program for Binary Search

javaCopyEditpublic int binarySearch(int[] arr, int key) {
    int low = 0, high = arr.length - 1;
    while (low <= high) {
        int mid = (low + high) / 2;
        if (arr[mid] == key) return mid;
        if (arr[mid] < key) low = mid + 1;
        else high = mid - 1;
    }
    return -1;
}

---

🔹 9. What is TreeSet in Java?

• Stores unique elements in sorted (ascending) order.
• Based on Red-Black Tree.
• Operations like add(), remove(), contains() take O(log n).

---

🔹 10. Java Code for Depth-First Search (DFS) in a Graph

javaCopyEditvoid dfs(int v, boolean[] visited, List<List<Integer>> graph) {
    visited[v] = true;
    System.out.print(v + " ");
    for (int u : graph.get(v)) {
        if (!visited[u]) {
            dfs(u, visited, graph);
        }
    }
}

---

📌 Pro Tips for Java DSA Interviews

• Always explain time and space complexity
• Use Java’s Collections Framework smartly
• Practice on platforms like LeetCode, GeeksforGeeks, and InterviewBit
• Be prepared to optimize your solution if asked

---

🔚 Final Thoughts

Mastering DSA in Java is crucial if you want to crack technical rounds confidently. The questions listed above cover beginner to intermediate concepts with real interview-level depth. Be sure to practice writing Java code under timed conditions.