Published in

Geek Culture

# Interview questions on Data Structures

## Interview Preparation on Data Structures for Software Engineering

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.
• 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.
• 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.
• 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.
• 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.
• 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.
• 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.
• 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.
• 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.
• The Dequeue (double-ended queue) is an ordered set of elements that may be inserted and deleted at both ends.
• 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.
• 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.
`int a=15;int b=12;a=a+bb=a-ba=a-b// Now values of a,b are exchanged without using a third variable`
• 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.
• 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.
• 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.
• 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.
• 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.
• 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.
• 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.

--

--

## More from Geek Culture

A new tech publication by Start it up (https://medium.com/swlh).