Data structure interview questions

1. What is Data Structure?

- Data structure is a group of data elements grouped together under one name.
- These data elements are called members. They can have different types and different lengths.
- Some of them store the data of same type while others store different types of data.

2. Which data structure is used to perform recursion?

- The data structure used for recursion is Stack.
- Its LIFO property helps it remembers its 'caller'. This helps it know the data which is to be returned when the function has to return.
- System stack is used for storing the return addresses of the function calls.

3. Does the Minimal Spanning tree of a graph give the shortest distance between any 2 specified nodes?

- No, it doesn’t.
- It assures that the total weight of the tree is kept to minimum.
- It doesn't imply that the distance between any two nodes involved in the minimum-spanning tree is minimum.

4. If you are using C language to implement the heterogeneous linked list, what pointer type will you use?

- A heterogeneous linked list contains different data types in its nodes. We can not use ordinary pointer to connect them.
- The pointer that we use in such a case is void pointer as it is a generic pointer type and capable of storing pointer to any type.

5. Differentiate between PUSH and POP?

- Pushing and popping refers to the way data is stored into and retrieved from a stack.
- PUSH – Data being pushed/ added to the stack.
- POP - Data being retrieved from the stack, particularly the topmost data.

6. When is a binary search algorithm best applied?

- It is best applied to search a list when the elements are already in order or sorted.
- The list here is searched starting in the middle. If that middle value is not the correct one, the lower or the upper half is searched in the similar way.

7. How do you reference all the elements in a one-dimension array?

- This is done using an indexed loop.
- The counter runs from 0 to the array size minus one.
- Using the loop counter as the array subscript helps in referencing all the elements in one-dimensional array.

8. What is Huffman’s algorithm?

- It is used in creating extended binary trees that have minimum weighted path lengths from the given weights.
- It makes use of a table that contains frequency of occurrence for each data element.

9. What is Fibonacci search?

- It is a search algorithm that applies to a sorted array.
- It uses divide-and-conquer approach that reduces the time needed to reach the target element.

10. Which data structure is applied when dealing with a recursive function?

- A recursive function is a function that calls itself based on a terminating condition.
- It uses stack.
- Using LIFO, a call to a recursive function saves the return address. This tells the return address to the calling function after the call terminates.

11. How does dynamic memory allocation help in managing data?

- Dynamic memory allocation helps to store simple structured data types.
- It can combine separately allocated structured blocks to form composite structures that expand and contract as required.

12. What is a bubble sort and how do you perform it?

- Bubble sort is a sorting technique which can be applied to data structures like arrays.
- Here, the adjacent values are compared and their positions are exchanged if they are out of order.
- The smaller value bubbles up to the top of the list, while the larger value sinks to the bottom.

13. How does variable declaration affect memory allocation?

- The amount of memory to be allocated depends on the data type of the variable.
- An integer type variable is needs 32 bits of memory storage to be reserved.

14. You want to insert a new item in a binary search tree. How would you do it?

- Let us assume that the you want to insert is unique.
- First of all, check if the tree is empty.
- If it is empty, you can insert the new item in the root node.
- If it is not empty, refer to the new item’s key.
- If the data to be entered is smaller than the root’s key, insert it into the root’s left subtree.
- Otherwise, insert it into the root’s right subtree.

15. Why is the isEmpty() member method called?

- The isEmpty() member method is called during the dequeue process. It helps in ascertaining if there exists any item in the queue which needs to be removed.
- This method is called by the dequeue() method before returning the front element.

16. What is a queue ?

- A Queue refers to a sequential organization of data.
- It is a FIFO type data structure in which an element is always inserted at the last position and any element is always removed from the first position.

17. What is adequeue?

- A dequeue is a double-ended queue.
- The elements here can be inserted or removed from either end.

18. What is a postfix expression?

- It is an expression in which each operator follows its operands.
- Here, there is no need to group sub-expressions in parentheses or to consider operator precedence..