Basic Data Structure Interview Questions for Freshers

1. What are Data Structures?

A data structure is a mechanical or logical way that data is organized within a program. The
organization of data is what determines how a program performs. There are many types of
data structures, each with its own uses. When designing code, we need to pay particular
attention to the way data is structured. If data isn't stored efficiently or correctly structured,
then the overall performance of the code will be reduced.

2. Why Create Data Structures?

Data structures serve a number of important functions in a program. They ensure that each
line of code performs its function correctly and efficiently, they help the programmer
identify and fix problems with his/her code, and they help to create a clear and organized
code base.

3. What are some applications of Data structures?

Following are some real-time applications of data structures:

 Decision Making
 Genetics
 Image Processing
 Blockchain
 Numerical and Statistical Analysis
 Compiler Design
 Database Design and many more
4. Explain the process behind storing a variable in memory.

 A variable is stored in memory based on the amount of memory that is needed.

Following are the steps followed to store a variable:
o The required amount of memory is assigned first.
o Then, it is stored based on the data structure being used.
 Using concepts like dynamic allocation ensures high efficiency and that the storage
units can be accessed based on requirements in real-time.

5. Can you explain the difference between file structure and storage structure?

 File Structure: Representation of data into secondary or auxiliary memory say any
device such as a hard disk or pen drives that stores data which remains intact until
manually deleted is known as a file structure representation.
 Storage Structure: In this type, data is stored in the main memory i.e RAM, and is
deleted once the function that uses this data gets completely executed.

The difference is that the storage structure has data stored in the memory of the computer
system, whereas the file structure has the data stored in the auxiliary memory.

6. Describe the types of Data Structures?

 Linear Data Structure: A data structure that includes data elements arranged
sequentially or linearly, where each element is connected to its previous and next
nearest elements, is referred to as a linear data structure. Arrays and linked lists are
two examples of linear data structures.
 Non-Linear Data Structure: Non-linear data structures are data structures in which
data elements are not arranged linearly or sequentially. We cannot walk through all
elements in one pass in a non-linear data structure, as in a linear data structure. Trees
and graphs are two examples of non-linear data structures.

7. What is a stack data structure? What are the applications of stack?

A stack is a data structure that is used to represent the state of an application at a particular
point in time. The stack consists of a series of items that are added to the top of the stack
and then removed from the top. It is a linear data structure that follows a particular order in
which operations are performed. LIFO (Last In First Out) or FILO (First In Last Out) are
two possible orders. A stack consists of a sequence of items. The element that's added last
will come out first, a real-life example might be a stack of clothes on top of each other.
When we remove the cloth that was previously on top, we can say that the cloth that was
added last comes out first.

Following are some applications for stack data structure:

 It acts as temporary storage during recursive operations

 Redo and Undo operations in doc editors
 Reversing a string
 Parenthesis matching
 Postfix to Infix Expressions
 Function calls order

8. What are different operations available in stack data structure?

Some of the main operations provided in the stack data structure are:

 push: This adds an item to the top of the stack. The overflow condition occurs if the
stack is full.
 pop: This removes the top item of the stack. Underflow condition occurs if the stack
is empty.
 top: This returns the top item from the stack.
 isEmpty: This returns true if the stack is empty else false.
 size: This returns the size of the stack.

9. What is a queue data structure? What are the applications of queue?

A queue is a linear data structure that allows users to store items in a list in a systematic
manner. The items are added to the queue at the rear end until they are full, at which point
they are removed from the queue from the front. Queues are commonly used in situations
where the users want to hold items for a long period of time, such as during a checkout
process. A good example of a queue is any queue of customers for a resource where the
first consumer is served first.
Following are some applications of queue data structure:

 Breadth-first search algorithm in graphs

 Operating system: job scheduling operations, Disk scheduling, CPU scheduling etc.
 Call management in call centres

10. What are different operations available in queue data structure?

 enqueue: This adds an element to the rear end of the queue. Overflow conditions
occur if the queue is full.
 dequeue: This removes an element from the front end of the queue. Underflow
conditions occur if the queue is empty.
 isEmpty: This returns true if the queue is empty or else false.
 rear: This returns the rear end element without removing it.
 front: This returns the front-end element without removing it.
 size: This returns the size of the queue.

11. Differentiate between stack and queue data structure.

