Data structures Interview Questions

Practice Problems

1. What is a data structure?

The data structure is the way data is organized (stored) and manipulated for retrieval and access. It also defines the way different sets of data relate to one another, establishing relationships and forming algorithms.

2. What is a linear data structure? Name a few examples.

A data structure is linear if all its elements or data items are arranged in a sequence or a linear order. The elements are stored in a non-hierarchical way so that each item has successors and predecessors except the first and last element in the list.

Examples of linear data structures are Arrays, Stack, Strings, Queue, and Linked List.

3. What are some applications of data structures? 

Numerical analysis, operating system, AI, compiler design, database management, graphics, statistical analysis, and simulation.

4. What is the difference between file structure and storage structure?

The difference lies in the memory area accessed. Storage structure refers to the data structure in the memory of the computer system, whereas file structure represents the storage structure in the auxiliary memory.

5. What is a linked list data structure?

It’s a linear data structure or a sequence of data objects where elements are not stored in adjacent memory locations. The elements are linked using pointers to form a chain. Each element is a separate object, called a node.  Each node has two items: a data field and a reference to the next node. The entry point in a linked list is called the head. Where the list is empty, the head is a null reference and the last node has a reference to null.

A linked list is a dynamic data structure, where the number of nodes is not fixed, and the list has the ability to grow and shrink on demand.

It is applied in cases where:

• We deal with an unknown number of objects or don’t know how many items are in the list
• We need constant-time insertions/deletions from the list, as in real-time computing where time predictability is critical
• Random access to any elements is not needed
• The algorithm requires a data structure where objects need to be stored irrespective of their physical address in memory
• We need to insert items in the middle of the list as in a priority queue

Some implementations are stacks and queues, graphs, directory of names, dynamic memory allocation, and performing arithmetic operations on long integers.

6. Are linked lists considered linear or non-linear data structures?

Linked lists are considered both linear and non-linear data structures depending upon the application they are used for. When used for access strategies, it is considered as a linear data-structure. When used for data storage, it is considered a non-linear data structure.

7. What are the advantages of a linked list over an array? In which scenarios do we use Linked List and when Array?

Advantages of a linked list over an array are:

1. Insertion and Deletion

Insertion and deletion of nodes is an easier process, as we only update the address present in the next pointer of a node. It’s expensive to do the same in an array as the room has to be created for the new elements and existing elements must be shifted.

2. Dynamic Data Structure

As a linked list is a dynamic data structure, there is no need to give an initial size as it can grow and shrink at runtime by allocating and deallocating memory. However, the size is limited in an array as the number of elements is statically stored in the main memory.

3. No wastage of memory

As the size of a linked list can increase or decrease depending on the demands of the program, and memory is allocated only when required, there is no memory wasted. In the case of an array, there is memory wastage. For instance, if we declare an array of size 10 and store only five elements in it, then the space for five elements is wasted.

4. Implementation

Data structures like stack and queues are more easily implemented using a linked list than an array.

Some scenarios where we use linked list over array are:

• When we know the upper limit on the number of elements in advance
• When there are a large number of add or remove operations
• When there are no large number of random access to elements
• When we want to insert items in the middle of the list, such as when implementing a priority queue

Some scenarios in which we use array over the linked list are:

• When we need to index or randomly access elements
• When we know the number of elements in the array beforehand, so we can allocate the correct amount of memory
• When we need speed when iterating through all the elements in the sequence
• When memory is a concern; filled arrays use less memory than linked lists, as each element in the array is the data but each linked list node requires the data as well as one or more pointers to the other elements in the linked list

In summary, we consider the requirements of space, time, and ease of implementation to decide whether to use a linked list or array.

8. What is a doubly-linked list? Give some examples.

It is a complex type (double-ended LL) of a linked list in which a node has two links, one that connects to the next node in the sequence and another that connects to the previous node. This allows traversal across the data elements in both directions. 

Examples include: 

• A music playlist with next and previous navigation buttons
• The browser cache with BACK-FORWARD visited pages
• The undo and redo functionality on a browser, where you can reverse the node to get to the previous page

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

All of the elements in a one-dimension array can be referenced using an indexed loop as the array subscript so that the counter runs from 0 to the array size minus one. 

10. What are dynamic data structures? Name a few.

They are collections of data in memory that expand and contract to grow or shrink in size as a program runs. This enables the programmer to control exactly how much memory is to be utilized.

Examples are the dynamic array, linked list, stack, queue, and heap.

An algorithm is a step by step method of solving a problem or manipulating data. It defines a set of instructions to be executed in a certain order to get the desired output. 

12. Why do we need to do an algorithm analysis?

A problem can be solved in more than one way using several solution algorithms. Algorithm analysis provides an estimation of the required resources of an algorithm to solve a specific computational problem. The amount of time and space resources required to execute is also determined.

The time complexity of an algorithm quantifies the amount of time taken for an algorithm to run as a function of the length of the input. The space complexity quantifies the amount of space or memory taken by an algorithm, to run as a function of the length of the input.

13. What is a stack?

A stack is an abstract data type that specifies a linear data structure, as in a real physical stack or piles where you can only take the top item off the stack in order to remove things. Thus, insertion (push) and deletion (pop) of items take place only at one end called top of the stack, with a particular order: LIFO (Last In First Out) or FILO (First In Last Out).

14. Where are stacks used?

• Expression, evaluation, or conversion of evaluating prefix, postfix, and infix expressions
• Syntax parsing
• String reversal
• Parenthesis checking
• Backtracking

15. What is a queue data structure? 

A queue is an abstract data type that specifies a linear data structure or an ordered list,  using the First In First Out (FIFO) operation to access elements. Insert operations can be performed only at one end called REAR and delete operations can be performed only at the other end called FRONT. 

16. List some applications of queue data structure.

To prioritize jobs as in the following scenarios:

• As waiting lists for a single shared resource in a printer, CPU, call center systems, or image uploads; where the first one entered is the first to be processed
• In the asynchronous transfer of data; or example pipes, file IO, and sockets
• As buffers in applications like MP3 media players and CD players
• To maintain the playlist in media players (to add or remove the songs)

17. What is a Dequeue?

It is a double-ended queue, or a data structure, where the elements can be inserted or deleted at both ends (FRONT and REAR).

18. What operations can be performed on queues?

• enqueue() adds an element to the end of the queue
• dequeue() removes an element from the front of the queue
• init() is used for initializing the queue
• isEmpty tests for whether or not the queue is empty
• The front is used to get the value of the first data item but does not remove it
• The rear is used to get the last item from a queue

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

Generally, both heap and stack are part of memory and used in Java for different needs: 

• Heap is more flexible than the stack because memory space can be dynamically allocated and de-allocated as needed 
• Heap memory is used to store objects in Java, whereas stack memory is used to store local variables and function call 
• Objects created in the heap are visible to all threads, whereas variables stored in stacks are only visible to the owner as private memory
• When using recursion, the size of heap memory is more whereas it quickly fill-ups stack memory 

20. Where can stack data structure be used?

• Expression evaluation
• Backtracking
• Memory management
• Function calling and return

<script data-ad-client="ca-pub-5946381419757134" async src="https://pagead2.googlesyndication.com/pagead/js/adsbygoogle.js"></script>