DATA STRUCTURES (40)

Tuesday, 18 July 2017 03:25

Data Structure Interview Questions | Set 1

Written by

What is a Data Structure?
A data structure is a way of organizing the data so that the data can be used efficiently. Different kinds of data structures are suited to different kinds of applications, and some are highly specialized to specific tasks. For example, B-trees are particularly well-suited for implementation of databases, while compiler implementations usually use hash tables to look up identifiers.

What are linear and non linear data Structures?

• Linear: A data structure is said to be linear if its elements form a sequence or a linear list. Examples: Array. Linked List, Stacks and Queues
• Non-Linear: A data structure is said to be linear if traversal of nodes is nonlinear in nature. Example: Graph and Trees.

What are the various operations that can be performed on different Data Structures?

• Insertion − Add a new data item in the given collection of data items.
• Deletion − Delete an existing data item from the given collection of data items.
• Traversal − Access each data item exactly once so that it can be processed.
• Searching − Find out the location of the data item if it exists in the given collection of data items.
• Sorting − Arranging the data items in some order i.e. in ascending or descending order in case of numerical data and in dictionary order in case of alphanumeric data.

How is an Array different from Linked List?

• The size of the arrays is fixed, Linked Lists are Dynamic in size.
• Inserting and deleting a new element in an array of elements is expensive, Whereas both insertion and deletion can easily be done in Linked Lists.
• Random access is not allowed in Linked Listed.
• Extra memory space for a pointer is required with each element of the Linked list.
• Arrays have better cache locality that can make a pretty big difference in performance.

What is Stack and where it can be used?

Stack is a linear data structure which the order LIFO(Last In First Out) or FILO(First In Last Out) for accessing elements. Basic operations of stack are : Push, Pop , Peek

Applications of Stack:

1. Infix to Postfix Conversion using Stack
2. Evaluation of Postfix Expression
3. Reverse a String using Stack
4. Implement two stacks in an array
5. Check for balanced parentheses in an expression

What is a Queue, how it is different from stack and how is it implemented?

Queue is a linear structure which follows the order is First IFirst Out (FIFO) to access elements. Mainly the following are basic operations on queue: Enqueue, DequeueFront, Rear
The difference between stacks and queues is in removing. In a stack we remove the item the most recently added; in a queue, we remove the item the least recently added. Both Queues and Stacks can be implemented using Arrays and Linked Lists.

What are Infix, prefix, Postfix notations?

• Infix notation: + Y – Operators are written in-between their operands. This is the usual way we write expressions. An expression such as
`   A * ( B + C ) / D`
• Postfix notation (also known as “Reverse Polish notation”): X Y Operators are written after their operands. The infix expression given above is equivalent to
`   A B C + * D/`
• Prefix notation (also known as “Polish notation”): + X Y Operators are written before their operands. The expressions given above are equivalent to
`   / * A + B C D`

What is a Linked List and What are its types?

A linked list is a linear data structure (like arrays) where each element is a separate object. Each element (that is node) of a list is comprising of two items – the data and a reference to the next node.Types of Linked List :

1. Singly Linked List : In this type of linked list, every node stores address or reference of next node in list and the last node has next address or reference as NULL. For example 1->2->3->4->NULL
2. Doubly Linked List : Here, here are two references associated with each node, One of the reference points to the next node and one to the previous node. Eg. NULL<-1<->2<->3->NULL
3. Circular Linked List : Circular linked list is a linked list where all nodes are connected to form a circle. There is no NULL at the end. A circular linked list can be a singly circular linked list or doubly circular linked list. Eg. 1->2->3->1 [The next pointer of last node is pointing to the first]

Which data structures are used for BFS and DFS of a graph?

• Queue is used for BFS
• Stack is used for DFS. DFS can also be implemented using recursion (Note that recursion also uses function call stack).

Can doubly linked be implemented using a single pointer variable in every node?
Doubly linked list can be implemented using a single pointer.

How to implement a stack using queue?

A stack can be implemented using two queues. Let stack to be implemented be ‘s’ and queues used to implement be ‘q1’ and ‘q2’. Stack ‘s’ can be implemented in two ways:

• Method 1 (By making push operation costly)
• Method 2 (By making pop operation costly)

How to implement a queue using stack?

A queue can be implemented using two stacks. Let queue to be implemented be q and stacks used to implement q be stack1 and stack2. q can be implemented in two ways:

• Method 1 (By making enQueue operation costly)
• Method 2 (By making deQueue operation costly)

Which Data Structure Should be used for implementiong LRU cache?

We use two data structures to implement an LRU Cache.