Stack Queue
Stack is a linear data structure where data Queue is a linear data structure where data is
is added and removed from the top. ended at the rear end and removed from the front.
Stack is based on LIFO(Last In First Out) Queue is based on FIFO(First In First Out)
principle principle
Insertion operation in Stack is known as
Insertion operation in Queue is known as eneque.
push.
Delete operation in Stack is known as
Delete operation in Queue is known as dequeue.
pop.
Only one pointer is available for both Two pointers are available for addition and
addition and deletion: top() deletion: front() and rear()
Used in solving recursion problems Used in solving sequential processing problems

12. How to implement a queue using stack?

A queue can be implemented using two stacks. Let q be the queue andstack1 and stack2 be
the 2 stacks for implementing q. We know that stack supports push, pop, and peek
operations and using these operations, we need to emulate the operations of the queue -
enqueue and dequeue. Hence, queue q can be implemented in two methods (Both the
methods use auxillary space complexity of O(n)):

1. By making enqueue operation costly:

 Here, the oldest element is always at the top of stack1 which ensures dequeue
operation occurs in O(1) time complexity.
 To place the element at top of stack1, stack2 is used.
 Pseudocode:
o Enqueue: Here time complexity will be O(n)

enqueue(q, data):
While stack1 is not empty:
Push everything from stack1 to stack2.
Push data to stack1
Push everything back to stack1.

 Dequeue: Here time complexity will be O(1)

deQueue(q):
If stack1 is empty then error else
Pop an item from stack1 and return it

2. By making the dequeue operation costly:

 Here, for enqueue operation, the new element is pushed at the top of stack1. Here, the
enqueue operation time complexity is O(1).
 In dequeue, if stack2 is empty, all elements from stack1 are moved to stack2 and top
of stack2 is the result. Basically, reversing the list by pushing to a stack and returning
the first enqueued element. This operation of pushing all elements to a new stack
takes O(n) complexity.
  Pseudocode:
o Enqueue: Time complexity: O(1)

enqueue(q, data):
Push data to stack1

 Dequeue: Time complexity: O(n)

dequeue(q):
If both stacks are empty then raise error.
If stack2 is empty:
While stack1 is not empty:
push everything from stack1 to stack2.
Pop the element from stack2 and return it.

13. How do you implement stack using queues?

 A stack can be implemented using two queues. We know that a queue supports
enqueue and dequeue operations. Using these operations, we need to develop push,
pop operations.
 Let stack be ‘s’ and queues used to implement be ‘q1’ and ‘q2’. Then, stack ‘s’ can be
implemented in two ways:

1. By making push operation costly:

 This method ensures that the newly entered element is always at the front of ‘q1’ so
that pop operation just dequeues from ‘q1’.
 ‘q2’ is used as auxillary queue to put every new element in front of ‘q1’ while
ensuring pop happens in O(1) complexity.
 Pseudocode:
o Push element to stack s: Here push takes O(n) time complexity.

push(s, data):
Enqueue data to q2
Dequeue elements one by one from q1 and enqueue to q2.
Swap the names of q1 and q2

 Pop element from stack s: Takes O(1) time complexity.

pop(s):
dequeue from q1 and return it.

2. By making pop operation costly:

 In push operation, the element is enqueued to q1.

 In pop operation, all the elements from q1 except the last remaining element, are
pushed to q2 if it is empty. That last element remaining of q1 is dequeued and
returned.
  Pseudocode:
o Push element to stack s: Here push takes O(1) time complexity.

push(s,data):
Enqueue data to q1

 Pop element from stack s: Takes O(n) time complexity.

pop(s):
Step1: Dequeue every elements except the last element from q1 and enqueue to q2.
Step2: Dequeue the last item of q1, the dequeued item is stored in result variable.
Step3: Swap the names of q1 and q2 (for getting updated data after dequeue)
Step4: Return the result.

14. What is array data structure? What are the applications of arrays?

An array data structure is a data structure that is used to store data in a way that is efficient
and easy to access. It is similar to a list in that it stores data in a sequence. However, an
array data structure differs from a list in that it can hold much more data than a list can. An
array data structure is created by combining several arrays together. Each array is then
given a unique identifier, and each array’s data is stored in the order in which they are
created.

Array data structures are commonly used in databases and other computer systems to store
large amounts of data efficiently. They are also useful for storing information that is
frequently accessed, such as large amounts of text or images.

15. Elaborate on different types of array data structure

There are several different types of arrays:

 One-dimensional array: A one-dimensional array stores its elements in contiguous

memory locations, accessing them using a single index value. It is a linear data
structure holding all the elements in a sequence.
  Two-dimensional array: A two-dimensional array is a tabular array that includes
