Trees
In a Binary Tree, if a node is at Level L (where the root is Level 0), what is the maximum number of nodes that can exist at that specific level?
(WATCHOUT: The question is not asking total nodes from root to L)
2^L
What is the fundamental rule that every standard Queue must follow?
FIFO (First In, First Out)
Graphs can be classified as either Directed or Undirected. in a Directed graph,
1. What is the difference between an In-degree and an Out-degree?
2. What do you call a node where all its outward edges originate (it has no incoming edges)?
1. In-degree is the number of edges coming into a node.
Out-degree is the number of edges going out.
2. A Source. (Bonus: A node with only incoming edges is called a Sink. Don't ask me y, I don't know ;-;)
void printPairs(int n) {
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
printf("%d, %d\n", i, j);
}
}
}
O(n^2)
IF every node in the tree has either 0 or 2 children, which specific type of Binary Tree does this describe? (pretty sure this won't come out but eh)
Full Binary Tree
Complete Binary Tree
Perfect Binary Tree
Full Binary Tree
Ure implementing a queue using an array. After a few push and pop operations, you find that the rear of the queue has reached the end of the array, but the front of the array is empty.
What specific type of queue "wraps around" to fix this without having to shift every element?
Circular Queue
Let's say u have a graph with V nodes and E edges. If you use an Adjacency Matrix (Cost Matrix), how much space does it take in terms of V?
O(V^2)
int fibonacci(int n) {
if (n <= 1) return n;
return fibonacci(n - 1) + fibonacci(n - 2);
}
O(2^n)
Given the following sequence of numbers: [15, 10, 20, 8, 12, 17, 25],
1. Draw the Binary Tree (use paint or canva)
2. List the Pre-order, In-order, and Post-order traversals using []
[15, 10, 8, 12, 20, 17, 25]
[8, 10, 12, 15, 17, 20, 25]
[8, 12, 10, 17, 25, 20, 15]
A Priority Queue is a further development of the Queue concept. But in Priority Queue, its made up of two components, which is?
A key and a value (k, v)
Why is an Adjacency List considered more efficient for a a graph with very few edges (sparse graph)?
In a sparse graph, a matrix is filled mostly with zeros (wasted space). An Adjacency List only stores the actual edges that exist, saving memory (what if u don't wanna save memory? Well go ham with Adjacency Matrix)
void jump(int n) {
for (int i = 1; i * i <= n; i++) {
printf("%d ", i);
}
}
\sqrt(n)
Ure given the Post-order and In-order traversals of a tree.
- Post-order: [D, E, B, F, G, C, A]
- In-order: [D, B, E, A, F, C, G]
Which node is the Root, and which node is the Right Child of the root? (Answer format eg: D, B)
A, C
Ure tasked with designing a task manager for an OS. Compare a normal Queue and a Priority Queue by providing one major advantage (Pro) and one major disadvantage (Con) for each in this specific scenario.
Queue (FIFO):
Pros: Operations are always O(1). Every task is treated equally based on arrival time.
Cons: High-priority system tasks (like a crash alert) has to wait behind low-priority tasks that arrived earlier.
Priority Queue:
Pros: Allows urgent tasks to "jump" to the front of the line. Essential for complex algorithms like Heapsort or Dijkstra's.
Cons: Operations are generally slower like O(log n) for heaps or O(n) for lists. It also risks something called "Starvation" where low-priority tasks never get processed. Crazy term, ik.
Compare the behavior of Depth First Search (DFS) and Breadth First Search (BFS):
1. Which one uses a Stack (or recursion) and which one uses a Queue?
2. If u are looking for the shortest path (minimum number of edges) in an unweighted graph, which algorithm should u use?
1. DFS uses a Stack. BFS uses a Queue.
2. BFS.
If u use DFS, then: Once DFS finds a path, it considers that path "found." It does not check other branches to see if a shorter one exists. It explores based on "completing a path" rather than "measuring a distance." Compare this with BFS.
Because BFS explores every possible path of length k before moving to length k+1, the very first time it encounters the target node, it is mathematically guaranteed to be via the shortest possible path.
#include <stdio.h>
#define MAX_STRENGTH 255
void apply_filter(int n) {
int intensity = 0;
for (int i = n; i > 0; i /= 2) {
for (int k = 0; k < 10; k++) {
intensity = (intensity + k) % MAX_STRENGTH;
}
for (int j = 0; j < i; j++) {
printf("Filtering pixel at %d\n", j);
}
}
}
O(n)
Design the pseudocode for a BST that supports insert, search, and delete using the data [15, 10, 20, 8, 12, 17, 25]. Your delete function has to correctly handle the most difficult scenario: deleting a node with two children :3333
Gl
banana
Write the pseudocode for the entire queue code w/ PUSH(X) and POP(X) (function or in main, whichever) operations in a Queue using an array of size 10 [10, 20, 30, 40, 50, 60, 70, 80, 90, 100].
After writing the code, find the Time Complexity for both operations.
banana
Write only the function pseudocode to perform a BFS on a graph starting from a node V. Ur code should track which nodes have been "visited" to avoid infinite loops.
#include <stdio.h>
void dummy_sort(int n) {
for(int i = 0; i < n; i++) { int x = i; }
}
// hint: use master theorem :3
int search_engine(int n) {
if (n <= 1) return 1;
dummy_sort(n);
int res = search_engine(n / 2) +
search_engine(n / 2) +
search_engine(n / 2) +
search_engine(n / 2);
return res + 67;
}
O(n^2)