Tag Archives: Data Structure

C Programming, Data Structure and Algorithm, Interview, Programming

Stack Interview Questions

Sudhir Singh 12 Comments

The stack is always a favourite part of the interviewer in any programming interview. Stack has an important place in Linear data structure and used to implement complex solutions. Stack Interview Questions are the best collection of concepts and questions asked in the data structure Interview.

Stacks are important part of data structures and comes under abstract data structures. They allow access to only one data item at a time and that is the last item inserted.


Since internally other data structures are used by stack, they are abstract data type. Stacks use array. Stacks are useful to perform many operations in other data types.
Few examples of Stack implementation:

  • Stack is used by Binary trees in traversing of nodes.
  • Stack is used by Graphs in searching the vertices of the graph.
  • Stacks can be used to process tasks, messages etc.

To crack Stack interview and to give perfect answers to stack interview questions and answers, It is very important to have basic concepts of stack and other data types like array.

Here we have given the basic concept of stack and implementation of stack using C language.

While keeping in mind the practical implementation and complexity we have given plenty of examples of stack implementation and operations using C Programming.

What is a Stack?



A stack is a linear data structure and represented a list of the element in which an element may be inserted or deleted only from one end, called the top of the stack.

Elements in the stack are arranged in a linear fashion. Unlike an array, we can not access an element randomly.

According to the behaviour of Stack, we can have two important operations

  1. PUSH and
  2. POP

Insertion of an element in the stack from the top is called PUSH and removal of an element from the stack is called POP.

We can only access the last element inserted in a Stack. Hence We can say an Item can either Inserted or Deleted At only one end of the stack and that end is the TOP. This is why We called it a LIFO – Last In First Out.

Main Features of Stack


  1. The stack is a Linear type data structure
  2. Allow only the last element to access
  3. Random access of element is not allowed
  4. The stack is an ordered list of similar data type
  5. When a stack is completely full it is called Overflow Stack and If completely empty it is called Underflow Stack.
  6. A stack is a recursive data structure. Here is a structural definition of a Stack:
    1. a stack is either empty or
    2. it consisted of a top and the rest which is a stack;

Application of Stack

  • We can use stack reverse a string. You push a given string to stack – character by character – and then POP character from the stack.
  • Undo Operations in the text editor is an application of stack PUSH and POP.

Basic Operations on Stack

Stack allowed the following operation with data stored it with:

  1. Push operation
  2. Pop operation
  3. Peek operation
  4. isFull
  5. isEmpty

Algorithm for PUSH Operation in Stack

Consider MAX represents the last position of the element to be inserted and TOP is the current position. TOP initially points to 0.


Algorithm POP Operation in Stack

The function will return the popped value from the stack

Implementation of Stack



The stack can be implemented as

  1. Using Array
  2. Using a Linked list

Array and linked list both are used to implement a stack. Both have some advantages and disadvantages associated with them. Here are some relative comparisons between these two.

  • The array is a collection of similar data types elements while the linked list is a collection of elements of the same type connected to each other by pointers.
  • Array consumes memory in a contiguous manner. Also, the size of array is decided at compile time. This kind of memory allocation is called Static memory allocation. But in case of linked list memory allocated at runtime. The size of the list can be increased or decreased at runtime. This kind of memory allocation is called dynamic memory allocation.
  • The size of the array is fixed. Memory allocated as soon as the array is declared. In the case of a linked list, size can grow or shrink. 
  • In array, due to memory allocation in contiguous in manner, insertion and deletion take more time in comparison to linked list.
  • Accessing an element in an array is faster. Also, any element of an array can be easily accessed by using indexing. This is not in the case of a linked list. You have to transverse from the starting point to access any element.

 

Implement Stack using an Array



A working Example of Implementation of Stack using Array

Implement Stack using a Linked list



A working Example of Implementation of Stack using Linked List

Spread the love
C Programming, Data Structure and Algorithm, Interview, Programming

Binary Search Tree Data Structure

Dhananjay 3 Comments

A tree is best thought of in this sort of picture. You have a root node at the very top and it has child nodes and each of those child nodes, they have child nodes themselves, and so on.

Very often when we’re talking about trees we talk about binary trees. 

Binary Tree 

A binary tree means that each node has no more than two child nodes. 

That is that each node has a left node and a right node. Of course one or both of those could also be null.      

Binary Search Tree

A binary search tree is a binary tree that fulfills a specific ordering property and a special tree data structure. So on any subtree, the left nodes are less than the root node which is less than all of the right notes. This ordering property makes finding a node very fast because we have a pretty good idea of where it would be. 