rows and columns and stores data. An M × N two-dimensional array is created by
grouping M rows and N columns into N columns and rows.

 Three-dimensional array: A three-dimensional array is a grid that has rows,

columns, and depth as a third dimension. It comprises a cube with rows, columns, and
depth as a third dimension. The three-dimensional array has three subscripts for a
position in a particular row, column, and depth. Depth (dimension or layer) is the first
index, row index is the second index, and column index is the third index.

16. What is a linked list data structure? What are the applications for the Linked list?

A linked list can be thought of as a series of linked nodes (or items) that are connected by
links (or paths). Each link represents an entry into the linked list, and each entry points to
the next node in the sequence. The order in which nodes are added to the list is determined
by the order in which they are created.
Following are some applications of linked list data structure:

 Stack, Queue, binary trees, and graphs are implemented using linked lists.
 Dynamic management for Operating System memory.
 Round robin scheduling for operating system tasks.
 Forward and backward operation in the browser.

17. Elaborate on different types of Linked List data structures?

Following are different types of linked lists:

1. Singly Linked List: A singly linked list is a data structure that is used to store multiple
items. The items are linked together using the key. The key is used to identify the item and
is usually a unique identifier. In a singly linked list, each item is stored in a separate node.
The node can be a single object or it can be a collection of objects. When an item is added
to the list, the node is updated and the new item is added to the end of the list. When an
item is removed from the list, the node that contains the removed item is deleted and its
place is taken by another node. The key of a singly linked list can be any type of data
structure that can be used to identify an object. For example, it could be an integer, a string,
or even another singly linked list. Singly-linked lists are useful for storing many different
types of data. For example, they are commonly used to store lists of items such as grocery
lists or patient records. They are also useful for storing data that is time sensitive such as
stock market prices or flight schedules.

2. Doubly Linked List: A doubly linked list is a data structure that allows for two-way
data access such that each node in the list points to the next node in the list and also points
back to its previous node. In a doubly linked list, each node can be accessed by its address,
and the contents of the node can be accessed by its index. It's ideal for applications that
need to access large amounts of data in a fast manner. A disadvantage of a doubly linked
list is that it is more difficult to maintain than a single-linked list. In addition, it is more
difficult to add and remove nodes than in a single-linked list.

3. Circular Linked List: A circular linked list is a unidirectional linked list where each
node points to its next node and the last node points back to the first node, which makes it
circular.

4. Doubly Circular Linked List: A doubly circular linked list is a linked list where each
node points to its next node and its previous node and the last node points back to the first
node and first node’s previous points to the last node.

5. Header List: A list that contains the header node at the beginning of the list, is called the
header-linked list. This is helpful in calculating some repetitive operations like the number
of elements in the list etc.

18. Difference between Array and Linked List.

Arrays Linked Lists
A linked list is a collection of entities known as
An array is a collection of data
nodes. The node is divided into two sections: data and
elements of the same type.
address.
It keeps the data elements in a single It stores elements at random, or anywhere in the
memory. memory.
The memory size of an array is fixed
The memory size of a linked list is allocated during
and cannot be changed during
runtime.
runtime.
An array's elements are not dependent
Linked List elements are dependent on one another.
on one another.
It is easier and faster to access an
In the linked list, it takes time to access an element.
element in an array.
Memory utilization is ineffective in Memory utilization is effective in the case of linked
the case of an array. lists.
Operations like insertion and deletion Operations like insertion and deletion are faster in the
take longer time in an array. linked list.

19. What is an asymptotic analysis of an algorithm?

Asymptotic analysis of an algorithm defines the run-time performance as per its

mathematical boundations. Asymptotic analysis helps us articulate the best case(Omega
Notation, Ω), average case(Theta Notation, θ), and worst case(Big Oh Notation, Ο)
performance of an algorithm.

20. What is hashmap in data structure?

Hashmap is a data structure that uses an implementation of a hash table data structure
which allows access to data in constant time (O(1)) complexity if you have the key.

21. What is the requirement for an object to be used as key or value in HashMap?

 The key or value object that gets used in the hashmap must
implement equals() and hashcode() method.
  The hash code is used when inserting the key object into the map and the equals
method is used when trying to retrieve a value from the map.

22. What is the time complexity of basic operations get() and put() in HashMap class?

The time complexity is O(1) assuming that the hash function used in the hash map
distributes elements uniformly among the buckets.