1. Queue which is implemented using a doubly linked list. The maximum size of the queue will be equal to the total number of frames available (cache size).The most recently used pages will be near front end and least recently pages will be near rear end.
2. A Hash with page number as key and address of the corresponding queue node as value. See

How to check if a given Binary Tree is BST or not?
If inorder traversal of a binary tree is sorted, then the binary tree is BST. The idea is to simply do inorder traversal and while traversing keep track of previous key value. If current key value is greater, then continue, else return false.

Monday, 17 July 2017 03:55

Write a program to Delete a Tree.

Written by

To delete a tree we must traverse all the nodes of the tree and delete them one by one. So which traversal we should use – Inorder or Preorder or Postorder. Answer is simple – Postorder, because before deleting the parent node we should delete its children nodes first

We can delete tree with other traversals also with extra space complexity but why should we go for other traversals if we have Postorder available which does the work without storing anything in same time complexity.

For the following tree nodes are deleted in order – 4, 5, 2, 3, 1

`#include<stdio.h>`
`#include<stdlib.h>`

`/* A binary tree node has data, pointer to left child `
`   ``and a pointer to right child */`
`struct` `node `
`{`
`    ``int` `data;`
`    ``struct` `node* left;`
`    ``struct` `node* right;`
`};`

`/* Helper function that allocates a new node with the`
`   ``given data and NULL left and right pointers. */`
`struct` `node* newNode(``int` `data) `
`{`
`    ``struct` `node* node = (``struct` `node*)`
`                           ``malloc``(``sizeof``(``struct` `node));`

`    ``node->data = data;`
`    ``node->left = NULL;`
`    ``node->right = NULL;  `
`    ``return``(node);`
`}`

`/*  This function traverses tree in post order to `
`    ``to delete each and every node of the tree */`
`void` `deleteTree(``struct` `node* node) `
`{`
`    ``if` `(node == NULL) ``return``;`

`    ``/* first delete both subtrees */`
`    ``deleteTree(node->left);`
`    ``deleteTree(node->right);`
`  `
`    ``/* then delete the node */`
`    ``printf``(``"\n Deleting node: %d"``, node->data);`
`    ``free``(node);`
`} `

`/* Driver program to test deleteTree function*/`
`int` `main()`
`{`
`    ``struct` `node *root = newNode(1); `
`    ``root->left            = newNode(2);`
`    ``root->right          = newNode(3);`
`    ``root->left->left     = newNode(4);`
`    ``root->left->right   = newNode(5); `
`  `
`    ``deleteTree(root);  `
`    ``root = NULL;`

`    ``printf``(``"\n Tree deleted "``);`
`  `
`    ``getchar``();`
`    ``return` `0;`
`}`
`Output:`

``` Deleting node: 4
Deleting node: 5
Deleting node: 2
Deleting node: 3
Deleting node: 1
Tree deleted ```

The above deleteTree() function deletes the tree, but doesn’t change root to NULL which may cause problems if the user of deleteTree() doesn’t change root to NULL and tires to access values using root pointer. We can modify the deleteTree() function to take reference to the root node so that this problem doesn’t occur. See the following code.

`#include<stdio.h>`
`#include<stdlib.h>`

`/* A binary tree node has data, pointer to left child`
`   ``and a pointer to right child */`
`struct` `node`
`{`
`    ``int` `data;`
`    ``struct` `node* left;`
`    ``struct` `node* right;`
`};`

`/* Helper function that allocates a new node with the`
`   ``given data and NULL left and right pointers. */`
`struct` `node* newNode(``int` `data)`
`{`
`    ``struct` `node* node = (``struct` `node*)`
`                           ``malloc``(``sizeof``(``struct` `node));`

`    ``node->data = data;`
`    ``node->left = NULL;`
`    ``node->right = NULL;`
`    ``return``(node);`
`}`

`/*  This function is same as deleteTree() in the previous program */`
`void` `_deleteTree(``struct` `node* node)`
`{`
`    ``if` `(node == NULL) ``return``;`

`    ``/* first delete both subtrees */`
`    ``_deleteTree(node->left);`
`    ``_deleteTree(node->right);`

`    ``/* then delete the node */`
`    ``printf``(``"\n Deleting node: %d"``, node->data);`
`    ``free``(node);`
`}`

`/* Deletes a tree and sets the root as NULL */`
`void` `deleteTree(``struct` `node** node_ref)`
`{`
`  ``_deleteTree(*node_ref);`
`  ``*node_ref = NULL;`
`}`

