Data Structures and Algorithms Interview Questions And Answers in Java for experienced professionals from Codingcompiler. These Data Structures and Algorithms Interview Questions were asked in various interviews conducted by top multinational companies across the globe. We hope that these interview questions on Data Structures and Algorithms will help you in cracking your job interview. All the best and happy learning.
In this blog, you are going to learn
- Data Structures and Algorithms Interview Questions in Java
- Data Structures and Algorithms Interview Questions and Answers in Java
- The Best Data Structures and Algorithms Interview Questions and Answers in Java
- Frequently Data Structures and Algorithms Interview Questions and Answers in Java
Data Structures and Algorithms Interview Questions in Java
- What is a Data Structure?
- How to find middle element of linked list in one pass?
- How to find if a linked list has a loop?
- In an integer array, there is 1 to 100 number, out of one is duplicate, how to find?
- What is Circular Queue? Why should we use it?
- What is the difference between the Singly Linked List and Doubly Linked List data structure?
- How to identify the third element from the end in a linked list in one pass?
- Describe some of the operations that are performed on different Data Structures?
- What do you understand by Data Structure?
- What are linear and non-linear types of data Structures? Also, How is an Array different from Linked List?
Data Structures and Algorithms Interview Questions and Answers in Java
Q. What is a Data Structure?
Answer: A data structure is a way of organizing the data so that the data can be used efficiently. Different kinds of data structures are suited to different kinds of applications, and some are highly specialized to specific tasks. For example, B-trees are particularly well-suited for implementation of databases, while compiler implementations usually use hash tables to look up identifiers.
Q. How to find middle element of linked list in one pass?
Answer::
One of the most popular question from data structures and algorithm mostly asked on a telephonic interview. Since many programmers know that, in order to find the length of a linked list we need to first traverse through the linked list till we find the last node, which is pointing to null, and then in second pass we can find a middle element by traversing only half of length.
They get confused when the interviewer asks him to do the same job in one pass i.e. without traversing the linked list again.
In order to find middle element of linked list in one pass, you need to maintain two-pointer, one increment at each node while other increments after two nodes at a time, by having this arrangement, when the first pointer reaches the end, the second pointer will point to a middle element of the linked list. See this trick to find middle element of linked list in a single pass for more details.
Q. How to find if a linked list has a loop?
Answer:
This question has a bit of similarity with the earlier algorithm and data structure interview question. I mean we can use two pointer approach to solve this problem.
If we maintain two pointers, and we increment one pointer after processing two nodes and other after processing every node, we are likely to find a situation where both the pointers will be pointing to the same node.
Q. In an integer array, there is 1 to 100 number, out of one is duplicate, how to find?
Answer: simply add all numbers stored in an array, and the total sum should be equal to n(n+1)/2. Now just subtract actual sum to expected sum, and that is your duplicate number.
Of course, there is a brute force way of checking each number against all other numbers, but that will result in the performance of O(n^2) which is not good.
By the way, this trick will not work if an array has multiple duplicates or its not numbers forming an arithmetic progression. Here is an example of one way to find the duplicate number in the array.
Q. What is Circular Queue? Why should we use it?
A: Circular Queue is a linear data structure in which the operations are performed based on FIFO (First In First Out) principle and the last position is connected back to the first position to make a circle.
In a normal Queue Data Structure, we can insert elements until queue becomes full. But once if queue becomes full and later if elements are dequeued, we have to shift all the elements every time an element is to be inserted in the queue.
Q. What is the difference between the Singly Linked List and Doubly Linked List data structure?
Answer:
This is another classical interview question on the data structure, mostly asked on telephonic rounds. The main difference between the singly linked list and the doubly linked list is the ability to traverse.
In a singly linked list, a node only points towards the next node, and there is no pointer to the previous node, which means you can not traverse back on a singly linked list.
On the other hand, the doubly linked list maintains two pointers, towards the next and previous node, which allows you to navigate in both directions in any linked list.
Q. How to identify the third element from the end in a linked list in one pass?
Answer:
If the same trick as above of maintaining two pointers is applied where one pointer increments, when first has moved up to the 3rd element, then in that case when the first pointer reaches to the end of the given linked list, the second pointer will be pointing to the 3rd element of the list from last.
Q. Describe some of the operations that are performed on different Data Structures?
Answer:
Operations that can be performed on data structures are as below:
Insertion: This is used to add a new data item in the existing set of data items.
Deletion: This is used to delete an already available data item from the existing set of data items.
Traversal: This can be used to access each data item only once before it is processed.
Searching: This can be used to find out the location of the data item if that particular item exists in the given collection of data items.
Sorting: This one is for arranging the data items in some order such as in ascending or descending order if numerical data and in dictionary order if alphanumeric data.
The Best Data Structures and Algorithms Interview Questions and Answers in Java
Q. What do you understand by Data Structure?
Answer:
A data structure can be considered as a way of organizing the data for efficient utilization.
For example, Binary trees are particularly suited for database implementation, while compiler implementations are usually done using hash tables to look up identifiers.
Q. What are linear and non-linear types of data Structures? Also, How is an Array different from Linked List?
Answer:
Linear: A data structure is called as linear if its elements form a sequence or a linear list such as Array, Linked List, Stacks, and Queues.
Non-Linear: A data structure is called as non-linear if traversal of nodes is of nonlinear nature such as Graphs and Trees.
Difference between array and linked list are the following: –
- The size of the arrays is fixed always, Linked Lists size is not fixed.
- Insert and delete in an array is an expensive process, whereas the same can be easily done in Linked Lists.
- Accessing an element randomly is not possible in case of Linked Listed, but possible in an array.
- Extra memory space for a pointer is needed with each element of the Linked list, arrays don’t have pointers.
- Arrays have better cache locality mechanism that can make a big difference in performance.
Q. Why do we need to do algorithm analysis?
Answer:
A problem can be solved in more than one way. So, many solution algorithms can be derived for a given problem. We analyze available algorithms to find and implement the best suitable algorithm.
Q. What are asymptotic notations?
Answer: Asymptotic analysis can provide three levels of mathematical binding of execution time of an algorithm −
- Best case is represented by Ω(n) notation.
- Worst case is represented by Ο(n) notation.
- Average case is represented by Θ(n) notation.
Q. What are common operations that can be performed on a data-structure?
Answer:
The following operations are commonly performed on any data-structure −
Insertion − adding a data item
Deletion − removing a data item
Traversal − accessing and/or printing all data items
Searching − finding a particular data item
Sorting − arranging data items in a pre-defined sequence
Q. Briefly explain the approaches to develop algorithms.
Answer:
There are three commonly used approaches to develop algorithms −
Greedy Approach − finding solution by choosing next best option
Divide and Conquer − diving the problem to a minimum possible sub-problem and solving them independently
Dynamic Programming − diving the problem to a minimum possible sub-problem and solving them combinedly
Frequently Data Structures and Algorithms Interview Questions and Answers in Java
Q. What is stack?
Answer:
In data-structure, stack is an Abstract Data Type (ADT) used to store and retrieve values in Last In First Out method.
Q. Why do we use stacks?
Answer:
Stacks follows LIFO method and addition and retrieval of a data item takes only Ο(n) time. Stacks are used where we need to access data in the reverse order or their arrival. Stacks are used commonly in recursive function calls, expression parsing, depth first traversal of graphs etc.
Q. Why do we use queues?
Answer:
As queues follows FIFO method, they are used when we need to work on data-items in exact sequence of their arrival. Every operating system maintains queues of various processes. Priority queues and breadth first traversal of graphs are some examples of queues.
Q. How would you detect and remove a loop in a linked list?
Answer:
A linked list is a data structure that, like an array, is linear. However, whereas an array stores its elements in contiguous locations, linked lists store elements randomly and links them through pointers. Generally, a linked list as a data structure constructed from nodes, each consisting of a data field and a link that points to the next node in the list. Loops in a linked list could cause errors in the program. To answer this question well, you should have a solid knowledge of recursion as it is a recursive data structure.
Example: “To detect and a remove a loop in a linked list, you should write a detectAndRemoveLoop() function, which checks for loop in a linked list and then removes it if present and then returns true. If no loop is detected, the function returns false.”
Q. How do you implement a postorder tree traversal recursion?
Answer: The binary tree is a data structure that, unlike arrays and linked lists, does not store elements in a linear fashion, but in a hierarchical way. This binary tree questions tests your ability to evaluate or delete an expression. To answer this question, you should be able to visually show how to create a postorder recursion for the hiring manager to see your process.
Example: “A post-order tree traversal of node ‘n’ involves the following steps, starting from the root:
The left subtree of ‘n’ is traversed by calling printPostorder(n.left).
The right subtree of ‘n’ is traversed by calling printPostorder(n.right).
Then the node ‘n’ itself is visited.”
Q. What is an AVL Tree?
Answer:
AVL trees are height balancing binary search tree. AVL tree checks the height of left and right sub-trees and assures that the difference is not more than 1. This difference is called Balance Factor.
BalanceFactor = height(left-sutree) − height(right-sutree)
Q. What is a spanning tree?
Answer:
A spanning tree is a subset of Graph G, which has all the vertices covered with minimum possible number of edges. A spanning tree does not have cycles and it can not be disconnected.
Q. What is the difference between Stack and Queue data structure?
Answer:
One of the classical data structure interviews question. I guess everyone knows, No? Anyway, the main difference is that Stack is LIFO (Last In First Out) data structure while Queue is a FIFO (First In First Out) data structure
Q. Explain Binary Heap?
Answer:
Binary Heap is a complete binary tree, which answers to the heap property. In simple terms it is a variation of a binary tree with the following properties:
Heap is a complete binary tree: A tree is said to be complete if all its levels, except possibly the deepest, are complete. This property of Binary Heap makes it suitable to be stored in an array.
Follows heap property: A Binary Heap is either a Min-Heap or a Max-Heap.
Min Binary Heap: For every node in a heap, node’s value is lesser than or equal to values of the children
Max Binary Heap: For every node in a heap, the node’s value is greater than or equal to values of the children
Popular applications of binary heap include implementing efficient priority-queues, efficiently finding the k smallest (or largest) elements in an array and many more.
Q. What is QuickSort in Java?
Answer:
Quicksort algorithm is a fast, recursive, non-stable sort algorithm which works by the divide and conquer principle. It picks an element as pivot and partitions the given array around that picked pivot.
Steps to implement Quick sort:
- Pick a suitable “pivot point”.
- Divide the lists into two lists based on this pivot element. Every element which is smaller than the pivot element is placed in the left list and every element which is larger is placed in the right list. If an element is equal to the pivot element then it can go in any list. This is called the partition operation.
- Recursively sort each of the smaller lists.
Here’s pseudocode representing Quicksort Algorithm.
QuickSort(A as array, low as int, high as int){
if (low < high){
pivot_location = Partition(A,low,high)
Quicksort(A,low, pivot_location)
Quicksort(A, pivot_location + 1, high)
}
}
Partition(A as array, low as int, high as int){
pivot = A[low]
left = low
for i = low + 1 to high{
if (A[i] < pivot) then{
swap(A[i], A[left + 1])
left = left + 1
}
}
swap(pivot,A[left])
return (left)}
In the above pseudocode, partition() function performs partition operation and Quicksort() function repeatedly calls partition function for each smaller list generated. The complexity of quicksort in the average case is Θ(n log(n)) and in the worst case is Θ(n2).
Related Interview Questions
- Core Java Interview Questions
- JSF Interview Questions
- JSP Interview Questions
- JPA Interview Questions
- Spring Framework Interview Questions
- Spring Boot Interview Questions
- Core Java Multiple Choice Questions
- 60 Java MCQ Questions And Answers
- Aricent Java Interview Questions
- Accenture Java Interview Questions
- Advanced Java Interview Questions For 5 8 10 Years Experienced
- Core Java Interview Questions For Experienced
- GIT Interview Questions And Answers
- Network Security Interview Questions
- CheckPoint Interview Questions
- Page Object Model Interview Questions
- Apache Pig Interview Questions
- Python Interview Questions And Answers
- Peoplesoft Integration Broker Interview Questions
- PeopleSoft Application Engine Interview Questions