Data Structures

Question 1

What is the height of a node in a tree?

Answer 1

the number of edges on the longest path between that node and a leaf.
any leaf node will have height 0

Question 2

What is a tree?

Answer 2

it is a hierarchical data structure made of nodes and edges that:

1. all nodes are connected
2. there are no cycles
3. each node has only one parent

Question 3

What are the 3 ways if traversing a binary tree by depth?

Answer 3

PreOrder: evaluate the node once your reach it
InOrder: evaluate the node once you evaluated all left subtree
PostOrder: evaluate the node once you evaluated all right subtree

Question 4

What is the average and worst time complexity of insert, search, delete on a binary search tree?

Answer 4

Average: O(h) where h is the tree height
Worst : O(n)

For all operations

O(h) is also O(logN)

Question 5

What is a Full binary tree?

Answer 5

is a binary tree in which all nodes except leaves have two children

Question 6

What is a Complete binary tree?

Answer 6

Binary Tree is complete if all levels are completely filled except possibly the last level and the last level has all keys as left as possible

Question 7

What is a Perfect binary tree?

Answer 7

It is a binary tree in which all internal nodes have 2 children and every leaf node is on the same level.

Question 8

What is the depth of a node in a tree?

Answer 8

is the number of edges from the node to the tree’s root node.
A root node will have a depth of 0.

Question 9

What is a BST?

Answer 9

Binary Search Tree

1. The left subtree of a node contains only nodes with keys less than the node’s key.
2. The right subtree of a node contains only nodes with keys greater than the node’s key.
3. Both the left and right subtrees must also be binary search trees.

Question 10

What are the three abstract data types explained by Skiena? What are their difference?

Answer 10

Containers, dictionary and priority queue

Containers allow storage and retrieval of elements independent of the content (lists, arrays, trees)

Dictionaries stores and retrieves based on a key.

Question 11

What is the advantage of priority queue over a normal sorted list?

Answer 11

Priority queue is more efficient for inserting items after everything is sorted.
It can be done in O(logn) time.

Question 12

What are the two most common ways of collision resolution in a hash map? Explain.

Answer 12

Chaining: where we keep an array of linked lists. Waste memory with pointers on the linked list

Open memory: we keep an array of elements. When there is a collision we search for the next free spot. Deletion can be tricky.

Question 13

What is the degree of a vertex/node in a graph?

Answer 13

It is the number of incident edges on a node, with loops counted twice.

Question 14

What are the 3 main ways of representing graphs in programming? Explain each.

Answer 14

• Adjacency List: Vertices are stored as objects, and every vertex stores a list of adjacent vertices. Allows the storage of additional data on the vertices because it is an object. Additional data can be stored if edges are also stored as objects, in which case each vertex stores its incident edges and each edge stores its incident vertices.
• Adjacency Matrix: A two-dimensional matrix, in which the rows represent source vertices and columns represent destination vertices. Data on edges and vertices must be stored externally. Only the cost for one edge can be stored between each pair of vertices.
• Incidence Matrix: A two-dimensional Boolean matrix, in which the rows represent the vertices and columns represent the edges. The entries indicate whether the vertex at a row is incident to the edge at a column.

Question 15

Which structure is better for representing sparse graphs? Why?

Answer 15

Adjacency List, because it uses space more effectively than the Adjacency Matrix, since the latter will have many empty spots in the matrix.

Question 16

What is a heap?

Answer 16

A heap is a tree-based data structure that satisfies the heap property: if P is a parent node of C, then the value/key of P is greater than or equal the value of C (is the case of a max-heap), or is less than or equal the value o C (in the case of a min-heap).

Question 17

What data structure is important to implement the Dijkstra algorithm in a time-efficient way? Why?

Answer 17

The Min-Heap (min priority queue).

That is because at each iteration of the algorithm, we have to choose the vertex/node with the minimal path so far.

Question 18

Usually an adjacency matrix is implemented as a VxV array. How can I optimize the space used by the adjacency matrix?

Answer 18

By implementing the adjacency matrix using a hashmap keyed by the pair of vertices.

Question 19

What is the main advantage of using an adjacency matrix over an adjacency list?

Answer 19

It provides O(1) time for verifying if two vertices are connected.

Question 20

In which sort of situations a heap is indicated?

Answer 20

In algorithms in which, in each iteration, we find ourselves looking for a minimum of maximum. (e.g. merge k-sorted lists, Djikstra’s Shortest Path)

Question 21

How can we find the shortest path between two nodes in an undirected, unweighted graph?

Answer 21

Just run BFS until we find the destination node. That path will be the shortest path in that condition.

Question 22

How can we find a cycle in a graph?

Answer 22

Run BFS and keep track of visited nodes. If we visit a note twice, there is a cycle.

Question 23

What is graph coloring? And what is a legal coloring?

Answer 23

Coloring is assigning each node a color. Legal coloring is a coloring strategy in which adjacent nodes does not have the same color.

Question 24

What is the maximum degree of a graph?

Answer 24

Is the highest degree of all nodes.

Question 25

What is the chromatic number of a graph?

Answer 25

It is the lowest number of colors we can use to legally color a graph