`/* Driver program to test deleteTree function*/`
`int` `main()`
`{`
`    ``struct` `node *root = newNode(1);`
`    ``root->left            = newNode(2);`
`    ``root->right          = newNode(3);`
`    ``root->left->left     = newNode(4);`
`    ``root->left->right   = newNode(5);`

`    ``// Note that we pass the address of root here`
`    ``deleteTree(&root);`
`    ``printf``(``"\n Tree deleted "``);`

`    ``getchar``();`
`    ``return` `0;`
`}`
```Deleting node: 4
Deleting node: 5
Deleting node: 2
Deleting node: 3
Deleting node: 1
Tree deleted ```

Time Complexity: O(n)
Space Complexity: If we don’t consider size of stack for function calls then O(1) otherwise O(n)

Monday, 17 July 2017 03:52

Write a Program to Find the Maximum Depth or Height of a Tree

Written by

Recursively calculate height of left and right subtrees of a node and assign height to the node as max of the heights of two children plus 1. See below pseudo code and program for details.

Algorithm:

``` maxDepth()
1. If tree is empty then return 0
2. Else
(a) Get the max depth of left subtree recursively  i.e.,
call maxDepth( tree->left-subtree)
(a) Get the max depth of right subtree recursively  i.e.,
call maxDepth( tree->right-subtree)
(c) Get the max of max depths of left and right
subtrees and add 1 to it for the current node.
max_depth = max(max dept of left subtree,
max depth of right subtree)
+ 1
(d) Return max_depth
```

See the below diagram for more clarity about execution of the recursive function maxDepth() for above example tree.

```            maxDepth('1') = max(maxDepth('2'), maxDepth('3')) + 1
= 2 + 1
/    \
/         \
/             \
/                 \
/                     \
maxDepth('1')                  maxDepth('3') = 1
= max(maxDepth('4'), maxDepth('5')) + 1
= 1 + 1   = 2
/    \
/        \
/            \
/                \
/                    \
maxDepth('4') = 1     maxDepth('5') = 1```
`#include<stdio.h>`
`#include<stdlib.h>`

`/* A binary tree node has data, pointer to left child `
`   ``and a pointer to right child */`
`struct` `node `
`{`
`    ``int` `data;`
`    ``struct` `node* left;`
`    ``struct` `node* right;`
`};`

`/* Compute the "maxDepth" of a tree -- the number of `
`    ``nodes along the longest path from the root node `
`    ``down to the farthest leaf node.*/`
`int` `maxDepth(``struct` `node* node) `
`{`
`   ``if` `(node==NULL) `
`       ``return` `0;`
`   ``else`
`   ``{`
`       ``/* compute the depth of each subtree */`
`       ``int` `lDepth = maxDepth(node->left);`
`       ``int` `rDepth = maxDepth(node->right);`

`       ``/* use the larger one */`
`       ``if` `(lDepth > rDepth) `
`           ``return``(lDepth+1);`
`       ``else` `return``(rDepth+1);`
`   ``}`
`} `

`/* Helper function that allocates a new node with the`
`   ``given data and NULL left and right pointers. */`
`struct` `node* newNode(``int` `data) `
`{`
`    ``struct` `node* node = (``struct` `node*)`
`                                ``malloc``(``sizeof``(``struct` `node));`
`    ``node->data = data;`
`    ``node->left = NULL;`
`    ``node->right = NULL;`
`  `
`    ``return``(node);`
`}`
`  `
`int` `main()`
`{`
`    ``struct` `node *root = newNode(1);`

`    ``root->left = newNode(2);`
`    ``root->right = newNode(3);`
`    ``root->left->left = newNode(4);`
`    ``root->left->right = newNode(5); `
`  `
`    ``printf``(``"Hight of tree is %d"``, maxDepth(root));`
`  `
`    ``getchar``();`
`    ``return` `0;`
`}`
Monday, 17 July 2017 03:49

Write a program to Calculate Size of a tree

Written by

Size of a tree is the number of elements present in the tree. Size of the below tree is 5.

Example Tree

Size() function recursively calculates the size of a tree. It works as follows:

Size of a tree = Size of left subtree + 1 + Size of right subtree.

Algorithm:

```size(tree)
1. If tree is empty then return 0
2. Else
(a) Get the size of left subtree recursively  i.e., call
size( tree->left-subtree)
(a) Get the size of right subtree recursively  i.e., call
size( tree->right-subtree)
(c) Calculate size of the tree as following:
tree_size  =  size(left-subtree) + size(right-
subtree) + 1
(d) Return tree_size```
`#include <stdio.h>`
`#include <stdlib.h>`

