## Algorithms FAQs Part 2.

**What is linear search?**

**Answer: **Linear search is the simplest form of search. It searches for the element sequentially starting from the first element. This search has a disadvantage if the element is located at the end. Advantage lies in the simplicity of the search. Also it is most useful when the elements are arranged in a random order.

**What is binary search? **

**Answer: **Binary search is most useful when the list is sorted. In binary search, element present in the middle of the list is determined. If the key (number to search) is smaller than the middle element, the binary search is done on the first half. If the key (number to search) is greater than the middle element, the binary search is done on the second half (right). The first and the last half are again divided into two by determining the middle element.

**Explain the bubble sort algorithm.**

**Answer: **Bubble sort algorithm is used for sorting a list. It makes use of a temporary variable for swapping. It compares two numbers at a time and swaps them if they are in wrong order. This process is repeated until no swapping is needed. The algorithm is very inefficient if the list is long.

E.g. List: – 7 4 5 3

1. 7 and 4 are compared

2. Since 4 < 7, 4 is stored in a temporary variable.

3. the content of 7 is now stored in the variable which was holding 4

4. Now, the content of temporary variable and the variable previously holding 7 are swapped.

**What is quick sort? **

**Answer: **Quick sort is one the fastest sorting algorithm used for sorting a list. A pivot point is chosen. Remaining elements are portioned or divided such that elements less than the pivot point are in left and those greater than the pivot are on the right. Now, the elements on the left and right can be recursively sorted by repeating the algorithm.

**Describe Trees using C++ with an example.**

Tree is a structure that is similar to linked list. A tree will have two nodes that point to the left part of the tree and the right part of the tree. These two nodes must be of the similar type.

The following code snippet describes the declaration of trees. The advantage of trees is that the data is placed in nodes in sorted order.

struct TreeNode

{

int item; // The data in this node.

TreeNode *left; // Pointer to the left subtree.

TreeNode *right; // Pointer to the right subtree.

}

The following code snippet illustrates the display of tree data.

void showTree( TreeNode *root )

{

if ( root != NULL ) { // (Otherwise, there’s nothing to print.)

showTree(root->left); // Print items in left sub tree.

cout << root->item << ” “; // Print the root item.

showTree(root->right ); // Print items in right sub tree.

}

} // end inorderPrint()

*Data Structure trees – posted on August 03, 2008 at 22:30 PM by Amit Satpute*

**Question – What is a B tree?**

**Answer: **A B-tree of order m (the maximum number of children for each node) is a tree which satisfies the following properties :

1. Every node has <= m children.

2. Every node (except root and leaves) has >= m/2 children.

3. The root has at least 2 children.

4. All leaves appear in the same level, and carry no information.

5. A non-leaf node with k children contains k – 1 keys

**Question – What are splay trees?**

**Answer: **A splay tree is a self-balancing binary search tree. In this, recently accessed elements are quick to access again

It is useful for implementing caches and garbage collection algorithms.

When we move left going down this path, its called a zig and when we move right, its a zag.

Following are the splaying steps. There are six different splaying steps.

1. Zig Rotation (Right Rotation)

2. Zag Rotation (Left Rotation)

3. Zig-Zag (Zig followed by Zag)

4. Zag-Zig (Zag followed by Zig)

5. Zig-Zig

6. Zag-Zag

**Question – What are red-black trees?**

**Answer :**A red-black tree is a type of self-balancing binary search tree.

In red-black trees, the leaf nodes are not relevant and do not contain data.

Red-black trees, like all binary search trees, allow efficient in-order traversal of elements.

Each node has a color attribute, the value of which is either red or black.

Characteristics:

The root and leaves are black

Both children of every red node are black.

Every simple path from a node to a descendant leaf contains the same number of black nodes, either counting or not counting the null black nodes

**Question – What are threaded binary trees?**

**Answer: **In a threaded binary tree, if a node ‘A’ has a right child ‘B’ then B’s left pointer must be either a child, or a thread back to A.

In the case of a left child, that left child must also have a left child or a thread back to A, and so we can follow B’s left children until we find a thread, pointing back to A.

This data structure is useful when stack memory is less and using this tree the treversal around the tree becomes faster.

**Question – What is a B+ tree?**

