Stacks/queues
What's the difference between a stack and a queue?
Queue: FILO
Stack: FIFO
Maximum height of a AVL tree given n nodes?
floor(1.5logn)
Are these lines of code valid?
const int three = 3;
const int* pointer = (int*)three;
What is the rule of 3?
If you declare any of the 3, you must declare them all (can use = delete):
1. Destructor
2. Copy constructor
3. Copy assignment operator
What's the benefit of having a heap as an array?
No holes, indexing of parent and child easy, no pointers!
What helper function do you need to make a function recursive?
One with the node, one without.
What data type should you use to represent an adjacency matrix?
bool
What are the four flags you should check when getting input with cin? And when are they activate?
1. Bad - type (nonrecoverable) error
2. Fail - logical error or type error
3. EOF - if eof is reached after extraction
4. Good - no errors, value of the stream itself
How do you declare a queue as templated?
template<typename T>
queue {
public:
T* array;
const &T peek() const {};
LIGHTNING ROUND:
What are the rules for a red-black tree?
Root must be a black node
There must be the same # of black nodes in each path (from root to leaf)
No two nodes in a row can be red.
(red nodes do not count towards the path #)
LIGHTNING ROUND:
All member functions of a linked list and their runtime?
Insert (end) O(1)
Search O(n)
Delete(end) O(1) (any) O(n)
How do you use delete?
delete after you use new, and if you've allocated an array of pointers use delete[].
What variables do you need to implement a queue (circular or not)?
front,
size,
maxSize
What does the linux pw manager store???????
What is the run-time of a function that decreases the size of the problem by a factor of 4 each time it runs?
O(logn)
(not O(log4n))
How would you write a function header that passes in a vector and a string (what question should you be asking) and returns a size?
Do we modify the variables?
int size([const] vector<int> &usedVector, [const] string &usedString);
Why is resize O(1)? What would the run time be if we resized every time we input a node?
On average the run-time is O(1) because after n inserts the cost is n, so O(n)/n = 1.
O(n), since there is no more amortized cost.
What is the weird case when inserting into an AVL Tree and when does it happen?
What's the run-time of QuickSort?
O(nlogn)
If not specified, go with the typical case
Secret graph question:
What is the run-time of Dijkstra's? Why?
O(n2). Check every edge for every node, n * n