Java Lists, stacks and queues
Simple structures whose questions are really about choosing the right one and knowing the cost of each operation.
3 concepts · 9 interview questions
What this topic covers
Every concept in lists, stacks and queues, and the questions each one gets asked as. Where a question links, it has a full write-up.
Array lists and linked lists
Contiguous storage gives random access and cache locality; linked nodes give cheap splicing if you already hold the node.
- ArrayList or LinkedList, and why is the textbook answer usually wrong?
- Reverse a linked list, iteratively and recursively.
- Merge two sorted lists.
Stacks, queues and deques
Last-in-first-out and first-in-first-out access. A surprising number of parsing and ordering problems are a stack in disguise.
- Validate balanced brackets in an expression.
- Implement a queue using two stacks.
- What should you use instead of java.util.Stack, and why?
Heaps and priority queues
A partially ordered tree giving the smallest or largest element in constant time, with logarithmic insertion and removal.
- Find the k largest elements in a stream.
- Merge k sorted lists.
- How does PriorityQueue order its iteration?