**Answer: **It is a dynamic, multilevel index, with maximum and minimum bounds on the number of keys in each index segment. all records are stored at the lowest level of the tree; only keys are stored in interior blocks.

**Describe Tree database. Explain its common uses.**

A tree is a data structure which resembles a hierarchical tree structure. Every element in the structure is a node. Every node is linked with the next node, either to its left or to its right. Each node has zero or more child nodes. The length of the longest downward path to a leaf from that node is known as the height of the node and the length of the path to its root is known as the depth of a node.

Common Uses:

– To manipulate hierarchical data

– Makes the information search, called tree traversal, easier.

– To manipulate data that is in the form of sorted list.

**What is binary tree? Explain its uses.**

A binary tree is a tree structure, in which each node has only two child nodes. The first node is known as root node. The parent has two nodes namely left child and right child.

Uses of binary tree:

– To create sorting routine.

– Persisting data items for the purpose of fast lookup later.

– For inserting a new item faster

**How do you find the depth of a binary tree?**

The depth of a binary tree is found using the following process:

1. Send the root node of a binary tree to a function

2. If the tree node is null, then return false value.

3. Calculate the depth of the left tree; call it ‘d1’ by traversing every node. Increment the counter by 1, as the traversing progresses until it reaches the leaf node. These operations are done recursively.

4. Repeat the 3rd step for the left node. Name the counter variable ‘d2’.

5. Find the maximum value between d1 and d2. Add 1 to the max value. Let us call it ‘depth’.

6. The variable ‘depth’ is the depth of the binary tree.

**Explain pre-order and in-order tree traversal.**

A non-empty binary tree is traversed in 3 types, namely pre-order, in-order and post-order in a recursive fashion.

**Pre-order:
**Pre-order process is as follows:

– Visit the root node

– Traverse the left sub tree

– Traverse the right sub tree

**In-Order:
**In order process is as follows:

– Traverse the left sub tree

– Visit the root node

– Traverse the right sub tree

**What is a B+ tree? Explain its uses.**

B+ tree represents the way of insertion, retrieval and removal of the nodes in a sorted fashion. Every operation is identified by a ‘key’. B+ tree has maximum and minimum bounds on the number of keys in each index segment, dynamically. All the records in a B+ tree are persisted at the last level, i.e., leaf level in the order of keys.

B+ tree is used to visit the nodes starting from the root to the left or / and right sub tree. Or starting from the first node of the leaf level. A bi directional tree traversal is possible in the B+ tree.

**Define threaded binary tree. Explain its common uses**

A threaded binary tree is structured in an order that, all right child pointers would normally be null and points to the ‘in-order successor’ of the node. Similarly, all the left child pointers would normally be null and points to the ‘in-order predecessor’ of the node.

Uses of Threaded binary tree:

– Traversal is faster than unthreaded binary trees

– More subtle, by enabling the determination of predecessor and successor nodes that starts from any node, in an efficient manner.

– No stack overload can be carried out with the threads.

– Accessibility of any node from any other node

– It is easy to implement to insertion and deletion from a threaded tree.

**Explain implementation of traversal of a binary tree.**

Binary tree traversal is a process of visiting each and every node of the tree. The two fundamental binary tree traversals are ‘depth-first’ and ‘breadth-first’.

The depth-first traversal are classified into 3 types, namely, pre-order, in-order and post-order.

**Pre-order:** Pre-order traversal involves visiting the root node first, then traversing the left sub tree and finally the right sub tree.

**In-order:** In-order traversal involves visiting the left sub tree first, then visiting the root node and finally the right sub tree.

**Post-order:** Post-order traversal involves visiting the left sub tree first, then visiting the right sub tree and finally visiting the root node.

The breadth-first traversal is the ‘level-order traversal’. The level-order traversal does not follow the branches of the tree. The first-in first-out queue is needed to traversal in level-order traversal.

**Explain implementation of deletion from a binary tree.**

To implement the deletion from a binary tree, there is a need to consider the possibilities of deleting the nodes. They are:

– Node is a terminal node: In case the node is the left child node of its parent, then the left pointer of its parent is set to NULL. In all other cases, if the node is right child node of its parent, then the right pointer of its parent is set to NULL.

– Node has only one child: In this scenario, the appropriate pointer of its parent is set to child node.

