Collections
A list collection that supports fast iteration and insertion/removal on both ends
What is a linked list?
A sorting algorithm that splits a list into two using a pivot
What is quicksort?
This keyword is used to ensure that a block of code can only be run once at a time to prevent data loss or corruption.
What is synchronized?
The representation of a graph where each vertex stores a list or set of the other vertices it connects to
What is an adjacency list?
A data structure that keeps its elements sorted where elements can be inserted or removed in O(log n) time
What is a binary search tree?
The two methods that classes must override to work in a hash map/set
What are equals() and hashCode()?
This method is used to make a thread stop executing for the specified amount of time.
What is sleep()?
This algorithm for finding paths in an unweighted graph is implemented using a FIFO queue.
What is BFS (breadth-first search)?
A collection with nondeterministic ordering where items can be inserted in O(1) time (average case)
What is a hashset?
This hash set/map implementation resolves collisions by storing the value in the next unfilled slot
What is linear probing?
Each network connection (TCP or UDP) is uniquely identified by these two things.
What are an IP address and port?
This step in backtracking decreases the number of states you need to check in the future.
What is pruning?
Preorder, inorder, and postorder traversals of the following binary tree:
https://f.trimill.xyz/tree-1.png
What are:
EPQJXMV
QPJEMXV
QJPMVXE
The time complexities of the following algorithms, respectively:
Binary search, merge sort, selection sort, linear search
What are O(log n), O(n log n), O(n^2), and O(n)?
The first provides connection-oriented, reliable communication over a network, while the second is connectionless and makes no reliability guarantees.
What are TCP and UDP?
The order that vertices would be reached by performing recursive DFS on this graph:
https://f.trimill.xyz/graph-4.png
(start at the vertex labeled S, visit neighbors alphabetically)
What is S A C B D F G E?
The min-heap resulting from the following operations:
- Insert 5, 3, 4, 1, 6
- Extract min
- Extract min
- Insert 2, 7
The steps of performing insertion sort on the following list (show the list after each iteration):
9 1 6 4 3
What are:
1 9 6 4 3
1 6 9 4 3
1 4 6 9 3
1 3 4 6 9
?
This syntax can be used in Python to automatically close a file after opening it
what is "with open(...) as ..."
The next step of Dijkstra's algorithm in the following graph:
https://f.trimill.xyz/graph-3.png
(green vertices have been visited, blue ones have not)
What is visiting vertex D?