Home » Top 20 Data Structure Interview Questions for SDET

# Top 20 Data Structure Interview Questions for SDET #### 1. What is the Data Structure?

Data Structure is the method of arranging data in such a way that it can be used to perform common and most frequent operations effectively and efficiently. It represents a logical relationship between data and its function.

Data Structures is about creating data elements in terms of some relationship, for organizing and storing them in a better way.

#### 2. What is Linked List?

A Linked list is a linear data structure, which contains two parts. First is data part, which is used to information of the element in the list. Other one is link, which contains the pointer to next node or previous node or both, that holds the address of the node. Combination of these make a node.

#### 3. What is Singly Linked List?

A singly Linked list is a linear data structure, in which link only store reference to the next node. It can not point to the previous node. The last node always points to null. It’s size can be changed during the run time i.e dynamically. It is also known as one-way list.We cannot traverse in backwards direction.

#### 4. What is Doubly Linked List?

A doubly Linked list is a linear data structure, in which link store reference to the next node as well as to the previous node.

The last node always points to null.We can traverse in both direction. Operations like adding, deleting a node require more changing more links than singly linked list.

#### 5. What is Circular Linked List?

Circular linked list is a linked list, in which all nodes are connected to form a circle i.e last node points to the first node of the list. A circular linked list can be a singly circular linked list or doubly circular linked list.We can traverse the complete linked list by starting from any point in the list.

#### 6. What is Stack?

A stack is a non primitive data type linear data structure ordered list, in which the addition of new data and deletion of data takes place from one end, known as top.

Elements can’t be deleted or inserted from the middle of the stack. Stacks follows Last in first out(LIFO) principle. The size of the stack can be static as well as of dynamic size depending on the need of the user.

#### 7. What is Binary Search?

Binary search is an efficient algorithm for finding an element from a sorted list of array. It works by repeatedly dividing the list in half portion so it that could contain the item or element, until we have narrowed down the possible locations to just one element and at that location we will find our required element in the list.

Binary search is also known as half-interval search, and runs in logarithmic time and in worst case it takes O(log n) comparisons, where n is the number of element.

#### 8. Which sorting algorithm is considered the fastest?

There are so many sorting algorithms such as quick sort, bubble sort, balloon sort, radix sort, merge sort, etc.

But none of them can be considered as the fastest because each algorithm is designed for a particular data structure and data set. It would depend on the data set that you would want to sort.

#### 9. What are dynamic data structures?

Dynamic data structures are those structures that expand and contract as a program runs i.e their size is decided during the run time.

It provides a flexible way of manipulating data because it can adjust according to the size of the data. It enables the programmer to control exactly how much memory is utilized in the heap memory.

#### 10. What Are The Advantages Of Linked List Over Array ?

• Unlike Linked List it is expensive to insert and delete elements in the array.
• One can’t double or triple the size of array as it occupies block of memory space.
• Successive element’s need not occupy adjacent space in memory.
• It doesn’t require reallocation or reorganization of the entire list because the data elements need not be stored contiguously in memory.

#### 11. What Do You Mean By Overflow And Underflow?

When we want to insert the element/ data into the data structure but there is no available space available this situation is called overflow.

When we want to delete element/data from a data structure that is already empty this situation is called underflow.

When overflow or underflow condition happens, either the program will crash or the programming language will have its own way of handing things, i.e. by giving the exception in the program.

#### 12. What Is The Data Structures Used To Perform Recursion?

Stack is used to perform recursion because of its LIFO (Last In First Out) property as it remembers its ‘caller’ so knows whom to return when the function has to return.

Recursion uses system stack for storing the return addresses of every function calls.

Every recursive function can have its equivalent iterative function. Even when such equivalent iterative functions are coded, explicit stack is to be used.

#### 13. Why Do we use a Multidimensional Array?

A multidimensional array is very useful in organizing subgroups of elements within an array. A multidimensional array stores memory addresses of data in a pointer array and an array of pointers.

Multidimensional arrays are used to store element in matrix form.

E.g: a railway timetable, we need to use a 3 dimensional array for storing height, width and length of each room on each floor of a building.

#### 15. Define A Set?

A set is a collection of objects need not to be in any particular order. The cardinality of a set is the number of elements present in set. In set no element can appear more than once. An empty set is a set whose cardinality is zero. A singleton set is a set whose cardinality is one.

There are many different ways to implement sets. The simplest one, but in most cases it is least efficient, is to simply create a linear list containing each of the elements in the set.

#### 16. Define Hashing?

Hashing is the technique of transforming a string of characters into a usually shorter fixed length value or key that represents the original string. The values are stored in a data structure called hash table. Hashing is used to index and retrieve items in a database because it is faster to find the element using the short hashed key than to find it using the original value.

Hashing allows to modify and retrieve any data/element in a constant time O(1).It is mostly used in the encryption and decryption of digital signatures.

#### 17. Define A Binary Search Tree?

A binary search tree is a special kind of binary tree, which is either empty or follows all the given conditions:

• Every node has a different value and no two nodes should have the same value i.e all values are distinct.
• The values in any of the left sub-tree is less than the value of its parent node.
• The values in any of the right sub-tree is greater than the value of its parent node.
• The left and right sub-tree of each node are again binary search tree.

#### 18. How to find middle element of linked list in one pass?

If we need to find the middle element of a linked list in one pass, we need to maintain two reference, one increment at each node at a time while other increments after two nodes at a time.

We need to increment the first reference until the it reaches the end of the linked list, by having this arrangement in the list, when the first pointer reaches the end, the second pointer will point to a middle element of the linked list and we get the required element.

#### 19. What are the advantages of the heap over a stack?

The advantage of heap memory over the stack are as follows:

• In Heap we can allocated and de-allocated memory dynamically according to our need that make it more flexible than stack memory.
• When we use recursion it require lot of memory, as the size of heap memory is more than stack it is preferred more.
• In Heap when we create any object that will be to all threads, whereas variables stored in stack are only visible to the owner as private memory.

#### 20. What are the advantages of binary search over a linear search?

Binary search is more efficient than a linear search because it performs fewer comparisons. In linear search, we can only eliminate one element/data per comparison every time we can’t find the target value,whereas in the binary search, we eliminate half the set with each comparison.

Binary search require O(log n) time compared to linear search’s O(n) time. This means that more of the elements present in the array, the faster is binary search compared to a linear search.