data structure interview questions for freshers
What is LIFO?
LIFO is a short form of Last In First Out. It refers to how data is accessed, stored and retrieved. Using this scheme, data that was stored last should be the one to be extracted first. This also means that in order to gain access to the first data, all the other data that was stored before this first data must first be retrieved and extracted.
How do you reference all the elements in a one-dimension array?
To reference all the elements in a one -dimension array, you need to use an indexed loop, So that, the counter runs from 0 to the array size – 1. In this manner, You can reference all the elements in sequence by using the loop counter as the array subscript.
When is a binary search best applied?
A binary search is an algorithm that is best applied to search a list when the elements are already in order or sorted. The list is searched starting in the middle, such that if that middle value is not the target search key, it will check to see if it will continue the search on the lower half of the list or the higher half. The split and search will then continue in the same manner.
What is selection sort?
Selection sort is in-place sorting technique. It divides the data set into two sub-lists: sorted and unsorted. Then it selects the minimum element from unsorted sub-list and places it into the sorted list. This iterates unless all the elements from unsorted sub-list are consumed into sorted sub-list.
Given a Binary Search Tree and print its values in ascending order
We have to perform Inorder traversal, It is the property of binary search tree and Inorder traversal.
Is it possible to implement a queue using Linked List?
Yes its possbile to implement queue using linked list.
Given a Tree, is it possible to find the greatest and least among leaves in linear time?
Linear solution exist,have two variables min and max. Perform any tree traversal. Assign the first traversed leaf element to min and max for all other leaf elements to check with these variables and update it accordingly. If a current element is < min then update min with that element. If it is > min then check with max.
Is it possible to find find the greatest and least value among the nodes in a given BST without using any extra variables?
Solution exist without any extra variables, As per BST property, the leftmost node should be the least one and the rightmost node should be the greatest. In other words, the first and last node of an Inorder traversal is the least and greatest among the nodes respectively.
Is it possible to implement 2 stacks in an array?
Condition: None of the stacks should indicate an overflow until every slot of an array is used.
2 stacks can be implemented for the given condition, Start 1st stack from left (1st position of an array) and 2nd from right (the last position say n). Move 1st stack towards right( i.e 1,2,3 …n) and 2nd towards left (i.e n,n-1,n-2…1).
fresher data structure interview questions
Given two keys K1 & K2, write an algorithm to print all the elements between them with K1<=K2 in a BST.
The linear solution is possible without using any extra space,perform an inorder traversal. Once you find K1 print it and continue traversal now, print all other traversed elements until you reach K2.Note: If K1 == K2 stop once you find K1.
data structure interview questions with answers
Diffrence between STACK and ARRAY.
Stack follows a LIFO pattern. It means that data access follows a sequence wherein the last data to be stored when the first one to be extracted. Arrays, on the other hand, does not follow a particular order and instead can be accessed by referring to the indexed element within the array.
What is a bubble sort and how to implement?
A bubble sort is one sorting technique that can be applied to data structures such as an array. It works by comparing adjacent elements and exchanges their values if they are out of order. This method lets the smaller values “bubble” to the top of the list, while the larger value sinks to the bottom.
What are the parts of a linked list?
A linked list typically has two parts: the head and the tail. Between the head and tail lie the actual nodes. All these nodes are linked sequentially.
How does selection sort work?
Selection sort works by picking the smallest number from the list and placing it at the front. This process is repeated for the second position towards the end of the list. It is the simplest sort algorithm.
What is a graph?
A graph is one type of data structure that contains a set of ordered pairs. These ordered pairs are also referred to as edges or arcs and are used to connect nodes where data can be stored and retrieved.
Differentiate linear from a nonlinear data structure.
The linear data structure is a structure wherein data elements are adjacent to each other. Examples of linear data structure include arrays, linked lists, stacks, and queues. On the other hand, a non-linear data structure is a structure wherein each data element can connect to more than two adjacent data elements. Examples of nonlinear data structure include trees and graphs.
What are doubly linked lists?
Doubly linked lists are a special type of linked list wherein traversal across the data elements can be done in both directions. This is made possible by having two links in every node, one that links to the next node and another one that connects to the previous node.
Briefly explain the recursive algorithm.
The recursive algorithm targets a problem by dividing it into smaller, manageable sub-problems. The output of one recursion after processing one sub-problem becomes the input to the next recursive process.
How do you search for a target key in a linked list?
To find the target key in a linked list, you have to apply a sequential search. Each node is traversed and compared with the target key, and if it is different, then it follows the link to the next node. This traversal continues until either the target key is found or if the last node is reached.