Data Structures Interview Questions And Answers
Q1. What is the data structure?
Ans: A data structure is the logical or mathematical arrangement of data in memory. It considers not only the physical layout of the data items in the memory but also the relationships between these data items and the operations that can be performed on these items.
Q2. Define a variable ?
Ans: A variable is defined as a meaningful name given to a data storage location in the computer memory. When using a variable, we actually refer to the address of the memory where the data is stored.
Q3. Which Data Structure Should be used for implementing LRU cache?
- The queue 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 the rear end.
- A Hash with page number as key and address of the corresponding queue node as value.
Q4. How to implement a stack using a queue?
Ans: 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)
Q5. 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.
Q6. What are linear and non-linear data structures?
Ans: A linear data structure involves the arrangement of values in a linearly. Some typical examples of a linear data structure are lists, queues, stacks, and arrays.
In a non-linear data structure, the elements are not stored in a sequence. Graphs and tree are some examples of a non-linear data structure.
Q7. What is the difference between a data type and data structure?
Ans: In computing, a data type is a group of data values with characteristics that are already defined. Some data types are floats, characters, integer, and string. These are called primitive data types. A data structure, on the other hand, is a grouping of data for easy organization and accessibility. Tables, Array stacks, structs, queues, classes, files, and lists are some data structure.
Q8. What are data structure operations?
Q9. Can you list out all the operations that can be performed/executed in data structures?
Ans: The following are the operations that can be executed in data structures:
- Insertion: Insertion is a process where a new data element can be added to the data items collection.
- Deletion: Deletion is a process where a data element can be deleted from the data items collection.
- Traversal: Traversal id one of the basic operations within the data structure. Also, in this process, every data element can be accessed.
- Searching: Searching is a process where a data element can be searched within the collection of data elements. The data element should be present in the data collection.
- Sorting: Sorting is a process where the data elements can be arranged in an orderly fashion, i.e. ascending or descending order.
Q10. Explain what is a Stack and it's usage?
Ans: The Stack is nothing but a linear data structure where the data elements can be accessed. They are two ways to access the data elements,
- First in Last out (FILO)
- Last in First out (LIFO)
For Stack, the basic operations are listed below:
Q11. What is a queue and how it is implemented?
Ans: A queue is also a linear form of data structure where all the data elements are available in a systematic format. The data elements are available in First in First out form (FIFO).
The basic operation of the Queue are listed below:
Q12. What is the difference between Queue and Stack?
Ans: Both Queue and Stack are the same and follow a linear data structure model. The main difference between these two is the way a record is deleted/removed.
In a stack, the most recent data element that is added will be removed. Whereas, in Queue, the least recent data element that is added to the list will be deleted.
Queues and Stacks are created with the use of arrays and linked lists.
Q13. List out the different types of Linked lists that are available?
Ans: Below is the different types of Linked lists that are available.
- Singly Linked List
- Doubly Linked list
- Circular Linked list
Q14. Explain the difference between file structure and storage structure?
Ans: The key difference between a storage structure and the file structure is the amount of memory that has been acquired.
The data structure that is stored in the main memory of the computer system is classified as a storage structure. This is an inbuilt storage system where the data is available.
On the other hand, if the data is residing on an extra/backup storage then it is classified as a File structure.
Q15. Explain what is a stack?
Ans: A Stack can be classified as an ordered list where all the operations like insertions/ deletions can be executed only from one end. The mentioned stack is nothing but a pure list of execution tasks, the order follows LIFO structure, i.e. Last-In-First-Out. So according to the LIFO structure, the line item that is entered into the stack will be executed at the end (concerning the priority).
Q16. Can you list out the operations that can be performed on Stack?
Ans: The following are the list of operations that can be performed on Stack.
- Push operation:
- Peek operation
- Pop operation
Q17. Do you know the syntax of stack overflow condition?
Ans: The syntax of stack overflow condition is :
Q18. Explain the difference between push and pop operations?
Ans: With the help of push and pop operations, the data can be effectively handled/managed within a stack. The main difference between push and pop operations is listed below:
Push operation is used when inserting the data into the Stack.
Pop operation is used when deleting the data from the Stack.
Q19. Describe what is an array?
Ans: An array is nothing but a collection of data elements that are stored together in a memory location. Also, accessing the data elements within an array is very simple and every data element will have their index number. Using the index number the data element can be easily accessed.
Q20. Explain what do you mean by a multi-dimensional array?
Ans: A multi-dimensional array is nothing but an array of arrays. The data is stored or piled in the form of the tabular structure where it has rows and columns. The use of multi-dimensional arrays will help to store more amount of data in chunks.
Q21. A node contains two fields, can you tell me what are they?
Ans: A node contains two fields, they are :
- Data field
- Link field
Q22. Explain what do you mean by the queue data structure?
Ans: A queue data structure is nothing but an ordered list that is piled up in the form of a stack. They are two ends to the queues where the operations can be taken into consideration:
Rear: All the data insertions are performed in Rear.
Front: All the data deletions are performed in Front.
Q23. Can you list out some practical examples of the queue data structure?
Ans: Below is the few practical examples of data structure:
The daily usage of printers. All the print jobs at the printer follow a queue data structure. The same with all of your computing requests, CPU handles it well by a queuing mechanism
Data transfer activities via, sockets, pipes follow a queue data structure.
All the media songs that are piled up one after the other, i.e. playlists.
Q24. What is a dequeue?
Ans: Dequeue is also known as a double-ended queue. It is exactly the opposite of a queue mechanism. In dequeue structure, all the data insertions and data deletion activities can be executed from both the sides, i.e. Front & Rear.
Q25. Can you let me know the minimum number of queues that are needed to implement a priority queue?
Ans: In general, to implement the priority queue, we need a bare minimum of at least two queues. One queue is essential to store all of the data elements together and another queue is needed to store the priority-based information.
Q26. Do you know how many types of trees are available? List them out?
Ans: They are 6 types of tree that are available. Below is the list:
- Binary search tree
- General tree
- Tournament tree
- Binary tree
- Expression tree
Q27. Explain what is Binary tree?
Ans: A binary tree is a type of tree structure where each node has two children, i.e left child, and right child. Using this the tree structure can be progressed.
Q28. Can you please let me know which data structure is best for tree construction?
Ans: A queue data structure is the best data structure fit for tree construction.
Q29. Explain what is a Path?
Ans: A path is an orderly sequence of a continuous flow of vertices which are connected via their edges. Usually in this type of sequence, there are no restrictions observed.
Q30. Explain what is the cycle?
Ans: A cycle is nothing but a closed path where the first vertice is the same as to that of the last/end vertex. Also, we get to see one condition here, the same vertex should not be passed twice.
Q31. Explain what is a circuit?
Ans: A circuit is very similar to that of a cycle but the only difference is that the vertex can be passed n number of times and don't have any restrictions. Within the circuit, the first vertex is the same as that of the last vertex.
Q32. For the BFS algorithm which data structure is useful?
Ans: For the BFS algorithm, the queue data structure is useful.
Q33. For the DFS algorithm, which data structure is useful?
Ans: For the DFS algorithm, the stack data structure is useful.
Q34. What is a linear search?
Ans: Linear search is also known as a sequential search. With this linear search approach, the search element is compared to every element in the list sequentially until a potential match is found.
Q35. What is a binary search?
Ans: A binary search is also called a half interval search or a binary chop. Within this search algorithm, the target value will be identified by comparing it to the array.
Q36. Can you list out the advantages of selection sort?
Ans: The advantages of selection sort are given below:
- It is easy to use
- Implementation wise it doesn't take much time
- Selection sort can be applied for smaller data sets
- it is efficient when compared to bubble sort
Q37. Explain what is NULL?
Ans: A NULL is a value that can be assigned to a data element. It represents that there is no data available for that particular data element.
Q38. Explain what is VOID?
Ans: VOID is a data type identifier.
It is used to identify pointers that don't have a size associated.
Q39. Explain the main difference between a binary search and linear search?
Ans: The main difference between a binary search and the linear search is the number of comparisons it does to the target value. In most of the cases, binary search is quick compared to the linear search.
Q40. For sequential representation, which data structure is used?
Ans: An adjacency matrix is a data structure that is used for sequential representation.
Q41. For linked representation, which data structure is used?
Ans: An adjacency list is used for linked representation.
Q42. Can you let me know where the tree data structure is applied?
Ans: The tree data structure is applied in the following area:
- To understand the hierarchal data model
- Analysis of the syntax
- Symbol table construction process
- Arithmetic expressions and its manipulation.
Q43. Can you increase the size of a linked list?
Ans: Yes, the size of a linked list can be increased. The size is increased at the runtime.
Q44. Can you increase the size of an array?
Ans: No, the size of an array cannot be increased.
Q45. Is linked list a linear data structure or a non-linear data structure?
Ans: A linked list is considered as a linear data structure and a non-linear data structure. Based on the usage and the situation, the linked list can be aligned.
Based on data storage criteria, a linked list is considered as a non-linear data structure.
Based on the access strategy, a linked list is considered as a linear data structure.
Q46. Give examples of Multi-linked structures?
Ans: The following are examples of multi-linked structures
- Generating index
- Sparse matrix