Data Structures and Algorithms in Java
Explain the difference between an ArrayList and a LinkedList in Java.
Answer:
ArrayList uses a dynamic array internally, providing O(1) average time for random access but O(n) for insertions/deletions in the middle. LinkedList uses a doubly linked list, offering O(1) for insertions/deletions at ends but O(n) for random access and middle operations due to traversal.
When would you use a HashMap over a TreeMap in Java?
Answer:
Use a HashMap when you need fast average-case O(1) performance for insertions, deletions, and lookups, and the order of elements does not matter. Use a TreeMap when you need elements to be stored in a sorted order based on their keys, as it provides O(log n) performance for operations.
Describe the concept of Big O notation and its importance in algorithm analysis.
Answer:
Big O notation describes the upper bound or worst-case complexity of an algorithm's running time or space requirements as the input size grows. It's crucial for comparing algorithm efficiency, predicting performance, and choosing the most suitable algorithm for a given problem, especially with large datasets.
What is a 'Stack' data structure, and what are its primary operations?
Answer:
A Stack is a LIFO (Last-In, First-Out) data structure. Its primary operations are push (adds an element to the top), pop (removes and returns the top element), and peek (returns the top element without removing it). It's often used for function call management and expression evaluation.
How does a 'Queue' data structure differ from a Stack, and what are its common uses?
Answer:
A Queue is a FIFO (First-In, First-Out) data structure, unlike a Stack's LIFO. Elements are added at the rear (offer/add) and removed from the front (poll/remove). Common uses include task scheduling, breadth-first search (BFS), and managing shared resources.
Explain the concept of 'hashing' and how it's used in HashMaps.
Answer:
Hashing is the process of converting an input (or key) into a fixed-size value (hash code) using a hash function. In HashMaps, this hash code determines the bucket where a key-value pair is stored, enabling fast average-case O(1) retrieval. Collisions are handled typically by separate chaining (linked lists) or open addressing.
What is a 'tree' data structure, and what is a 'binary search tree' (BST)?
Answer:
A tree is a hierarchical data structure consisting of nodes connected by edges, with a single root node. A Binary Search Tree (BST) is a special type of binary tree where for every node, all keys in its left subtree are smaller than its key, and all keys in its right subtree are larger.
Briefly explain the difference between Depth-First Search (DFS) and Breadth-First Search (BFS) for graph traversal.
Answer:
DFS explores as far as possible along each branch before backtracking, typically using a stack (or recursion). BFS explores all neighbor nodes at the current depth level before moving to the next depth level, typically using a queue. DFS is good for pathfinding, BFS for shortest path on unweighted graphs.
What is the time complexity of sorting an array using QuickSort in the average and worst cases?
Answer:
QuickSort has an average-case time complexity of O(n log n). In the worst-case scenario, typically when the pivot selection consistently leads to highly unbalanced partitions (e.g., already sorted array), its time complexity degrades to O(n^2).
When would you choose a HashSet over an ArrayList for storing a collection of unique elements?
Answer:
Choose a HashSet when you need to store unique elements and require very fast average-case O(1) performance for adding, removing, and checking for element existence. An ArrayList allows duplicates and has O(n) for existence checks and removals, making HashSet superior for uniqueness and lookup speed.