In this data structure interview question, you can also discuss your experience and situations using queue. 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.
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.
1. A music playlist with next and previous navigation buttons.
2. The browser cache with BACK-FORWARD visited pages.
3. The undo and redo functionality on a browser, where you can reverse the node to get to the previous page.
Data abstraction is a powerful tool for breaking down complex data problems into manageable chunks. This is applied by initially specifying the data objects involved and the operations to be performed on these data objects without being overly concerned with how the data objects will be represented and stored in memory.
A postfix expression is an expression in which each operator follows its operands. The advantage of this form is that there is no need to group sub-expressions in parentheses or to consider operator precedence.
The amount of memory to be allocated or reserved would depend on the data type of the variable being declared. For example, if a variable is declared to be of integer type, then 32 bits of memory storage will be reserved for that variable.
Pushing and popping applies to the way data is stored and retrieved in a stack. A push denotes data being added to it, meaning data is being “pushed” into the stack. On the other hand, a pop denotes data retrieval, and in particular, refers to the topmost data being accessed.
Null is a value, whereas Void is a data type identifier. A variable that is given a Null value indicates an empty value. The void is used to identify pointers as having no initial size.
Merge sort, is a divide-and-conquer approach for sorting the data. In a sequence of data, adjacent ones are merged and sorted to create bigger sorted lists. These sorted lists are then merged again to form an even bigger sorted list, which continues until you have one single sorted list.
FIFO stands for First-in, First-out, and is used to represent how data is accessed in a queue. Data has been inserted into the queue list the longest is the one that is removed first.
Apart from being able to store simple structured data types, dynamic memory allocation can combine separately allocated structured blocks to form composite structures that expand and contract as needed.
It depends on where you intend to apply linked lists. If you based it on storage, a linked list is considered non-linear. On the other hand, if you based it on access strategies, then a linked list is considered linear.
Multidimensional arrays make use of multiple indexes to store data. It is useful when storing data that cannot be represented using single dimensional indexing, such as data representation in a board game, tables with data stored in more than one column.
A stack is a data structure in which only the top element can be accessed. As data is stored in the stack, each data is pushed downward, leaving the most recently added data on top.
Hashing is a very useful technique used to convert a range of key-value pairs into indexes of an array. Hash tables come in handy while creating associative data storage in which data index can easily be found just by providing its key-value pair!
The interpolation search technique is a modification over the Binary Search method.
The interpolation search algorithm works on the probing position of desired values.
By definition, a recursive function calls itself back or directly calls a function that calls it. Every recursive function has some base criteria, following which the function stops calling itself.
MSTs, in weighted graphs, are trees that have minimum weight, but they span across all the vertices.
Prim’s algorithm works by considering nodes as single trees. Then, it keeps on adding new nodes to the spanning tree from the given graph that has to be converted into the required spanning tree.
Kruskal’s Algorithm considers the graph as a forest and each of its nodes as an individual tree. A tree is said to connect to another tree if and only if it has the least cost among all the options, and it violates no property of a Minimum Spanning Tree (MST).
The differences between the cycle, path, and circuit are as follows:
>> A patch is an order of neighbouring vertices connected by edges without any restrictions.
>> A cycle is a closed path wherein the initial vertex is the same as the end vertex. In a cycle, no particular verte can be visited twice.
>> A circuit, like a cycle, is a closed path with the initial vertex the same as the end vertex. However, any particular vertex in a circuit can be visited more than once.
The Graph (G) Data Structure can be defined as an ordered set G(V,E) where V represents the set of vertices and E is the edges that form the connections. Basically, a Graph can be thought of as a cyclic tree where nodes can maintain complex relationships between them and not just parent-child relationships.
A B-Tree of an order m contains the following properties:
<> All the properties of an M-way tree.
<> Every node of the B_tree will have maximum m children.
<> Every node except root and leaf will have at least m / 2 children.
<> The root node must have at least 2 child nodes.
<> All leaf nodes must lie on the same horizontal level.
AVL trees are height-balanced trees, so they don’t allow for the tree to get skewed from any one side. The time taken for all the operations performed on BST of height h is O(h). However, this can go on to be O(n) in the worst case scenario – where BST becomes skewed. AVL helps in eliminating this limitation by restricting the height of the tree. In doing so, it imposes an upper bound on all the operations to be maximum of O(log n) where n = number of nodes.
Bubble sort algorithm is also referred as sinking sort. In this type of sorting, the list to be sorted out compares the pair of adjacent items. If they are organized in the wrong order, it will swap the values and arrange them in the correct order.
All recursive algorithm must follow three laws
>> It should have a base case
>> A recursive algorithm must call itself
>> A recursive algorithm must change its state and move towards the base case
Recursive algorithm is a method of solving a complicated problem by breaking a problem down into smaller and smaller sub-problems until you get the problem small enough that it can be solved easily. Usually, it involves a function calling itself.
Radix sort puts the element in order by comparing the digits of the numbers. It is one of the linear sorting algorithms for integers.
Best case scenario:
Best case scenario for an algorithm is explained as the arrangement of data for which the algorithm performs best. For example, we take a binary search, for which the best case scenario would be if the target value is at the very center of the data you are searching. The best case time complexity would be 0 (1)
Worst case scenario: It is referred for the worst set of input for a given algorithm. For example quicksort, which can perform worst if you select the largest or smallest element of a sublist for the pivot value. It will cause quicksort to degenerate to O (n2).
Some of the commonly used cryptographic algorithms are
<> DES and Triple DES
<> LOKI and so on
Encryption is the process of converting plaintext into a secret code format referred as “Ciphertext”. To convert the text, algorithm uses a string of bits referred as “keys” for calculations. The larger the key, the greater the number of potential patterns for creating cipher text. Most encryption algorithm use codes fixed blocks of input that have length about 64 to 128 bits, while some uses stream method.
To know whether the linked list has a loop, we will take two pointer approach. If we maintain two pointers, and we increase one pointer after processing two nodes and other after processing every node, we are likely to encounter a situation where both the pointer will be pointing to the same node. This will only occur if linked list has a loop.
“Hash Algorithm” is a hash function that takes a string of any length and decreases it to a unique fixed length string. It is used for password validity, message & data integrity and for many other cryptographic systems.
Insertion sort is an in-place sorting algorithm which means that it requires no extra or little. storage. For insertion sort, it requires only single list elements to be stored out-side the initial data, making the space-complexity 0(1).
Skip list the method for data structuring, where it allows the algorithm to search, delete and insert elements in a symbol table or dictionary. In a skip list, each element is represented by a node. The search function returns the content of the value related to key. The insert operation associates a specified key with a new value, while the delete function deletes the specified key.
Some problems that use Divide and conquer algorithm to find their solution are listed below.
> Merge Sort
> Quick Sort
> Binary Search
> Strassen's Matrix Multiplication
> Closest pair (points)
Dijkstra's algorithm is an algorithm for finding the shortest path from a starting node to the target node in a weighted graph. The algorithm makes a tree of shortest paths from the starting vertex and source vertex to all other nodes in the graph.
Suppose you want to go from home to office in the shortest possible way. You know some roads are heavily congested and challenging to use this, means these edges have a large weight. In Dijkstra's algorithm, the shortest path tree found by the algorithm will try to avoid edges with larger weights.
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 minus one. In this manner, You can reference all the elements in sequence by using the loop counter as the array subscript.
Heap-sort can be defined as a comparison based sorting algorithm. It divides its input into the unsorted and sorted region, until it shrinks the unsorted region by eliminating the smallest element and moving that to the sorted region.
Since random access is not acceptable in linked list, it is impossible to reach the middle element of O(1) time. Thus, binary search is not possible for linked list.
1. Multi-dimensional arrays are those data structures that span across more than one dimension.
2. This indicates that there will be more than one index variable for every point of storage. This type of data structure is primarily used in cases where data cannot be represented or stored using only one dimension. Most commonly used multidimensional arrays are 2D arrays.
3. 2D arrays emulates the tabular form structure which provides ease of holding the bulk of data that are accessed using row and column pointers.
In binary search, we compare the key with the item in the middle position of the array. If the key is less than the item searched then it must lie in the lower half of the array, if the key is greater than the item searched than it should be in upper half of the array.
Time complexity of an algorithm indicates the total time needed by the program to run to completion. It is usually expressed by using the big O notation.
Divide and Conquer is not an algorithm; it's a pattern for the algorithm. It is designed in a way as to take dispute on a huge input, break the input into minor pieces, and decide the problem for each of the small pieces. Now merge all of the piecewise solutions into a global solution. This strategy is called divide and conquer.
Divide and conquer uses the following steps to make a dispute on an algorithm.
Divide: In this section, the algorithm divides the original problem into a set of subproblems.
Conquer: In this section, the algorithm solves every subproblem individually.
Combine: In this section, the algorithm puts together the solutions of the subproblems to get the solution to the whole problem.
The complexity of the algorithm is a way to classify how efficient an algorithm is compared to alternative ones. Its focus is on how execution time increases with the data set to be processed. The computational complexity of the algorithm is important in computing.
It is very suitable to classify algorithm based on the relative amount of time or relative amount of space they required and specify the growth of time/ space requirement as a function of input size.
Time complexity is a Running time of a program as a function of the size of the input.
Space complexity analyzes the algorithms, based on how much space an algorithm needs to complete its task. Space complexity analysis was critical in the early days of computing (when storage space on the computer was limited).
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.
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.
Data Structures can be broadly divided into two categories:
<> Linear: In this, all the elements are stored sequentially, and retrieval takes place linearly. The arrangement is non-hierarchical, and each element has one successor and one predecessor. Example – Arrays, Linked Lists, Stacks, Queues, etc.
<> Non-linear: Here, the storage does not happen in a linear sequence – i.e., all elements don’t necessarily have just one successor and predecessor. Instead, elements in non-linear Data Structures are connected to two or more items in a non-linear manner. Example – Trees, Graphs, Heaps.
In File Structures, the data is stored on disks following standard file storage policies and is not compatible with external, third-party applications. In Data Structures, on the other hand, the data is stored both on the disk as well as RAM in customised storage policies, and these are highly compatible with external apps.
Data Structures can be defined as techniques used to define, store, and access data systematically. They form the most important component of any algorithm. Depending on the type of Data Structures, they store different kinds of data and are accessible in different ways. For an algorithm to return a result, it needs to operate on and manipulate a set of data structures in an organised and efficient manner to come to the final result.
An algorithm is a well-defined computational procedure that takes some values or the set of values, as an input and produces a set of values or some values, as an output.
Need for Algorithm
The algorithm provides the basic idea of the problem and an approach to solve it. Some reasons to use an algorithm are as follows.
<> The algorithm improves the efficiency of an existing technique.
<> To compare the performance of the algorithm with respect to other techniques.
<> The algorithm gives a strong description of requirements and goal of the problems to the designer.
<> The algorithm provides a reasonable understanding of the flow of the program.
<> The algorithm measures the performance of the methods in different cases (Best cases, worst cases, average cases).
<> The algorithm identifies the resources (input/output, memory) cycles required by the algorithm.
<> With the help of an algorithm, we can measure and analyze the complexity time and space of the problems.
<> The algorithm also reduces the cost of design.