Arrays
What is the time complexity of accessing an element in an array by index?
O(1) or constant time
What are the two main types of linked lists?
Singly linked lists and doubly linked lists
What principle does a stack follow?
LIFO (Last In, First Out)
In a binary tree, what is the maximum number of children each node can have?
2
What is the average-case time complexity for insertion and lookup in a hash table?
O(1)
In a zero-indexed array of size 10, what is the valid range of indices?
0 to 9
What advantage does a linked list have over an array for insertions at the beginning?
O(1) insertion time at the head versus O(n) for arrays
Name a real-world application where stacks are essential.
Function call stack, browser back button, undo operations, expression evaluation, or DFS
What property must a Binary Search Tree (BST) satisfy?
Left subtree values < node value < right subtree values
What are the two main collision resolution techniques?
Chaining (linked lists) and open addressing (linear probing, quadratic probing, double hashing)
What is the main disadvantage of arrays compared to linked lists when inserting elements in the middle?
Arrays require shifting all subsequent elements, making insertion O(n)
How do you detect a cycle in a linked list efficiently?
Floyd's cycle detection (tortoise and hare) using two pointers at different speeds
How can you implement a queue using two stacks?
Use one stack for enqueue, pop all to second stack for dequeue, achieving amortized O(1)
What is the worst-case time complexity for search in an unbalanced BST?
O(n) when the tree degenerates into a linked list
What is the load factor of a hash table?
The ratio of number of elements to table size (n/m)
Given an unsorted array, what is the most efficient time complexity to find the kth largest element?
O(n) using quickselect or heap-based selection
What is the time complexity of reversing a singly linked list in place?
O(n) time with O(1) space
What data structure would you use to implement a browser's forward and back buttons?
Two stacks (one for back history, one for forward history)
How does an AVL tree maintain balance?
Ensures height difference between left and right subtrees is at most 1, performing rotations when needed
Why is it important for a hash function to distribute keys uniformly?
To minimize collisions and maintain O(1) average performance; clustering causes degradation to O(n)
Describe how a dynamic array (like ArrayList in Java) achieves amortized O(1) insertion time.
It doubles its capacity when full, so while occasional resizing is O(n), the amortized cost over many insertions is O(1)
Explain why finding the middle element of a singly linked list requires O(n) time even though array access is O(1).
Linked lists don't support random access; you must traverse from the head, visiting each node sequentially
Design a min-stack that supports push, pop, and getMin operations all in O(1) time.
Use two stacks: one for values, one tracking minimum at each level
Compare the rebalancing frequency of AVL trees versus Red-Black trees and explain the trade-off.
AVL trees rebalance more frequently (stricter balance) giving faster lookups O(log n), while Red-Black trees rebalance less (looser balance) giving faster insertions/deletions
Explain how Python's dictionary handles hash collisions and when it resizes.
Uses open addressing with random probing; resizes when load factor exceeds 2/3, creating a new table approximately double the size