How Searching Works Binary Search Tree?

Let’s choose a node, it’s bigger than the root node, so let’s go to the right. Now the next node, if it’s smaller than that node so it must be on the left unless it should be in right. And so very quickly we can start to zoom in on where that node will be because at each operation we’ve chopped off hopefully about half of the nodes and very quickly we find the node we’re looking for. 

Inserting an Element

Inserts work much like finding an element works. We start with some element we want to insert like say, 19, and we say is it bigger or smaller than the route? 

Let say, it’s bigger so let’s go to the right. Now compare it to the next node? If it’s smaller so let’s go to the left. We will do this over and over again until we get to an empty spot or a null node and then we say ok that’s where we should insert our new element. 

Now the one problem here is that if we get elements in a particular order, we could get really imbalanced. Suppose we have a new binary search tree and we just follow the properties of insertion.

So we insert 1 and then 2 to it’s right and then 3 to it’s right and 4 to it’s right, we’re going to get this data structure that looks less like a tree and more like a long list.

 And then inserts and finds will no longer be so fast. There are some algorithms that can ensure that our tree stays balanced, that is roughly the same number of nodes will be on the left side of the subtree and on the right.

These algorithms get pretty complicated so we’re not gonna go into the details here, but it’s worth knowing that they’re built into a lot of programming languages and in a lot of cases and Data Structures Interview Questions you’ll just assume that you have a balanced tree. 

Traversing Through a Tree

The last operation to talk about is traversing or walking through a tree. So there are three common ways we walk through a tree we can do an 

  1. Inorder traversal
  2. Preorder traversal
  3. Postorder traversal. 

A Preorder traversal means that you visit the root first and then you visit it’s left nodes and it’s right nodes. 

In Inorder traversal, you visit the left nodes first then the current node and then you go to the right nodes. 

In a Post Order Traversal, the root node comes up last so you visit the left nodes and then the right nodes, then the current root node. 

Typically in binary search trees, we want to do in order traversals because that actually allows the nodes to be printed in order. 

Implement A Binary Search Tree

Spread the love
Data Structure and Algorithm, Interview, Programming

Tree Data structures Interview Questions for Freshers

Dhananjay 4 Comments

The tree is a nonlinear data structure and a very important part of computer programming. It is a very flexible, versatile and powerful data structure.

The tree can be used to represent data items possessing hierarchical relationships. Items in a tree are arranged as interconnected nodes and edges.

There is a special data item known as root and rest are known as subtrees. This segment is based on the Tree data structure Interview Questions asked in various programming interviews.

The tree data structure is an important part of data structure and played a very vital role in solving complex problems.

This segment is based on concepts and theory of Trees Data structure and very helpful for fresher candidates in an interview.

What are the main applications of Trees?

A tree is a hierarchical representation of data and a non-linear data structure. Hence it has application according to its properties :

  • To Represent hierarchical data
  • To Store data in a sorted fashion
  • To make the searching process easy

What is root?

The first item in the hierarchy is known as the root and it is placed at the top of the tree. A root is known as root is known and it is a terminal node having a degree greater than zero.

What is a node?

Each item in a tree is known as a Node. Nodes are connected to each other and hence they have a degree.

What is the degree of node?

The degree is known as the connectivity of a node. The number of subtrees connected to a node is known as the Degree of Node.

In the Given Tree :

  • Degree of A = 3
  • Degree of B = 0
  • Degree of D = 2
  • Degree of E = 0
  • Degree of F = 0

What is the Degree of Tree?

There are several nodes in a tree data structure.
Each Node has its degree, the number of the connected subtrees.
The degree of the node having the maximum degree is Known as the Degree of Tree.
For Example in the above tree, the Degree of Tree is 3, because the degree of Node A is 3 and It is maximum.

What are siblings?

Nodes having common parents are siblings.
We can say the nodes remain at the same level in a tree are siblings if they are connected to a common node.
The common node is known as Parent.
For Example, D is parent and E and F are siblings.

What is the edge?

The line which is connecting two nodes is known as Edge.

What is the path in a tree?

If we select a node as the source and another as a destination node, then the sequence of the node between these two nodes is known as path.

  • There may be many possible sequences so there may be many paths between two nodes.
  • The path is represented as node pairs. For example, in the given Tree structure the path between A and G is (A, D) (D, E) (E, G).

What is a forest?

The set of Disjointed trees is known as a forest.
When several subtrees are there and they are not joined by a root then this set is known as a forest.