`/* A binary tree node has data, pointer to left child `
`   ``and a pointer to right child */`
`struct` `node `
`{`
`    ``int` `data;`
`    ``struct` `node* left;`
`    ``struct` `node* right;`
`};`

`/* Helper function that allocates a new node with the`
`   ``given data and NULL left and right pointers. */`
`struct` `node* newNode(``int` `data) `
`{`
`  ``struct` `node* node = (``struct` `node*)`
`                       ``malloc``(``sizeof``(``struct` `node));`
`  ``node->data = data;`
`  ``node->left = NULL;`
`  ``node->right = NULL;`
`  `
`  ``return``(node);`
`}`

`/* Computes the number of nodes in a tree. */`
`int` `size(``struct` `node* node) `
`{  `
`  ``if` `(node==NULL) `
`    ``return` `0;`
`  ``else`
`    ``return``(size(node->left) + 1 + size(node->right));  `
`}`

`/* Driver program to test size function*/`
`int` `main()`
`{`
`  ``struct` `node *root = newNode(1);`
`  ``root->left        = newNode(2);`
`  ``root->right       = newNode(3);`
`  ``root->left->left  = newNode(4);`
`  ``root->left->right = newNode(5);   `

`  ``printf``(``"Size of the tree is %d"``, size(root));  `
`  ``getchar``();`
`  ``return` `0;`
`}`

Output:

`Size of the tree is 5`
Friday, 14 July 2017 12:29

Inorder Tree Traversal without Recursion

Written by

Using Stack is the obvious way to traverse tree without recursion. Below is an algorithm for traversing binary tree using stack. See this for step wise step execution of the algorithm.

```1) Create an empty stack S.
2) Initialize current node as root
3) Push the current node to S and set current = current->left until current is NULL
4) If current is NULL and stack is not empty then
a) Pop the top item from stack.
b) Print the popped item, set current = popped_item->right
c) Go to step 3.
5) If current is NULL and stack is empty then we are done.
```

Let us consider the below tree for example

```            1
/   \
2      3
/  \
4     5

Step 1 Creates an empty stack: S = NULL

Step 2 sets current as address of root: current -> 1

Step 3 Pushes the current node and set current = current->left until current is NULL
current -> 1
push 1: Stack S -> 1
current -> 2
push 2: Stack S -> 2, 1
current -> 4
push 4: Stack S -> 4, 2, 1
current = NULL

Step 4 pops from S
a) Pop 4: Stack S -> 2, 1
b) print "4"
c) current = NULL /*right of 4 */ and go to step 3
Since current is NULL step 3 doesn't do anything.

Step 4 pops again.
a) Pop 2: Stack S -> 1
b) print "2"
c) current -> 5/*right of 2 */ and go to step 3

Step 3 pushes 5 to stack and makes current NULL
Stack S -> 5, 1
current = NULL

Step 4 pops from S
a) Pop 5: Stack S -> 1
b) print "5"
c) current = NULL /*right of 5 */ and go to step 3
Since current is NULL step 3 doesn't do anything

Step 4 pops again.
a) Pop 1: Stack S -> NULL
b) print "1"
c) current -> 3 /*right of 5 */

Step 3 pushes 3 to stack and makes current NULL
Stack S -> 3
current = NULL

Step 4 pops from S
a) Pop 3: Stack S -> NULL
b) print "3"
c) current = NULL /*right of 3 */

Traversal is done now as stack S is empty and current is NULL. ```
`#include<stdio.h>`
`#include<stdlib.h>`
`#define bool int`

`/* A binary tree tNode has data, pointer to left child`
`   ``and a pointer to right child */`
`struct` `tNode`
`{`
`   ``int` `data;`
`   ``struct` `tNode* left;`
`   ``struct` `tNode* right;`
`};`

`/* Structure of a stack node. Linked List implementation is used for `
`   ``stack. A stack node contains a pointer to tree node and a pointer to `
`   ``next stack node */`
`struct` `sNode`
`{`
`  ``struct` `tNode *t;`
`  ``struct` `sNode *next;`
`};`

`/* Stack related functions */`
`void` `push(``struct` `sNode** top_ref, ``struct` `tNode *t);`
`struct` `tNode *pop(``struct` `sNode** top_ref);`
`bool` `isEmpty(``struct` `sNode *top);`

`/* Iterative function for inorder tree traversal */`
`void` `inOrder(``struct` `tNode *root)`
`{`
`  ``/* set current to root of binary tree */`
`  ``struct` `tNode *current = root;`
`  ``struct` `sNode *s = NULL;  ``/* Initialize stack s */`
`  ``bool` `done = 0;`

