Interview Questions
Data Structures in Java · Study material
Data Structures in Java – Interview Questions
1. What is a data structure?
A way of organising data in memory so that the required operations – access, search, insert, delete – are efficient.
2. Linear vs non-linear data structures?
Linear structures (array, linked list, stack, queue) arrange elements in a sequence; non-linear ones (trees, graphs) allow one element to connect to many.
3. Array vs linked list?
Arrays give O(1) index access and good cache locality but O(n) middle insertion; linked lists give O(1) insertion at a known node but O(n) access.
4. How does ArrayList grow?
When full it allocates a new array about 1.5 times larger and copies the elements, so add is amortized O(1).
5. How do you reverse a linked list?
Walk the list with prev, cur and next pointers, turning each node's next back to prev; O(n) time, O(1) space.
6. How do you detect a cycle in a linked list?
Floyd's algorithm: a slow pointer moves one step and a fast pointer two; they meet only if there is a cycle.
7. Stack vs queue?
A stack removes the most recently added element (LIFO); a queue removes the oldest (FIFO).
8. Why prefer ArrayDeque over Stack?
Stack is synchronized and inherits Vector's index methods; ArrayDeque is faster and offers a clean stack and queue API.
9. How do you implement a queue with two stacks?
Push into an "in" stack; when the "out" stack is empty, move everything across, then pop from "out". Each element moves once, so operations are amortized O(1).
10. What is a circular queue?
An array-based queue whose head and tail indexes wrap with % capacity, so freed slots at the front are reused.
11. What is a binary heap?
A complete binary tree stored in an array where every parent is ≤ (min-heap) or ≥ (max-heap) its children.
12. How do you make a max-heap with PriorityQueue?
Pass Comparator.reverseOrder() (or a reversed comparator) to the constructor.
13. How do you find the k largest elements efficiently?
Keep a min-heap of size k and drop its minimum whenever it grows past k: O(n log k).
14. What is a binary search tree?
A binary tree where left-subtree keys are smaller and right-subtree keys are larger than the node's key.
15. What are the tree traversals?
Inorder (left, node, right), preorder (node, left, right), postorder (left, right, node) and level-order (breadth-first, with a queue).
16. Why balance a BST?
Operations cost O(height); balancing (AVL, red-black) keeps the height O(log n) instead of O(n).
17. Adjacency list vs adjacency matrix?
A list uses O(V + E) space and suits sparse graphs; a matrix uses O(V²) but answers "is there an edge?" in O(1).
18. BFS vs DFS?
BFS explores level by level with a queue and finds shortest paths in unweighted graphs; DFS goes deep with a stack or recursion and suits cycle detection and topological sorting.
19. What is a trie used for?
Prefix queries such as autocomplete and spell checking, in O(length of the word).
20. How do hash tables handle collisions?
Separate chaining (a list or tree per bucket, as in HashMap) or open addressing (probing for the next free slot).