Java Data Structure & Algorithm Interview Questions & Answers
Qaisar Abbas
Sr. Software Engineer | Fintech | Java | Spring Boot | Microservices | Oracle DB | Containerization | Enterprise Software Architecture | Docker | Monolithic | System Design | EDD | SOA | DDD | Spring AI | CI/CD Pipline
A linked list is a linear data structure where elements are stored in a sequence, and each element points to the next one in the sequence. Here's a basic implementation in Java:
class Node {
int data;
Node next;
public Node(int data) {
this.data = data;
this.next = null;
}
}
class LinkedList {
Node head;
public void insert(int data) {
Node newNode = new Node(data);
if (head == null) {
head = newNode;
} else {
Node temp = head;
while (temp.next != null) {
temp = temp.next;
}
temp.next = newNode;
}
}
}
An array stores elements sequentially in memory with fixed size, whereas a linked list dynamically allocates memory for each element and stores them non-contiguously. Arrays have constant-time access, while linked lists have O(n) access time.
A stack is a linear data structure that follows the Last In, First Out (LIFO) principle. Elements can only be inserted or removed from the top of the stack. It supports two main operations: push (to insert) and pop (to remove).
class Stack {
private int maxSize;
private int[] stackArray;
private int top;
public Stack(int size) {
this.maxSize = size;
this.stackArray = new int[maxSize];
this.top = -1;
}
public void push(int data) {
if (top < maxSize - 1) {
stackArray[++top] = data;
} else {
System.out.println("Stack overflow!");
}
}
public int pop() {
if (top >= 0) {
return stackArray[top--];
} else {
System.out.println("Stack underflow!");
return -1;
}
}
}
Recursion is a programming technique where a function calls itself directly or indirectly to solve a problem. Example:
public class Factorial {
public static int factorial(int n) {
if (n == 0) {
return 1;
} else {
return n * factorial(n - 1);
}
}
public static void main(String[] args) {
int result = factorial(5);
System.out.println("Factorial of 5: " + result);
}
}
6. What is a binary search tree (BST) and how does it work?
A binary search tree is a binary tree where the value of each node's left child is less than the node's value, and the value of each node's right child is greater than the node's value. It allows for efficient searching, insertion, and deletion.
class Node {
int data;
Node left, right;
public Node(int data) {
this.data = data;
this.left = this.right = null;
}
}
class BST {
Node root;
public void insert(int data) {
root = insertRec(root, data);
}
private Node insertRec(Node root, int data) {
if (root == null) {
root = new Node(data);
return root;
}
if (data < root.data) {
root.left = insertRec(root.left, data);
} else if (data > root.data) {
root.right = insertRec(root.right, data);
}
return root;
}
}
7. Explain the concept of time complexity and space complexity.
Time complexity measures the amount of time an algorithm takes to run as a function of the length of its input. Space complexity measures the amount of memory an algorithm uses as a function of the length of its input.
8. What is the difference between breadth-first search (BFS) and depth-first search (DFS)?
BFS explores neighbors of a node before moving to the next level, while DFS explores as far as possible along each branch before backtracking.
9. Write a Java program to perform a breadth-first search (BFS) on a graph.
import java.util.LinkedList;
import java.util.Queue;
class Graph {
private int V;
private LinkedList<Integer>[] adj;
public Graph(int v) {
V = 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 BFS(int s) {
boolean visited[] = new boolean[V];
Queue<Integer> queue = new LinkedList<>();
visited[s] = true;
queue.add(s);
while (!queue.isEmpty()) {
s = queue.poll();
System.out.print(s + " ");
for (int n : adj[s]) {
if (!visited[n]) {
visited[n] = true;
queue.add(n);
}
}
}
}
public static void main(String args[]) {
Graph g = new Graph(4);
g.addEdge(0, 1);
g.addEdge(0, 2);
g.addEdge(1, 2);
g.addEdge(2, 0);
g.addEdge(2, 3);
g.addEdge(3, 3);
System.out.println("Following is Breadth First Traversal " +
"(starting from vertex 2)");
g.BFS(2);
}
}
10. Explain the concept of dynamic programming.
Dynamic programming is a method for solving complex problems by breaking them down into simpler subproblems and storing the solutions to those subproblems to avoid redundant calculations. It is typically used for optimization problems and problems with overlapping subproblems.
11. What is a hash table and how does it work?
A hash table is a data structure that stores key-value pairs. It uses a hash function to compute an index into an array of buckets or slots, from which the desired value can be found. Hash tables offer fast insertion, deletion, and lookup operations, with an average time complexity of O(1).
12. Implement a hash table in Java.
Here's a basic implementation of a hash table using separate chaining for collision resolution:
import java.util.LinkedList;
class MyHashMap {
private final int SIZE = 1000;
private LinkedList<Entry>[] table;
public MyHashMap() {
table = new LinkedList[SIZE];
for (int i = 0; i < SIZE; i++) {
table[i] = new LinkedList<>();
}
}
public void put(int key, int value) {
int index = key % SIZE;
for (Entry entry : table[index]) {
if (entry.key == key) {
entry.value = value;
return;
}
}
table[index].add(new Entry(key, value));
}
public int get(int key) {
int index = key % SIZE;
for (Entry entry : table[index]) {
if (entry.key == key) {
return entry.value;
}
}
return -1; // Not found
}
private class Entry {
int key;
int value;
public Entry(int key, int value) {
this.key = key;
this.value = value;
}
}
}
????
13. Explain the concept of a priority queue.
A priority queue is a data structure that stores elements based on their priorities. Elements with higher priorities are dequeued before elements with lower priorities. It supports operations like insertion and extraction of the highest (or lowest) priority element.
14. Implement a priority queue in Java.
Here's a basic implementation of a priority queue using a binary heap:
领英推荐
????
import java.util.PriorityQueue;
public class PriorityQueueExample {
public static void main(String[] args) {
PriorityQueue<Integer> pq = new PriorityQueue<>();
pq.add(5);
pq.add(2);
pq.add(8);
pq.add(1);
while (!pq.isEmpty()) {
System.out.print(pq.poll() + " ");
}
}
}
????
15. Explain the concept of a binary heap and its operations.
A binary heap is a complete binary tree where each node has a value greater than or equal to (max heap) or less than or equal to (min heap) the values of its children. It supports two main operations: insertion and extraction of the minimum or maximum element. Insertion maintains the heap property by bubbling the new element up to its correct position, and extraction removes the root element and rearranges the heap to maintain its property.
16. Implement a binary heap in Java.
Here's a basic implementation of a min heap in Java:
????class MinHeap {
private int[] heap;
private int size;
private int capacity;
public MinHeap(int capacity) {
this.capacity = capacity;
this.size = 0;
this.heap = new int[capacity];
}
private int parent(int i) {
return (i - 1) / 2;
}
private int leftChild(int i) {
return 2 * i + 1;
}
private int rightChild(int i) {
return 2 * i + 2;
}
private void swap(int i, int j) {
int temp = heap[i];
heap[i] = heap[j];
heap[j] = temp;
}
public void insert(int data) {
if (size == capacity) {
System.out.println("Heap is full!");
return;
}
size++;
int i = size - 1;
heap[i] = data;
while (i != 0 && heap[parent(i)] > heap[i]) {
swap(i, parent(i));
i = parent(i);
}
}
public int extractMin() {
if (size <= 0) {
System.out.println("Heap is empty!");
return -1;
}
if (size == 1) {
size--;
return heap[0];
}
int root = heap[0];
heap[0] = heap[size - 1];
size--;
minHeapify(0);
return root;
}
private void minHeapify(int i) {
int left = leftChild(i);
int right = rightChild(i);
int smallest = i;
if (left < size && heap[left] < heap[i])
smallest = left;
if (right < size && heap[right] < heap[smallest])
smallest = right;
if (smallest != i) {
swap(i, smallest);
minHeapify(smallest);
}
}
}
????
17. What is a trie data structure and where is it commonly used?
A trie (pronounced "try") is a tree-like data structure used to store a dynamic set of strings where each node represents a common prefix of its descendants. Tries are commonly used in text processing applications like autocomplete and spell checking.
18. Implement a trie data structure in Java.
Here's a basic implementation of a trie in Java:
? class TrieNode {
TrieNode[] children = new TrieNode[26];
boolean isEndOfWord;
TrieNode() {
isEndOfWord = false;
for (int i = 0; i < 26; i++)
children[i] = null;
}
}
class Trie {
private TrieNode root;
Trie() {
root = new TrieNode();
}
void insert(String key) {
TrieNode node = root;
for (int i = 0; i < key.length(); i++) {
int index = key.charAt(i) - 'a';
if (node.children[index] == null)
node.children[index] = new TrieNode();
node = node.children[index];
}
node.isEndOfWord = true;
}
boolean search(String key) {
TrieNode node = root;
for (int i = 0; i < key.length(); i++) {
int index = key.charAt(i) - 'a';
if (node.children[index] == null)
return false;
node = node.children[index];
}
return (node != null && node.isEndOfWord);
}
}
????
19. What is the difference between a stack and a queue?
Both stacks and queues are linear data structures, but they differ in the order of operations. In a stack, the last element added is the first one to be removed (Last In, First Out - LIFO), while in a queue, the first element added is the first one to be removed (First In, First Out - FIFO).
20. Implement a queue using two stacks in Java.
Here's an implementation of a queue using two stacks:
import java.util.Stack;
class QueueUsingStacks {
Stack<Integer> stack1 = new Stack<>();
Stack<Integer> stack2 = new Stack<>();
public void enqueue(int x) {
while (!stack1.isEmpty()) {
stack2.push(stack1.pop());
}
stack1.push(x);
while (!stack2.isEmpty()) {
stack1.push(stack2.pop());
}
}
public int dequeue() {
if (stack1.isEmpty()) {
System.out.println("Queue is empty!");
return -1;
}
return stack1.pop();
}
public int peek() {
if (stack1.isEmpty()) {
System.out.println("Queue is empty!");
return -1;
}
return stack1.peek();
}
public boolean isEmpty() {
return stack1.isEmpty();
}
}
????
21. Explain the concept of graph traversal and its types.
Graph traversal refers to the process of visiting all the nodes of a graph. Two common types of graph traversal are depth-first search (DFS) and breadth-first search (BFS). DFS explores as far as possible along each branch before backtracking, while BFS explores neighbors of a node before moving to the next level.
22. Implement depth-first search (DFS) for a graph in Java.
Here's a basic implementation of DFS for a graph:
import java.util.LinkedList;
class Graph {
private int V;
private LinkedList<Integer>[] adj;
public Graph(int v) {
V = 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 DFSUtil(int v, boolean[] visited) {
visited[v] = true;
System.out.print(v + " ");
for (int n : adj[v]) {
if (!visited[n]) {
DFSUtil(n, visited);
}
}
}
void DFS(int v) {
boolean[] visited = new boolean[V];
DFSUtil(v, visited);
}
}
????
23.? Explain the concept of divide and conquer.
Divide and conquer is a problem-solving technique where a problem is divided into smaller subproblems, solved independently, and then combined to find the solution to the original problem. It typically involves three steps: divide the problem into smaller subproblems, conquer the subproblems recursively, and combine the solutions of the subproblems.
24. Provide an example of a problem that can be solved using the divide and conquer approach.
One classic example is the merge sort algorithm, which follows the divide and conquer approach to sort an array. It divides the array into two halves, recursively sorts each half, and then merges the sorted halves to produce the final sorted array.
Thank You!
Follow Me for the latest updates!
Software Developer
5 个月Thank you, It was useful.
--
7 个月Thank you
DER BUNTE VOGEL ?? Internationaler Wissenstransfer - Influencerin bei Corporate Influencer Club | Wirtschaftswissenschaften
7 个月Thank you Qaisar Abbas