Interview Experience and Guide — part 4

Interview questions on Data Structures

Interview Preparation on Data Structures for Software Engineering

Hi all 😊, Today I am gonna share the common Data Structures related interview questions as part of my interview preparation series for Software Engineers. This is the fourth part of the series. In case you missed the previous sessions, you can read the first part here, OOP & Java, Database. Without further delay, let’s jump into today’s topic Data Structures.

Photo by Edgar Chaparro on Unsplash

Data Structures is a method of organizing data in a computer so that it may be efficiently used. There are a lot of Data Structures are available in every programming language. Each of them has its own characteristics, pros and cons as well. There will be a great potion of interview questions from data structures as well for software engineers as it is a fundamental knowledge in software engineering. To develop any kind of application or anything the presence of one or many data structures is unavoidable in software development. It is used from the Hello World program to complex problems in the software industry. In this article, the main data structures are covered that are available in Java. Let's move to the interview point of view in Data structures. These are the most asked questions in interviews.

1. What is meant by linear and non-linear data structures give some examples?

• A linear data structure is one in which data items are stored consecutively or linearly, with each member attached to its previous and next to neighbouring elements. As a result, we can explore all of the elements in only one run. Because computer memory is organized in a linear fashion, linear data structures are simple to build. Eg: List, Stack, Queue, Arraylist
• Non-linear data structures are data structures in which data elements are not ordered sequentially or linearly. As a result, we won’t be able to traverse all of the elements in a single run. In comparison to linear data structures, non-linear data structures are more difficult to construct. Eg: Trees, Maps, Graphs.

Photo by Denny Müller on Unsplash

2. What do you think about Linked lists is it linear Data structure?

• Linked lists are classified as either linear or non-linear data structures, depending on the application. It’s a linear data structure when it’s utilized for access methods. It’s a non-linear data structure when it’s utilized for data storage.

3. Compare and Contrast Array and LinkedList in Java?

• Array: Continuos memory allocation, Fixed Size, Can be accessed by Index, Insertion, and deletion in the middle is costly.
• LinkedList: No requirement for continuous memory allocation, dynamic memory allocation(No fixed size), No access by index, run through the collection for access, Insertion, and deletion in the middle is comparatively cheap in costs, Extra memory cost for pointers.

4. What is the difference between the Stack and Queue data structures?

• A stack is a linear data structure in which elements can only be added and removed from the top of the data structure. The LIFO is followed by a stack ( Last In First Out). The insertion of an element into the stack is known as a push operation, and the removal of an element from the stack is known as a pop operation.
• Following are some of the applications of a stack. Check for balanced parentheses in an expression, Evaluation of a postfix expression, Reverse a string
• A queue is a linear data structure in which elements can only be inserted from one side of the list, called the rear, and can only be deleted from the other side, called the front. FIFO (First In, First Out) method is used in the queue to access elements. Here en queue is used for insertion and dequeue is used for deletion.
• Only one pointer, called the top, is used to access the list in stacks, and it always points to the last entry in the list. We keep two pointers in the queue to access the list. The first pointer is always present and points to the first element placed in the list, whereas the rear pointer is always present and points to the final inserted element.
• Some of the applications of the queue are: Website request processing, CPU Task scheduling, Used as buffers in applications like MP3 media player, CD player and etc.

Photo by Zichao Zhang on Unsplash

5. What is the difference between graph and tree data structures?

• Graph: Non-linear data structure, Collection of vertices/nodes and edges, Multiple paths among nodes, No unique node called root, A cycle can be formed. Applications: For finding the shortest path in networking
• Tree: Non-linear data Structure, Collection of vertices/nodes and edges, Only one path from a node to node, General trees consist of nodes having any number of child nodes. But in the case of binary trees, every node can have at most two child nodes. There is a unique node called root, There will be no cycle. Applications: For game trees, Decision trees.

6. What is the difference between array vs sets?

• The biggest difference between an array & Set is that arrays can have duplicate values whereas sets can not have duplicates.
• Data in an array is ordered by index where assets use keys & the elements are iterable in the order of insertion.

7. What is meant by dynamic Data Structures?

• They are memory collections of data that expand and contract while a program runs, allowing them to increase or reduce in size. This allows the programmer to precisely manage the amount of memory used.
• Dynamic arrays, linked lists, stacks, queues, and heaps are some examples of data structures.

8. What are the differences between hashmap and hashtable?

• Hashmap is not synchronized. Cant be used in multi-threaded environments. But Hashtable is synchronized.
• Hashmap allows one null key and multiple null values whereas hashtable doesn't allow any null key or value.
• Hashmap is generally preferred over hashtable if thread safety is not required.