What is a binary tree?

A tree is a special case of a tree when any node can not have more than 2 children.

Each node can have at most two children.

We can structure a binary tree in three parts

  1. Root
  2. Left subtree
  3. Right Subtree

How many types of binary trees are there?

The most popular types of binary trees are as follows :

  • Full Binary Tree
  • Complete Binary Tree
  • Perfect Binary Tree

Full Binary Tree

A Binary Tree will be known as the full binary tree if each node of the tree has either two children or zero children.

The node having zero children is known as a leaf node, so a Full Binary tree is a tree where all nodes have two children except the leaf nodes.

A binary tree having every level is completed except the leaf nodes,

 

Perfect Binary Tree

In a Perfect Binary tree, all the internal nodes have two children and all the leaf nodes are at the same depth.

 

Spread the love
Data Structure and Algorithm, Interview

Data Structure Interview Questions

Dhananjay 14 Comments

Data structure are specialised format for manipulating data like  organising, processing, retrieving and storing data. There are several basic and advanced structure types, any data structures are available to be used by  specific scenario. Each data structure contains information about the data values, relationships between the data and functions that can be applied to the data.

Data structure is backbone of Programming and Implementation. So it plays a very important or we can say a crucial role in any programming interview. Almost the interview for Software Engineer , Software developer, Programmer and  Web Developer  posts are gone through a phase of Data Structure Interview Questions.  And Most of the time your interview performance decided by your data structures concepts.

This is not a complete tutorial of data structures but an overview of what are the topics and basic questions that can be asked in a Data Structure Interview. our purpose is to educate our readers about the importance of data structure in Interviews. Below we have given few questions and answers, hope you will find them useful:

What is Data Structure?

Data Structure is an organisation of data in such a way that manipulation and operations over the data can be done easily. There are many ways to achieve this goal. We have two broad categories as Linear and Non-Linear. The data structure is equally useful in analysing the complexity of heavy applications running over huge traffic and data.

What are the Characteristics of data structures?

Data structures are grouped by their characteristics. The Possible characteristics of data structures are:

1#Linear or non-linear data structures: That means whether the data items are arranged in chronological sequence, or in an unordered sequence. For Example Array is Linear and Graph is non Linear.

2#Homogeneous or non-homogeneous data structures: This describes the types of data in structures. Whether all data in a given structure are of the same type or of various types.

3#Static or dynamic data structures: That is the data structures are compiling style. Static data structures have fixed sizes, structures and memory are allocated at compile time where as Dynamic data structures sizes, structures and memory locations are decided at run time.

What is linear and Non-linear data structures?

Linear Data Structures are the structures where data is arranged in a sequential manner and can be added or delete in a sequence. But not leaner is fashion to arrange data in a non-sequential manner. We can randomly add or delete data from the structure.

What is an Array?

An array is a Linear type Data Structure which is used to collect the similar type of elements and stored in contiguous in memory locations identified by the index. Index of the array starts from zero(0). We can randomly access the element of the array using these indices.

What is a Stack?

The stack is an ordered collection of elements where addition and removal of elements happen at the same end. Such type of arrangement called LIFO, last-in-first-out.A linked list is Suitable for operations such as add, delete, and update.

There are two elementary operations performed on Stacks

  • push: add a new element at the top of the stack
  • pop: remove the top element fro the top of the stack

Click For More stack interview questions

What is a Linked List?

A Data structure where elements are connected via links. Links contains Items and reference to another link. There are three types of Linked lists:

  • Simple Linked List
  • Double Linked List
  • Circular Linked List

What is the Queue?

A Queue is a Data Structure opened at its ends. One end is open to insert new items in the queue and another is open to release existing items for queue. The basic operations of enqueue() and dequeue() work in FIFO- First In First Out Fashion. enqueue() is used to add new items in queue whereas dequeue() is used to remove existing items from queue.

How many types of Linked List are there?

There are three types of Linked lists:

  • Simple Linked List
  • Double Linked List
  • Circular Linked List

What is a Tree?

A tree is a collection of nodes connected to each other and in a hierarchy to maintain parent and child type relationship.

A tree is a nonlinear data structure.

There is a root node and next nodes are connected to root by directed edges and so on. A tree without a node is an empty tree.

Parent->Children.

What is a Heap?

A heap is a Non-Linear Data Structure based on tree and containing properties of Heap.

What is a Graph?

Collection of Nodes arranged as vertices and edges known as Graph. A graph is a Non-Linear type Data Structure. The relationship found between vertices is known as adjacency.

Spread the love