Programming Interviews

Front 1

What is a preorder tree traversal?

Back 1

First traverse the root, then the left, then the right.

Front 2

How do you implement an Least Recently Used algorithm using a circular linked list?

Back 2

Assumption: data of each node contains a structure that contains a flag indicating whether the data has been used.

For each node in the list, if the data indicates that it has been used, set the flag to false and proceed to the next node. The first node that is reached that has data that indicates it hasn't been used is the LRU; if all data in the list has been used, eventually the iteration will come full circle and the first node in the list will be designated the LRU

Front 3

How do you implement a queue with a linked list?

Back 3

enqueue inserts a node after the tail

dequeue removes the head

Front 4

How do you implement a stack with a linked list

Back 4

push estabilishes a new node as the head

pop removes the current head

Front 5

First traverse the root, then the left, then the right.

Back 5

What is a preorder tree traversal?

Front 6

What is an inorder tree traversal

Back 6

First traverse the left, then the root, then the right.

Front 7

First traverse the left, then the root, then the right.

Back 7

What is an inorder tree traversal

Front 8

What is a postorder tree traversal

Back 8

First traverse the left, then the right, then the root.

Front 9

First traverse the left, then the right, then the root.

Back 9

What is a postorder tree traversal

Front 10

What is a level-order tree traversal

Back 10

Traverse the root, and then visit nodes at each level from left to right (breadth-first exploration)

Front 11

Traverse the root, and then visit nodes at each level from left to right (breadth-first exploration)

Back 11

What is a level-order tree traversal

Front 12

What's the definition of a balanced tree?

Back 12

If all leaf nodes are at the same level, or if all leaf notes are in the last two levels and the second-to-last level is full

Front 13

If all leaf nodes are at the same level, or if all leaf notes are in the last two levels and the second-to-last level is full

Back 13

What's the definition of a balanced tree?

Front 14

How do you flatten a tree into a linked list (breadth traversal)?

Back 14

Pseudo code:

Node* current = root;
while(current)
{
list.add(current->data);
if(current->left) queue.enqueue(current-left);
if(current-right) queue.enqueue(current-right);
current = queue.dequeue();
}