FAQs on Non-linear Data Structures
Q: What are non-linear data structures?
A: Non-linear data structures are data structures where the elements are not arranged in a sequential or linear manner. Unlike linear data structures such as arrays, linked lists, stacks, and queues, non-linear data structures organize data in a hierarchical or interconnected manner.
Q: What are some examples of non-linear data structures?
A: Examples of non-linear data structures include trees, graphs, heaps, and hash tables.
Q: What is a tree data structure?
A: A tree is a hierarchical data structure that consists of nodes connected by edges. Each node has a parent node and zero or more child nodes. The topmost node in a tree is called the root node, and nodes with no children are called leaf nodes.
Q: Can you provide an example of a tree data structure and its implementation in code?
A: Here is the code.
class TreeNode:
def __init__(self, data):
self.data = data
self.children = []
class Tree:
def __init__(self):
self.root = None
def add_node(self, data, parent=None):
node = TreeNode(data)
if parent is None:
self.root = node
else:
parent.children.append(node)
return node
# Example usage:
tree = Tree()
root = tree.add_node("A")
b = tree.add_node("B", root)
c = tree.add_node("C", root)
tree.add_node("D", b)
Q: What is a graph data structure?
A: A graph is a collection of nodes (vertices) and edges that connect pairs of nodes. Graphs can be directed (edges have a direction) or undirected (edges have no direction). They are used to model relationships between entities.
Q: Can you provide an example of a graph data structure and its implementation in code?
A: Here is the code.
class Graph:
def __init__(self):
self.graph = {}
def add_edge(self, u, v):
if u not in self.graph:
self.graph[u] = []
if v not in self.graph:
self.graph[v] = []
self.graph[u].append(v)
self.graph[v].append(u) # Uncomment for undirected graph
# Example usage:
g = Graph()
g.add_edge('A', 'B')
g.add_edge('B', 'C')
g.add_edge('C', 'D')
Q: What is a heap data structure?
A: A heap is a specialized tree-based data structure that satisfies the heap property. In a max heap, for any given node C, the value of C is greater than or equal to the values of its children. In a min heap, the value of C is less than or equal to the values of its children.
Q: Can you provide an example of a heap data structure and its implementation in code?
A: Here is the code.
import heapq
# Example of min heap
heap = []
heapq.heappush(heap, 5)
heapq.heappush(heap, 2)
heapq.heappush(heap, 7)
print(heap) # Output: [2, 5, 7]
# Example of max heap (using negative values)
max_heap = []
heapq.heappush(max_heap, -5)
heapq.heappush(max_heap, -2)
heapq.heappush(max_heap, -7)
print([-x for x in max_heap]) # Output: [7, 5, 2]
Q: What is a hash table data structure?
A: A hash table is a data structure that stores key-value pairs. It uses a hash function to compute an index into an array of buckets or slots, from which the desired value can be found.
Q: Can you provide an example of a hash table data structure and its implementation in code?
A: Here is the code.
class HashTable:
def __init__(self):
self.size = 10
self.hash_table = [[] for _ in range(self.size)]
def hash_function(self, key):
return key % self.size
def insert(self, key, value):
hash_key = self.hash_function(key)
self.hash_table[hash_key].append((key, value))
def search(self, key):
hash_key = self.hash_function(key)
for pair in self.hash_table[hash_key]:
if pair[0] == key:
return pair[1]
return None
# Example usage:
ht = HashTable()
ht.insert(10, 'apple')
ht.insert(20, 'banana')
print(ht.search(10)) # Output: 'apple'
print(ht.search(20)) # Output: 'banana'
Important Interview Questions and Answers on Non-linear data structure
Q: What is a non-linear data structure?
A non-linear data structure is a type of data structure where the elements are not organized in a sequential manner. Unlike linear data structures (e.g., arrays, linked lists) where elements are arranged sequentially, non-linear data structures allow elements to be connected in a more complex manner, such as hierarchical or interconnected relationships.
Q: Give examples of non-linear data structures.
Examples of non-linear data structures include:
- Trees (e.g., binary trees, AVL trees, B-trees)
- Graphs (e.g., directed graphs, undirected graphs)
- Heaps (e.g., binary heap, Fibonacci heap)
Q: What is a binary tree? Explain its properties.
A binary tree is a hierarchical data structure composed of nodes, where each node has at most two children, referred to as the left child and the right child. The topmost node in a binary tree is called the root node. The properties of a binary tree include:
- Each node can have at most two children.
- Each child node is either a left child or a right child.
- Binary trees can be either empty (no nodes) or non-empty.
- The depth of a binary tree is the maximum distance from the root node to any leaf node.
- The height of a binary tree is the maximum depth of any node in the tree.
Example code:
class TreeNode:
def __init__(self, value):
self.value = value
self.left = None
self.right = None
# Example binary tree
# 1
# / \
# 2 3
# / \ / \
# 4 5 6 7
root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
root.left.left = TreeNode(4)
root.left.right = TreeNode(5)
root.right.left = TreeNode(6)
root.right.right = TreeNode(7)
Q: Explain Depth First Search (DFS) on a binary tree.
Depth First Search (DFS) is a traversal algorithm that explores as far as possible along each branch before backtracking. In the case of a binary tree, DFS can be implemented using recursion or a stack data structure. There are three variations of DFS:
- Preorder traversal: Process the current node, then recursively visit the left and right subtrees.
- Inorder traversal: Recursively visit the left subtree, process the current node, then recursively visit the right subtree.
- Postorder traversal: Recursively visit the left and right subtrees, then process the current node.
Example code (Preorder traversal):
def preorder_traversal(node):
if node is not None:
print(node.value)
preorder_traversal(node.left)
preorder_traversal(node.right)
# Example usage
preorder_traversal(root)
