STACKS, QUEUES, RECURSION
What data structure is typically used to evaluate a postfix expression?
Stack
What is the height of a tree with only one node?
0
What data structure is commonly used in BFS traversal.
Queue
What is the main advantage of using a hash table over an array?
Faster average-case lookup time (O(1))
What is the worst case time complexity of Shell Sort
O(n^2)
What is the time complexity of enqueue and dequeue operations in a circular queue implemented using an array?
O(1)
DAILY DOUBLE!! What traversal order results in a sorted output for a Binary Search Tree?
In-Order Traversal
True or false: All trees are graphs but not all graphs are trees
True
What is a collision in hashing, and name one resolution method.
When two keys hash to the same index; method: chaining or open addressing (linear/Quadratic probing, double hashing)
What is the best-case time complexity of Insertion Sort.
O(n)
Describe what happens if you forget the base case in a recursive function.
No terminating condition: Stack overflow/Infinite Recursion/Application crash.
Write the pre-order traversal of this tree: A -> (B, C), B -> (D, E), C -> (F)
A B D E C F
What is a topological sort and when is it applicable.
An ordering of vertices in a Directed acyclic graph, such that for every direct edge u->v, u comes before v in the ordering.
Define load factor and its importance in hash tables.
Load factor = (# elements) / (table size); affects performance and triggers resizing
Why is quicksort not a stable sort?
Because it may reorder equal elements during partitioning. Elements equal to the pivot can get swapped across.
Implement a recursive function to calculate the sum of all elements in an array.
int sum(int[], int n) {
if (n==0) return 0;
return arr[n-1]+ sum(arr, n-1); }What is the time complexity of searching in a balanced binary search tree?
O(log n)
DAILY DOUBLE!! Give an algorithm that can be used to detect a cycle in a graph
Maintain visited array. Recursively perform DFS at each current vertex. If you arrive at a node that is in the visited array then there is a cycle.
Explain double hashing and how it addresses clustering.
Double hashing uses a second hash function to determine the step size for probing, It reducing primary clustering compared to linear probing.
Explain a sorting algorithm that uses a divide-and Conquer approach and guarantees O(n log n) in all cases)
Mergesort. Recursively divides the array in half until each element is in its own array. Merges divided halves into final sorted array.
A queue is simulated by using two stacks. Briefly explain the logic.
Use one stack for enqueue; for dequeue, pop all elements into the second stack, then pop the top; If the next operation is enqueue, put all elements back and append to queue
Given a binary tree, give an algorithm to determine if it is height-balanced.
At each node, recursively do DFS on each subtree to determine if the height difference is <= 1. If so then it is height-balance.
Given an undirected graph, explain how to find the number of connected components.
Maintain list of unvisited nodes. where the list of unvisited is not emply: Increment counter to 1. Perform DFS or BFS from every unvisited node. If a node is visited remove it from the list. Return counter
Provide the pseudocode algorithm for the insert operation for a hash table using hash function k mod n and linear probing.
Loop from hash(key), check index until empty, insert. Wrap around using mod.
Provide an algorithm for Heapsort.
1.) Build Heap from array. 2.)Repeatedly extract the Minimum element (root of the heap). 3.)Replace with the last element of the heap. 4.) Heapify the root. 5.) Add the extracted element to the next position of the array.