`  ``while` `(!done)`
`  ``{`
`    ``/* Reach the left most tNode of the current tNode */`
`    ``if``(current !=  NULL)`
`    ``{`
`      ``/* place pointer to a tree node on the stack before traversing `
`        ``the node's left subtree */`
`      ``push(&s, current);                                               `
`      ``current = current->left;  `
`    ``}`
`       `
`    ``/* backtrack from the empty subtree and visit the tNode `
`       ``at the top of the stack; however, if the stack is empty,`
`      ``you are done */`
`    ``else`
`    ``{`
`      ``if` `(!isEmpty(s))`
`      ``{`
`        ``current = pop(&s);`
`        ``printf``(``"%d "``, current->data);`

`        ``/* we have visited the node and its left subtree.`
`          ``Now, it's right subtree's turn */`
`        ``current = current->right;`
`      ``}`
`      ``else`
`        ``done = 1; `
`    ``}`
`  ``} ``/* end of while */`
`}     `

`/* UTILITY FUNCTIONS */`
`/* Function to push an item to sNode*/`
`void` `push(``struct` `sNode** top_ref, ``struct` `tNode *t)`
`{`
`  ``/* allocate tNode */`
`  ``struct` `sNode* new_tNode =`
`            ``(``struct` `sNode*) ``malloc``(``sizeof``(``struct` `sNode));`

`  ``if``(new_tNode == NULL)`
`  ``{`
`     ``printf``(``"Stack Overflow \n"``);`
`     ``getchar``();`
`     ``exit``(0);`
`  ``}            `

`  ``/* put in the data  */`
`  ``new_tNode->t  = t;`

`  ``/* link the old list off the new tNode */`
`  ``new_tNode->next = (*top_ref);   `

`  ``/* move the head to point to the new tNode */`
`  ``(*top_ref)    = new_tNode;`
`}`

`/* The function returns true if stack is empty, otherwise false */`
`bool` `isEmpty(``struct` `sNode *top)`
`{`
`   ``return` `(top == NULL)? 1 : 0;`
`}   `

`/* Function to pop an item from stack*/`
`struct` `tNode *pop(``struct` `sNode** top_ref)`
`{`
`  ``struct` `tNode *res;`
`  ``struct` `sNode *top;`

`  ``/*If sNode is empty then error */`
`  ``if``(isEmpty(*top_ref))`
`  ``{`
`     ``printf``(``"Stack Underflow \n"``);`
`     ``getchar``();`
`     ``exit``(0);`
`  ``}`
`  ``else`
`  ``{`
`     ``top = *top_ref;`
`     ``res = top->t;`
`     ``*top_ref = top->next;`
`     ``free``(top);`
`     ``return` `res;`
`  ``}`
`}`

`/* Helper function that allocates a new tNode with the`
`   ``given data and NULL left and right pointers. */`
`struct` `tNode* newtNode(``int` `data)`
`{`
`  ``struct` `tNode* tNode = (``struct` `tNode*)`
`                       ``malloc``(``sizeof``(``struct` `tNode));`
`  ``tNode->data = data;`
`  ``tNode->left = NULL;`
`  ``tNode->right = NULL;`

`  ``return``(tNode);`
`}`

`/* Driver program to test above functions*/`
`int` `main()`
`{`

`  ``/* Constructed binary tree is`
`            ``1`
`          ``/   \`
`        ``2      3`
`      ``/  \`
`    ``4     5`
`  ``*/`
`  ``struct` `tNode *root = newtNode(1);`
`  ``root->left        = newtNode(2);`
`  ``root->right       = newtNode(3);`
`  ``root->left->left  = newtNode(4);`
`  ``root->left->right = newtNode(5); `

`  ``inOrder(root);`

`  ``getchar``();`
`  ``return` `0;`
`}`
`Time Complexity: O(n)`

Output:

` 4 2 5 1 3`
Friday, 14 July 2017 12:27

Print level order traversal line by line | Set 1

Written by

Given a binary tree, print level order traversal in a way that nodes of all levels are printed in separate lines.

For example consider the following tree

```          1
/     \
2       3
/   \       \
4     5       6
/  \     /
7    8   9

Output for above tree should be
1
2 3
4 5 6
7 8 9```
`/* Function to line by line print level order traversal a tree*/`
`void` `printLevelOrder(``struct` `node* root)`
`{`
`    ``int` `h = height(root);`
`    ``int` `i;`
`    ``for` `(i=1; i<=h; i++)`