– Node has two children: The predecessor is replaced by the node value, and then the predecessor of the node is deleted.

**Describe stack operation. **

Stack is a data structure that follows Last in First out strategy.

Stack Operations:-

� Push – Pushes (inserts) the element in the stack. The location is specified by the pointer.

� Pop – Pulls (removes) the element out of the stack. The location is specified by the pointer

� Swap: – the two top most elements of the stack can be swapped

� Peek: – Returns the top element on the stack but does not remove it from the stack

� Rotate:- the topmost (n) items can be moved on the stack in a rotating fashion

A stack has a fixed location in the memory. When a data element is pushed in the stack, the pointer points to the current element.

**Describe queue operation.**

Queue is a data structure that follows First in First out strategy.

Queue Operations:

� Enqueue- Inserts the element in the queue at the end.

� Dequeue – removes the element out of the queue from the front

� Size – Returns the size of the queue

� Front – Returns the first element of the queue.

� Empty – to find if the queue is empty.

**Discuss how to implement queue using stack.**

A queue can be implemented by using 2 stacks:-

� 1. An element is inserted in the queue by pushing it into stack 1

� 2. An element is extracted from the queue by popping it from the stack 2

� 3. If the stack 2 is empty then all elements currently in stack 1 are transferred to stack 2 but in the reverse order

� 4. If the stack 2 is not empty just pop the value from stack 2.

**Explain stacks and queues in detail.**

A stack is a data structure based on the principle Last In First Out. Stack is container to hold nodes and has two operations – push and pop. Push operation is to add nodes into the stack and pop operation is to delete nodes from the stack and returns the top most node.

A queue is a data structure based on the principle First in First Out. The nodes are kept in an order. A node is inserted from the rear of the queue and a node is deleted from the front. The first element inserted in the first element first to delete.

**Question – What are priority queues?**

A priority queue is essentially a list of items in which each item is associated with a priority

Items are inserted into a priority queue in any, arbitrary order. However, items are withdrawn from a priority queue in order of their priorities starting with the highest priority item first.

Priority queues are often used in the implementation of algorithms

**Question – What is a circular singly linked list?**

In a circular singly linked list, the last node of the list is made to point to the first node. This eases the traveling through the list..

**Describe the steps to insert data into a singly linked list.**

Steps to insert data into a singly linked list:-

**Insert in middle**

Data: 1, 2, 3, 5

1. Locate the node after which a new node (say 4) needs to be inserted.(say after 3)

2. create the new node i.e. 4

3. Point the new node 4 to 5 (new_node->next = node->next(5))

4. Point the node 3 to node 4 (node->next =newnode)

**Insert in the beginning**

Data: 2, 3, 5

1. Locate the first node in the list (2)

2. Point the new node (say 1) to the first node. (new_node->next=first)

**Insert in the end**

Data: 2, 3, 5

1. Locate the last node in the list (5)

2. Point the last node (5) to the new node (say 6). (node->next=new_node)

**Explain how to reverse singly link list.**

**Answer: **Reverse a singly link list using iteration:-

1. First, set a pointer ( *current) to point to the first node i.e. current=base

2. Move ahead until current!=null (till the end)

3. set another pointer (* next) to point to the next node i.e. next=current->next

4. store reference of *next in a temporary variable ( *result) i.e current->next=result

5. swap the result value with current i.e. result=current

6. and now swap the current value with next. i.e. current=next

7. return result and repeat from step 2

A linked list can also be reversed using recursion which eliminates the use of a temporary variable.

**Define circular linked list.**

**Answer: **In a circular linked list the first and the last node are linked. This means that the last node points to the first node in the list. Circular linked list allow quick access to first and last record using a single pointer.

**Describe linked list using C++ with an example.**

A linked list is a chain of nodes. Each and every node has at least two nodes, one is the data and other is the link to the next node. These linked lists are known as single linked lists as they have only one pointer to point to the next node. If a linked list has two nodes, one is to point to the previous node and the other is to point to the next node, then the linked list is known as doubly linked list.

To use a linked list in C++ the following structure is to be declared:

typedef struct List

{

long Data;

List* Next;

List ()

{

Next=NULL;

Data=0;

}

};

typedef List* ListPtr.

The following code snippet is used to add a node.

void List::AddANode()

