Time Complexity
What is the Big O time complexity to search for an element in a Linked List?
O(N)
What does LIFO stand for and which data structure does it refer to?
Last in, first out
Stack
What is the purpose of pre order, in order, and post order traversal and is this an example of depth first search of breadth first search?
To visit every node in the tree.
DFS
What is a binary heap and give an example of its use?
A binary heap is a type of binary tree that follows a property where every child is either less than or greater than it's parent depending on its implementation (max or min heap).
You are building a program to add items to a grocery list. You don't know how large this list may get.
Would it make more sense to use an array or an ArrayList? Why?
Argument for ArrayList - Since the size is unknown, it may be helpful to use an ArrayList since it can hold an 'unlimited' amount of items. The resizing of the underlying array is done for us. Otherwise we would need to manually do it ourselves.
Argument for Array - I don't know how to use objects.
Which of the following functions grows the slowest:
2n, n!
2n
Print the queue after the following operations:
2 is the front of the queue.
[2, 5, 8]
remove(), remove(), add(8)
[8, 8]
Explain the difference between a Binary Search Tree and a Binary Tree.
A BST has a property that every right child is greater than itself and every left child is less than (or equal to if applicable) itself.
A binary tree does not have this property.
Explain the process of a remove operation from a min-heap.
1) Swap the root node with the leftmost node on the lowest level
2) Delete that leaf
3) Perform the bubbleDown function on the new root node until the min-heap invariant is no longer violated.
What inferences about the time complexity can you make about the following recurrence relation without using substitution?
T(n) = 2T(n/2) + n2 , n > 0
1 , else
The Big O time complexity will be at least n2.
What is the Big O time complexity to perform the remove() operation on a heap?
log(n)
Print the stack after the following operations:
1 is the bottom of the stack.
[1, 9, 5, 6, 3]
pop(), push(6), pop(), pop(), pop(), push(1)
[1, 9, 5, 1]
Print the pre order traversal of the following binary tree represented by an array: [0]
[0]
What would the following max heap look like after two remove operations?
[8, 3, 6, 1, 2]
[3, 1, 2]
What is the Big O time complexity of inserting elements in a heap?
O(log(n))
A queue can be implemented with an array or a linked list.
What is the Big O time complexity to insert a new element into a queue implemented with an array vs a queue implemented with a linked list? Explain.
Array: O(N)
LinkedList: O(1)
It takes O(N) time in the worst case for an array implementation because once the internal array is full it is destroyed and a new one is created with a larger capacity.
It takes O(1) in the worst case for a linked list implementation because inserting a new node reference to a head or a tail is always a constant operation.
Print the stack after the following operations:
1 is the bottom of the stack.
[1, 2, 3, 4, 5]
pop(), pop(), pop(), push(4), push(1), push(2), pop()
[1, 2, 4, 1]
Print the in order traversal of the following binary tree represented by an array: [5, 1, 4, 3, 8]
3, 1, 8, 5, 4
Give a specific example of when a max heap would be helpful and make sense to use.
One example: Reading in a list of people for university database and you want to keep it sorted as you build it.
Find the time complexity of the following recurrence relation (worked required for points):
(No point penalty, all teams can get points if they can present a working solution on the board)
T(n) = T(n/2) + 12 , n > 0
1 , else
T(n) = T(n/2) + 12
T(n/2) = T(n/22) + 12
T(n/22) = T(n/23) + 12
T(n/2k-1) = T(n/2k) + 12
T(n/2k) = 1 according to base case
1 + summation from i=0 to k of (12)
Since n/2k = 1 -> 2k = n -> log(2k) = log(n)
k = log(n), plug this into summation
1 + summation from i=0 to log(n) of (12)
Pull out the 12
1 + 12(summation from i=0 to log(n))
1+ 12 log(n)
O(log(n))
You want to write a program to find the kth most largest element in an array. The array is not sorted. What kind of algorithm might you use and what is the time complexity of your algorithm?
(No point penalty for this question, best answer gets the points)
Using the quick select algorithm, we can achieve an average case of Theta(N). But it's worst case is O(N2) in the case where we choose a bad pivot, which only happens rarely.
(You will learn quick select in 343. It is "sort of like" a combination of quick sort and binary search to find some sort of kth element of a list.)
Dequeue is short for Double-Ended Queue where elements can be removed or added from either end.
What is the result of the following dequeue after the following operations:
[front,...,last]
[4, 9, 1, 6]
insertFront(7), removeLast(), removeLast(), insertFront(5), insertLast(1), removeFront()
[7, 4, 9, 1]
Given the following tree, what method of traversal would print "S" first?
[A, D, P, E, null, Z, S, C]
Post Order
Create a min-heap after adding the following values:
3, 2, 7, 1, 8
[1, 2, 7, 3, 8]
Find the time complexity of the following recurrence relation (work required for points):
(All teams can get some points if they can present a working solution on the board)
T(n) = 2T(n-1) + n , n > 0
1 , else
T(n) = 2T(n-1) + n
T(n-1) = 2T(n-2) + n-1
T(n-2) = 2T(n-3) + n-2
T(n-k-1) = 2T(n-k) + n-k-1
n-k = 1 according to base case
k = n-1
Substitution
2(2(2(2) + n-2) + n-1) + n
2n-1 + summation from i = 1 to n [2i(n-i)]
2n-1 + summation from i = 1 to n [2i(n-i)]
2n-1 + summation from i = 1 to n [2in-2ii)]
Break it up into 2 summations
...work, work, work
O(2n)