What is the time complexity of accessing an element by index in an array?
O(1) - arrays provide constant-time random access because elements are stored in contiguous memory locations.
What is the time complexity of inserting an element at the beginning of an array?
O(n) - all existing elements must be shifted one position to the right.
What is the time complexity of inserting at the end of a dynamic array (like TypeScript’s array)?
O(1) amortized - occasionally O(n) when the array needs to resize, but averaged over many operations it’s constant.
What is a linked list and when would you use it over an array?
A linked list is a sequence of nodes where each node contains data and a pointer to the next node. Use it when you need frequent insertions/deletions at arbitrary positions and don’t need random access.
What is the time complexity of inserting at the beginning of a singly linked list?
O(1) - just create a new node and point it to the current head.
What is the time complexity of inserting at the end of a singly linked list without a tail pointer?
O(n) - you must traverse the entire list to find the last node.
What is the difference between a singly linked list and a doubly linked list?
A singly linked list has nodes with only a ‘next’ pointer. A doubly linked list has both ‘next’ and ‘prev’ pointers, allowing traversal in both directions and O(1) deletion if you have a reference to the node.
What is a stack and what is its access pattern?
A stack is a LIFO (Last In, First Out) data structure. The last element added is the first one removed. Think of a stack of plates.
What are the time complexities of push, pop, and peek operations on a stack?
All O(1) - these operations only affect the top of the stack.
What is a queue and what is its access pattern?
A queue is a FIFO (First In, First Out) data structure. The first element added is the first one removed. Think of a line at a store.
What are the time complexities of enqueue and dequeue operations on a queue?
O(1) for both when implemented with a linked list or circular array. With a simple array, dequeue can be O(n) due to shifting.
What is a deque (double-ended queue)?
A deque allows insertion and deletion at both ends in O(1) time. It combines the capabilities of both stacks and queues.
What is a hash table/hash map?
A data structure that maps keys to values using a hash function. The hash function converts keys into array indices for fast lookups.
What are the average and worst-case time complexities for hash table operations (insert, delete, lookup)?
Average: O(1) for all operations. Worst case: O(n) when many keys hash to the same index (hash collisions).
What is a hash collision and how is it typically handled?
A collision occurs when two keys hash to the same index. Common solutions: chaining (linked list at each index) or open addressing (probing for next empty slot).
What makes a good hash function?
It should be deterministic, distribute keys uniformly across the array, be fast to compute, and minimize collisions.
What is the load factor in a hash table and why does it matter?
Load factor = number of entries / table size. Higher load factors increase collision probability. Tables typically resize when load factor exceeds 0.7-0.75.
What is a Set and how does it differ from an array?
A Set stores unique values with O(1) average lookup/insert/delete. Arrays allow duplicates and have O(n) lookup unless sorted.
What is a binary tree?
A hierarchical data structure where each node has at most two children, referred to as left and right children.
What is a Binary Search Tree (BST)?
A binary tree where for each node, all values in its left subtree are less than the node’s value, and all values in its right subtree are greater.
What are the time complexities for search, insert, and delete in a BST?
Average: O(log n). Worst case (unbalanced/skewed tree): O(n).
What is a balanced binary tree and why does it matter?
A tree where the height difference between left and right subtrees of any node is at most 1. Balancing ensures O(log n) operations instead of O(n).
Name two types of self-balancing BSTs.
AVL trees (strict balancing, faster lookups) and Red-Black trees (less strict, faster insertions/deletions). TreeMap in Java uses Red-Black.
What is a heap?
A complete binary tree that satisfies the heap property: in a max-heap, each parent is greater than or equal to its children; in a min-heap, each parent is less than or equal to its children.