{

ListPtr->Next = new List;

ListPtr=ListPtr->Next;

}

The following code snippet is used to traverse the list

void showList(ListPtr listPtr)

{

� while(listPtr!=NULL) {

cout<<listPtr->Data;

}

return temp;

}

/ / LListItr class; maintains “current position”.

*/ I*

/ / CONSTRUCTION: With no parameters. The LList class may

/ / construct a LListItr with a pointer to a LListNode.

/ /

/ / ******************PUBLOIPCE RATIONS*********************

/ / boo1 isValid( j –> True if not NULL

/ / void advance ( j –> Advance (if not already NULL)

/ / Object retrieve( ) –> Return item in current position

/ / ******************ERRORS********************************

/ / Throws BadIterator for illegal retrieve.

** **

template <class Object>

class LListItr

{

public:

LListItr( ) : current( NULL ) { 1

** **

boo1 isValid( j const

{ return current ! = NULL; )

** **

void advance ( j

{ if( isValid( j j current = current->next; 1

** **

const Object & retrieve( ) const

{ if( !isValid( j j throw BadIterator( ) ;

return current->element; }

** **

private:

LListNode<Object> *current; / / Current position

** **

LListItr( LListNode<Object> *theNode )

: current ( theNode ) {

** **

friend class LList<Object>; / / Grant access to constructor

};

**1 **/ / LList class.

**2 **/ /

**3 **/ / CONSTRUCTION: with no initializer.

**4 **/ / Access is via LListItr class.

**5 **/ /

**6 **/ / ******************PUBLIoC~ ERATIoNs******************X**

**7 **/ / boo1 isEmpty( ) –> Return true if empty; else false

**8 **/ / void makeEmpty( ) –> Remove all items

**9 **/ / LListItr zeroth( ) –> Return position to prior to first

**10 **/ / LListItr first( ) –> Return first position

**11 **/ / void insert( x, p ) –> Insert x after position p

**12 **/ / void remove( x ) –> Remove x

**13 **/ / LListItr find( x ) –> Return position that views x

**14 **/ / LListItr findprevious( x )

**15 **/ / –> Return position prior to x

**16 **/ / ******************ERR~R~*****~****************************

**17 **/ / No special errors.

**18**

**19 **template <class Object>

**20 **class LList

**21 **I

**22 **public:

**23 **LList( ) ;

**24 **LList( const LList & rhs ) ;

**25 **-LList( ) ;

**26**

**27 **boo1 isEmpty( const;

**28 **void makeEmpty( ) ;

**29 **LListItr<Object> zeroth( ) const;

**30 **LListItr<Object> first ( ) const;

**31 **void insert( const Object & x, const ~~istItr<Object&> p ) ;

**32 **LListItr<Object> find( const Object & x ) const;

**33 **LListItr<Object> findprevious( const Object & x ) const;

**34 **void remove( const Object & x ) ;

**35**

**36 **const LList & operator=( const LList & rhs ) ;

**37**

**38 **private:

**39 **LListNode<Object> *header;

};

**1 **/ / Construct the list.

**2 **template <class Object>

**3 **LList<Object>: :LList ( )

**4 **{

**5 **header = new LListNode<Object>;

**6 **1

**7**

**8 **/ / Test if the list is logically empty.

**9 **/ / Return true if empty, false, otherwise.

**10 **template <class Object>

**11 **boo1 LList<Object>: :isEmpty( ) const

**12 **{

**13 **return header->next == NULL;

**14 **1

**15**

**16 **/ / Return an iterator representing the header node.

**17 **template <class Object>

**18 **LListItr<Object> LList<Object>::zeroth( ) const

**19 **I

**20 **return LListItr<Object>( header ) ;

**21 **1

**22**

**23 **/ / Return an iterator representing the first node in the list.

24 / / This operation is valid for empty lists.

**25 **template <class Object>

**26 **LListItr<Object> LList<Object>::first( ) const

**27 **{

**28 **return LListItr<Object>( header->next ) ;

**29 **};

**1 **/ / Simple print function.

**2 **template <class Object>

**3 **void printlist( const LList<Object> & theList )

**4 **(

**5 **if( theList.isEmptyi ) )

6 cout << “Empty list” << endl;

**7 **else

8 }

**9 **LListItr<Object> itr = theList.first( ) ;

**10 **for( ; itr.isValid( ) ; itreadvance( ) )

**11 **cout << itr.retrieve( ) << ” “;

**12 **{

**13 **cout << endl;

**14 **}

** **

**1 **/ / Return iterator corresponding to the first node matching x.

**2 **/ / Iterator is not valid if item is not found.

**3 **template <class Object>

**4 **LListItr<Object> LList<Object>::find( const Object & x ) const

**5 **{

6 LListNode<Object> *p = header->next;

**7**

8 while( p ! = NULL && p->element ! = x )

9 p = p->next;

**10**

**11 **return LListItr<Object>( p ) ;

**12 **}

**1 **/ / Remove the first occurrence of an item X .

**2 **template <class Object>

**3 **void LList<Object>::remove( const Object & *x*

**4 **{

**5 **LListNode<Object> *p = findprevious( x ) .current;

**6**

**7 **if( p->next ! = NULL )

8 I

**9 **LListNode<Object> *oldNode = p->next;

**10 **p->next = p->next->next; / / Bypass

**11 **delete oldNode;

**12 **}

**13 **1

**Figure 17.13 **The remove routine for the LList class.

**1 **/ / Return iterator prior to the first node containing item x.

**2 **template <class Object>

**3 **LListItr<Object>

**4 **LList<Object>: : f indprevious ( const Object & x ) const

**5 **{

**6 **LListNode<Object> *p = header;

**7**

8 while( p-znext ! = NULL && p->next->element ! = x )

**9 **p = p->next;

**10**

**11 **return LListItr<Object>( p ) ;

**12 **}

**Figure 17.14 **The f indprevious routine-similar to the find routine-for use

with remove.

**1 **/ / Insert item x after p.

**2 **template <class Object>

**3 **void LList<Object>::

**4 **insert( const Object & x, const LListItr<Object> & p )

**5 **{

**6 **if ( p.current ! = NULL )

**7 **p.current->next = new LListNodecObject>( x,

8 p.current->next ) ;

**9 **}

**Figure 17.15 **The insertion routine for the LList class.

**1 **/ / Make the list logically empty.

**2 **template <class Object>

**3 **void LList<Object>: :makeEmpty( )

**4 **I

**5 **while( !isEmptyi ) )

6 remove ( first ( ) .retrieve ( ) ) ;

**7 **1

**8**

**9 **/ / Destructor.

**10 **template <class Object>

**11 **LList<Object>::-LList( )

**12 **(

**13 **makeErnpty ( ) ;

**14 **delete header;

**15 **1

**Figure 17.16 **The makeEmpty method and the LLis t destructor.

**1 **/ / Copy constructor.

**2 **template <class Object>

**3 **LList<Object>::LList( const LList<Object> & rhs )

**4 **{

**5 **header = new LListNodeiObject>;

**6 ***this = rhs;

**7 **}

**8**

**9 **/ / Deep copy of linked lists.

**10 **template <class Object>

**11 **const LList<Object> &

**12 **LList<Object>::operator=( const ~~ist<Object&> rhs *i*

**13 **{

**14 **if ( this ! = &rhs )

**15 **(

**16 **makeEmpty ( ) ;

**17**

**18 **LListItr<Object> ritr = rhs.first( ) ;

**19 **LListItr<Object> itr = zeroth( ) ;

**20 **for( ; ritr.isValid( ) ; ritr.advance( ) , itr.advance( )

**21 **insert( ritr.retrieve( ) , itr ) ;

**22 **{

**23 **return *this;

**24 **}

**Figure 17.17 **Two LLis **t **copy routines: operator= and copy constructor.

**Q: **Implement a Algorithm to check if the link list is in Ascending order?

**A: **template

bool linklist::isAscending() const{

nodeptr ptr = head;

while(ptr->_next)

{

if(ptr->_data > ptr->_next->_data)

return false;

ptr= ptr->_next;

}

return true;

}

** **

**Q: **Write an algorithm to reverse a link list?

**A: **template

void linklist::reverselist()

{

nodeptr ptr= head;

nodeptr nextptr= ptr->_next;

while(nextptr)

{

nodeptr temp = nextptr->_next;

nextptr->_next = ptr;

ptr = nextptr;

nextptr = temp;

}

head->_next = 0;

head = ptr;

}