Data Structures

Question 1

Tree: What is a height of a node?

Answer 1

It is the number of edges on the longest path between that node and a leaf node

Question 2

Tree: What is a height of a tree?

Answer 2

It is the number of edges on the longest path between the root and a leaf node

Question 3

Tree: What is a depth of a node?

Answer 3

It is the number of edges on the longest path between that node and the root

Question 4

Tree: What is a node’s level?

Answer 4

It is defined as by 1 + depth of that node

Question 5

Hashtable: What is a hash table?

Answer 5

It is a data structure which holds collection of key-value pairs and which operations of Insertion, Deletion and Lookup takes O(1) time

Question 6

Tree: What number of levels a binary tree should have to hold N elements?

Answer 6

Levels = ceiling(log(N+1))

Question 7

Tree: What is height-balanced binary tree?

Answer 7

A non-empty binary tree T is balanced if:

1. Left subtree of T is balanced
2. Right subtree of T is balanced
3. The difference between heights of left subtree and right subtree is not more than 1.

Note: An empty tree is height-balanced

Question 8

Tree: What is a full binary tree?

Answer 8

It is a tree in which every node other than the leaves has two children.

Question 9

Tree: What is a complete binary tree?

Answer 9

It is a binary tree in which every level, except possibly the last, is completely filled, and all nodes are as far left as possible.

Question 10

Graph: What is a strongly connected component (SCC) of a graph?

Answer 10

SCC is a subgraph in which any two vertices are connected to each other by a paths.

Question 11

Graph: What is a strongly connected graph?

Answer 11

Graph is called strongly connected iff it has only one SCC.

Question 12

Graph: What is a bridge of a graph?

Answer 12

The bridge or cut edge of a graph is any edge in a graph whose removal increases number of connected components.

Question 13

Graph: What is an articulation point of a graph?

Answer 13

The articulation point of a graph is any node in a graph whose removal increases number of connected components.

Question 14

Graph: What is a bipartite graph?

Answer 14

A bipartite graph is one whose vertices can be split into two independent groups U, V such that every edge connects between U and V.

Other definitions:

• The graph is two colorable
• The graph with no odd length cycles

Question 15

Graph: What is a complete graph?

Answer 15

A complete graph is one where there is a unique edge between every pair of nodes.