Photo by Masha Kotliarenko on Unsplash

9. What is a doubly-linked list?

• A doubly linked list is a more complicated sort of a linked list in which each node has a pointer to both the previous and next node in the sequence. A node in a doubly-linked list is made up of three parts: Data, Next data pointer and Previous data pointer.
• Doubly linked lists can be used in Undo-Redo operations in software, Next song, previous song section in music players and etc.

10. What is a dequeue?

• The Dequeue (double-ended queue) is an ordered set of elements that may be inserted and deleted at both ends.

11. How does HashMap handle collisions in Java?

• To address collisions, Java’s Java.util.HashMap class use a chaining mechanism. If new values with the same key are attempted to be pushed, these values are saved in a linked list stored in the key’s bucket as a chain together with the existing value in chaining.
• In the worst-case situation, all keys may have the same hashcode, resulting in the hash table being converted into a linked list. Due to the structure of the linked list, searching for a value will require O(n) time rather than O(1) time in this example. As a result, caution must be given while choosing a hashing algorithm.

Photo by Julie Tupas on Unsplash

12. What is a heap data structure?

• Heap is a non-linear data structure built on a tree with a complete binary tree as the tree. A binary tree is considered to be full if all levels are entirely filled, with the exception of the last level, which has all components pointing to the left as much as feasible. Heaps are of two types.
• Max-Heap: In a Max-Heap, the data element at the root node must be the most significant of all the data items in the tree. This condition should be true for all sub-trees of that binary tree recursively.
• Min-Heap: In a Min-Heap, the data element at the root node must be the smallest of all data items in the tree. This condition should be true for all sub-trees of that binary tree recursively.

Photo by Florian Olivo on Unsplash

13. How to find the second largest number in the given unsorted array?

14. How to swap two integer numbers without using a third variable?

int a=15;
int b=12;
a=a+b
b=a-b
a=a-b
// Now values of a,b are exchanged without using a third variable

15. Algorithm to Find the first duplicate letter in a given string?

• Here the time complexity of the given algorithm is O(n). HashSet is used to get the time complexity of the search in the set as O(1).
• The Break is used to avoid the for loop running after the duplicate is found.

16. What are the benefits of using a heap instead of a stack?

• Because memory space may be dynamically allocated and de-allocated as needed, the heap is more flexible than the stack. Objects are stored in heap memory in Java, whereas local variables and function calls are stored in stack memory.
• Variables kept on stacks are solely accessible to the user as private memory, but objects produced in the heap are visible to all threads. The size of heap memory increases while utilizing recursion, whereas stack memory quickly fills up.

Photo by Bekir Dönmez on Unsplash

17. Is there a limit to how many nodes a binary tree can have?

• When the nodes have NULL values, a binary tree might have a minimum of zero nodes. In addition, a binary tree can have one or two nodes.

18. What are the differences between Stack and Array?

• A LIFO pattern is followed by Stack. It indicates that data is accessed in a sequential manner, with the most recently stored data being the first to be extracted. Arrays, on the other hand, do not follow any sort of order and can be accessed simply by referring to the array’s indexed element.

19. In a linked list, how do you look for a certain key?

• The sequential search must be used to find the target key in a linked list. Each node is visited and compared to the target key; if the two are different, it proceeds to the next node along with the link. This process continues until the target key or the last node is located.

xPhoto by Karine Avetisyan on Unsplash

20. What is an AVL Tree?

• The AVL tree is a self-balancing Binary Search Tree (BST) with a maximum height difference between left and right subtrees of one for all nodes.

21. What is the most suitable Data Structure that can be used to check a String whether it is a palindrome or not?

• Stack
• Determine the string’s length. Now you must be able to locate the middle.
  All of the items should be pushed all the way to the middle of the stack.
  If the string’s length is odd, ignore the middle character. Keep popping items from the stack and comparing them to the current character until the string is finished.
• The string is not a palindrome if there is a mismatch. The string is a palindrome if all of the components match.

I believe that you understood all the matters discussed above related to the data structures topic for interviews. If you have any concerns or any clarifications, don’t hesitate to contact me through the response section. Thank you for spending your precious time reading this blog and I am believing this will inspire you to continue reading other blogs about facing interviews.

Enjoyed the article? Become a Medium member to continue learning without any limits. I’ll receive a portion of your membership fee, if you use the above link, with no extra cost to you. Thanks in advance.

Photo by Alexas_Fotos on Unsplash